首页 > 代码库 > 2.用选择排序对10个数进行排序

2.用选择排序对10个数进行排序

2024-07-16 21:46:39   216人阅读

【原理】
首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置；接着，再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
 
【复杂度和稳定性】

（1）选择排序时间复杂度
选择排序的时间复杂度是O(N2)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历N-1。因此，选择排序的时间复杂度是O(N2)。

（2）选择排序稳定性
选择排序是稳定的算法，它满足稳定算法的定义。
算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

 

【代码】

#include<iostream>using namespace std;template<class T>//模板的使用void selection_sort(T Array[],const int size);int main(){    int a[10];    cout<<"please input 10 numbers:"<<endl;    for(int i=0;i<10;i++)//用于输入内容    {        cin>>a[i];    }    selection_sort(a,sizeof(a)/sizeof(int));//调用函数，要注意sizeof(a)/sizeof(int)的意义    for(int j=0;j<10;j++)//输出数组    {        cout<<a[j]<<" ";    }    return 0;}template<class T>void selection_sort(T Array[],const int size){    int min;//确定最小值的数组下标    int temp;//中间值    for(int m=0;m<size-1;m++)//外层循环确定边界（即循环的最大值）    {        min=m;//确定数组最小值的下标，将之前已排序的固定        for(int n=m+1;n<size;n++)//内层循环用于判断哪个数据最小        {            if(Array[n]<Array[min])//判断最小值            {                min=n;//确定最小值的数组下标            }        }        if(min!=m)//交换数据        {            temp=Array[m];            Array[m]=Array[min];            Array[min]=temp;        }    }}

 


联系
我们