排序之简单选择排序

选择排序：通过n-i次关键字的比较，从n-i+1个记录中，选出关键字最小的记录，和第i个记录交换。

选择排序的关键，我认为，在于只进行了一次交换，因为引入了一个变量min，可以存储关键字最小的记录。

就时间复杂度上而言，由于简单排序时，比较和交换是分开的。因此要从两个方面考虑。

比较的次数：（n-1）+（n-2）+..+1 = （n-1）n/2；

交换的次数：最好的时候：0次；

最差的时候：n-1次。

因此总的时间复杂度为O(n2)。

/*选择排序：通过n-i次关键字之间的比较，找到n-i+1个关键字中最小的记录，并与第i个记录交换*/ #include<iostream> using namespace std; #define M 6 void swap(int *a, int m, int n) { int temp; temp = a[m]; a[m] = a[n]; a[n] = temp; } void Selectsort (int *a,int length) { int i,j,min; int m = length-1; for(i=0;i<m;i++) { min = i; for(j=i+1;j<=m;j++) { if(a[min]>a[j]) min = j; } if(i != min) swap(a,min,i); } } int main () { int r[M]; for(int i=0;i<M;i++) r[i]=rand()%M; for(int i=0;i<M;i++) cout<<r[i]; cout<<endl; Selectsort(r,M); for(int i=0;i<M;i++) cout<<r[i]; return 0; }