上面文章讲完了插入排序和交换排序,本次我们来讨论选择排序。

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。选择排序是不稳定的排序方法(比如序列[5, 5, 3]第一次就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)。


1、普通(单个)选择排序

每遍历一次,记录下最值元素所在位置,遍历结束后,将此最值元素调整到合适的位置。这样一次遍历,只需一次交换,便可将最值放置到合适位置

//成功返回0,失败返回-1intselect_sort(int*arr,constintn){//判断参数是否正确if(NULL==arr||0>=n)return-1;inti=0;//循环使用intj=0;//循环使用intk=-1;//记录比较的下标inttemp;//交换时作中间值//每次循环只进行一次交换最多进行n-1次循环,因此总体上,比冒泡进行交换的次数少for(i=0;i<n-1;i++){//第i次排序时,已经进行了i次大循环,因此已经排好了i个元素//已排好序的元素0,,...,i-2,i-1//待排元素为i,i+1,...,n-1k=i;//拿i的位置值与后面的值相比较for(j=i+1;j<n;i++){if(arr[k]<arr[j])k=j;}//判断k值是否有变化,有变量就交换if(k!=i){temp=arr[k];arr[k]=arr[i];arr[i]=temp;}}return0;}


2、二分选择排序

intselect_sort(int*arr,constintn){//判断参数是否正确if(NULL==arr||0>=n)return-1;inti=0;intj=0;intminpos=-1;intmaxpos=-1;inttemp;//每次循环完进行二次交换最多进行n/2次循环,因此总体上,比冒普通选择排序的次数少for(i=0;i<n/2;i++){minpos=i;maxpos=i;for(j=i+1;j<n;j++){if(arr[j]>arr[maxpos]){maxpos=j;continue;}if(arr[j]<arr[minpos]){minpos=j;}}temp=arr[i];arr[i]=arr[minpos];arr[minpos]=temp;if(maxpos==i){temp=arr[minpos];arr[minpos]=arr[n-1-i];arr[n-1-i]=temp;}else{temp=arr[maxpos];arr[maxpos]=arr[n-1-i];arr[n-1-i]=temp;}}return0;}