简单选择排序算法的C++实现

2018-06-17 21:07:21来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

简单选择排序采用最简单的选择方法,即在剩余序列中选出最小(或最大)的关键字,和剩余序列的第一个关键字交换位置,依次选择下去,直至使整个序列有序。

算法中两层循环的执行次数和初始序列没有关系,第二层循环每一次都需要遍历剩余带排序序列,故时间复杂度为O(n2)

直接上代码:

#include<iostream>
#include<string>
using namespace std;

template <typename T>
void selectionSort(T arr[],int n){

    for(int i=0;i<n;i++){
        
        //寻找[i,n)区间里的最小值
        int minIndex=i;        //为最小值的位置做个标记
        for(int j=i+1;j<n;j++)
            if(arr[j]<arr[minIndex])
                minIndex=j;
    
        swap(arr[i],arr[minIndex]);
    }
    
}


int main(){
    int array[10]={10,9,8,7,6,5,4,3,2,1};
    selectionSort(array,10);
    for(int i=0;i<10;i++)
        cout<<array[i]<<" ";
    cout<<endl;


    float a[3]={3.3f,2.2f,1.1f};
    selectionSort(a,3);
    for(int j=0;j<3;j++)
        cout<<a[j]<<" ";
    cout<<endl;

    string b[4]={"D","C","B","A"};
    selectionSort(b,4);
    for(int k=0;k<4;k++)
        cout<<b[k]<<" ";
    cout<<endl;

    return 0;
}

 对于简单选择排序,一趟排序后能确保一个关键字到达其最终位置。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:直接插入排序算法的C++实现

下一篇:C++之结构体struct