上一篇我们讲了插入排序，这一篇我们来讲选择排序。因为堆排序之前我们有详细讲过，所以这里只给出堆排序的思路，有兴趣的可以看一看。
选择排序
选择排序就是从数组中选出最小值和最大值，最小值放在第一个位置，最大值放在最后一个位置，依次执行，直到排成有序数组为止。
直接选择排序
直接选择排序就是从begin到end范围中获取最大值和最小值，将最小值放到begin位置，最大值放到end位置。依次执行直到排成有序数组为止。
思路
比如说我们有以下数组：
我们把数组起始位置作为begin，末尾作为end，从中找出最小值mini和最大值maxi。
我们将最小值mini位置和begin位置数据交换一下，然后将最大值maxi位置和end位置数据交换一下，使得最小值放到begin位置，最大值放到end位置。
然后begin++，end- -，再从beign到end范围中找出最小值mini和最大值maxi。
将mini和begin数据交换，maxi和end数据交换。
然后begin++，end- -，继续从begin到end范围中找最小值和最大值。
此时我们发现maxi在begin位置，如果我们继续直接交换mini和begin，maxi和end就会发生这样一件事。
我们发现最小值没有来到begin位置，最大值也没有到end位置，这是为什么呢？
maxi在begin位置的时候，我们先交换的是begin和mini位置的数据，这会导致maxi被交换到了mini的位置。
因此，当begin == maxi的时候，我们要让maxi = mini，这步的意义是存储begin被交换后maxi当前所处的位置，这样end和maxi交换才不会出错。## 代码实现
综上所述，我们排序的循环条件是begin < end，当end >= begin的时候则说明排序结束了。然后初始情况下begin = 0，end = n - 1;每次找到最小值最大值并放到begin，end位置后，begin++，end–。
接下来我们定义mini和maxi，我们让它们一开始等于begin，然后从begin + 1到end位置遍历一遍找最大值和最小值。
因为我们是先将最小值放到begin处，所以要判断begin == maxi是否成立，如果成立则让maxi = mini，记录交换后最大值的位置。
如果我们是先将最大值放到end处，则需要判断end == mini，成立则让mini = maxi。
然后将mini处数据和begin处交换，maxi处数据和end处交换。
这个代码就写好了。
我们来简单测试一下。
结果符合预期，说明代码没什么问题。
时间复杂度
该算法嵌套了两层循环，外层因为是两边同时查找，循环次数缩短到了 n/2，内层循环总次数也相当于一个公差为 -2 的等差数列之和，总的来说无论什么情况，该算法时间复杂度为 O(n2)。
堆排序
如果有兴趣的可以看看这篇文章，详细内容不再赘述。
数据结构:堆排序
堆排序是利用堆的思想来进行排序的算法，将原数组通过向上/向下调整算法调整成一个大堆，然后堆顶和堆底元素（数组开头和末尾）进行交换，数组大小 size–，再调整前 size 个元素保证成为一个大堆结构，循环往复直到 size == 0，排序结束。
voidSwap(int*x,int*y){inttmp=*x;*x=*y;*y=tmp;}//向下调整算法voidAdjustDown(int*arr,intparent,intn){intchild=parent*2+1;//左孩子while(child<n){if(child+1<n&&arr[child+1]>arr[child])child++;if(arr[parent]<arr[child]){Swap(&arr[parent],&arr[child]);parent=child;child=parent*2+1;}elsebreak;}}//向上调整算法AdjustUp(int*arr,intchild){intparent=(child-1)/2;while(child>0){if(arr[parent]<arr[child]){Swap(&arr[parent],&arr[child]);child=parent;parent=(child-1)/2;}elsebreak;}}//堆排序voidHeapSort(int*arr,intn){//建大堆for(inti=(n-1-1)/2;i--;i>=0){AdjustDown(arr,i,n);}//排序while(n>0){//交换堆顶和堆底元素Swap(&arr[0],&arr[n-1]);n--;AdjustDown(arr,0,n);}}
)
