上一篇我们讲了插入排序这一篇我们来讲选择排序。因为堆排序之前我们有详细讲过所以这里只给出堆排序的思路有兴趣的可以看一看。选择排序选择排序就是从数组中选出最小值和最大值最小值放在第一个位置最大值放在最后一个位置依次执行直到排成有序数组为止。直接选择排序直接选择排序就是从begin到end范围中获取最大值和最小值将最小值放到begin位置最大值放到end位置。依次执行直到排成有序数组为止。思路比如说我们有以下数组我们把数组起始位置作为begin末尾作为end从中找出最小值mini和最大值maxi。我们将最小值mini位置和begin位置数据交换一下然后将最大值maxi位置和end位置数据交换一下使得最小值放到begin位置最大值放到end位置。然后beginend- -再从beign到end范围中找出最小值mini和最大值maxi。将mini和begin数据交换maxi和end数据交换。然后beginend- -继续从begin到end范围中找最小值和最大值。此时我们发现maxi在begin位置如果我们继续直接交换mini和beginmaxi和end就会发生这样一件事。我们发现最小值没有来到begin位置最大值也没有到end位置这是为什么呢maxi在begin位置的时候我们先交换的是begin和mini位置的数据这会导致maxi被交换到了mini的位置。因此当begin maxi的时候我们要让maxi mini这步的意义是存储begin被交换后maxi当前所处的位置这样end和maxi交换才不会出错。## 代码实现综上所述我们排序的循环条件是begin end当end begin的时候则说明排序结束了。然后初始情况下begin 0end n - 1;每次找到最小值最大值并放到beginend位置后beginend–。接下来我们定义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;*ytmp;}//向下调整算法voidAdjustDown(int*arr,intparent,intn){intchildparent*21;//左孩子while(childn){if(child1narr[child1]arr[child])child;if(arr[parent]arr[child]){Swap(arr[parent],arr[child]);parentchild;childparent*21;}elsebreak;}}//向上调整算法AdjustUp(int*arr,intchild){intparent(child-1)/2;while(child0){if(arr[parent]arr[child]){Swap(arr[parent],arr[child]);childparent;parent(child-1)/2;}elsebreak;}}//堆排序voidHeapSort(int*arr,intn){//建大堆for(inti(n-1-1)/2;i--;i0){AdjustDown(arr,i,n);}//排序while(n0){//交换堆顶和堆底元素Swap(arr[0],arr[n-1]);n--;AdjustDown(arr,0,n);}}