三、选择排序
思路1：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的 数据元素排完 。
//选择排序1 void SelectSort(int* a, int n) { int begin = 0; while (begin < n - 1) { int min = begin; for (int i = begin; i <= n - 1; i++) { if (a[i] < a[min]) { min = i;//找最小值的下标 } } Swap(&a[begin], &a[min]); ++begin; } }
思路2：
思路1是每次选一个较小数（以升序为例）放到左边，直到全部排序完成；思路二的思想就是一次选两个数，小的放左边，大的放右边；
注意点：
如何解决呢？
此时最大值被换走了，我们可以修正一下max和min的位置；
// 选择排序2 void Swap(int* px, int* py) { int tmp = *px; *px = *py; *py = tmp; } void SelectSort(int* a, int n) { int begin = 0, end = n - 1; while (begin < end) { int mini = begin, maxi = begin; for (int i = begin; i <= end; i++) { if (a[i] < a[mini]) { mini = i;//找最小值的下标 } if (a[i] > a[maxi]) { maxi = i;//找最大值的下标 } } Swap(&a[begin], &a[mini]); //begin == maxi时，最大值被换走了，修正一下maxi的位置 if (begin == maxi) { maxi = mini; } Swap(&a[end], &a[maxi]); ++begin; --end; } }
四、堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
向下调整算法：
堆排序：
如果对堆的应用还不清楚的小伙伴可以去看这里：
链接：https://blog.csdn.net/sjsjnsjnn/article/details/124201028?spm=1001.2014.3001.5501
//向下调整函数（大堆（升序）用大于，小堆（降序）用小于） void AdjustDown(int* a, int n, int parent) { assert(a); int child = parent * 2 + 1; while (child < n) { //选出左右孩子中小的那个 if (child + 1 < n && a[child + 1] > a[child]) { ++child; } //如果小的孩子小于父亲，则交换，并继续向下调整 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } // 堆排序 void HeapSort(int* a, int n) { //倒着建堆 for (int i = (n - 1 - 1) / 2; i >= 0; --i) { AdjustDown(a, n, i); } //O(N*logN) int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } }
