数据结构课设个人（六）：简单选择排序

数据结构课设个人（六）：简单选择排序 问题描述 :

对于顺序存储的线性表，使用vector或数组，实现直接选择排序算法，并输出每趟的排序结果。

参考函数原型：（vector版本）

//直接选择排序

template

void SimpleSelectSort( vector &A );

输入说明 :

第一行：顺序表A的数据元素的数据类型标记（0：int，1：double，2：char，3：string）

第二行：待排序顺序表A的数据元素（数据元素之间以空格分隔）

输出说明 :

如第一行输入值为0、1、2、3之外的值，直接输出“err”

否则：

第一行：第一趟的排序结果（数据元素之间以","分隔）

第三行：第二趟的排序结果（数据元素之间以","分隔）

...

第n行：最终的排序结果（数据元素之间以","分隔）

输入范例 :

0
21 25 49 25 16 8

输出范例 :

8,25,49,25,16,21
8,16,49,25,25,21
8,16,21,25,25,49
8,16,21,25,25,49
8,16,21,25,25,49

思路：

基本思想：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。
首先，在n个记录中选择最小者放到R[1]位置；然后，从剩余的n-1个记录中选择最小者放到R[2]位置；…如此进行下去，直到全部有序为止。

优点：实现简单
缺点：每趟只能确定一个元素，表长为n时需要n-1趟
前提：顺序存储结构 

时间效率： O(n²)——虽移动次数较少，但比较次数仍多。 
空间效率： O(1)——没有附加单元(仅用到1个temp)
算法的稳定性：不稳定——因为排序时，25*到了25的前面。

代码实现：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include    //用于ostringstream、istringstream、stringstream这三个类
#include
#include
#include
#define ArraySize 100
using namespace std;
template
void createvector( vector &A )
{
    ElemType tmp;
    string temp;
    getline(cin,temp);
    stringstream input(temp); //输入流
    while(input>>tmp)
        A.push_back(tmp);
}
//直接选择排序
template
void SimpleSelectSort( vector &A ){
    int length=A.size();
    if(length==1){
        cout<>kd;
    cin.ignore();
    if(kd==0){
        vector A;
        createvector( A );
        SimpleSelectSort( A );
    }
    else if(kd==1){
        vectorA;
        createvector( A );
     SimpleSelectSort( A );
    }
    else if(kd==2){
         vectorA;
         createvector( A );
     SimpleSelectSort( A );
    }
     else if(kd==3){
        vectorA;
        createvector( A );
     SimpleSelectSort( A );
     }
    else
        cout<<"err"< 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5691323.html