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

选择排序(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;}