选择排序
基本思想
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
直接选择排序
- 在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
- 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
- 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
代码实现
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; while (begin < end) { int mini = begin; int 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]); if (begin == maxi) maxi = mini; Swap(&a[end], &a[maxi]); ++begin; --end; } } void TestSelectSort() { int a[] = { 105,5,8,2,50,7,-1,100,66 }; int n = sizeof(a) / sizeof(a[0]); SelectSort(a, n); Print(a, n); } int main() { TestSelectSort(); }
直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
对于堆排序而言，我们首先要做的第一步就是建堆
建完堆之后，将最后一个数据与堆顶数据交换，然后将除最后一个数据之外的所有数据重新向下调整，直至完全升序。
我们以动图的形式展示整个过程：
关于堆排序前面的博客我们已经学过一遍了，这次再提一次。
void AdjustDown(int* a, int n, int parent) { //最小的默认为左孩子 int minchild = 2 * parent + 1; while (minchild < n) { //找出小的那个孩子 if (minchild + 1 < n && a[minchild + 1] > a[minchild]) { minchild++; } //小堆 if (a[minchild] > a[parent]) { Swap(&a[minchild], &a[parent]); parent = minchild; minchild = 2 * parent + 1; } else { break; } } } void HeapSort(int* a, int n) { //建堆 for (int i = (n-1-1)/2; i>=0; i--) { AdjustDown(a, n, i); } //进行排序 int i = 1; while (i < n) { Swap(&a[0], &a[n - i]); AdjustDown(a, n - i, 0); ++i; } } void TestHeapSort() { int a[] = { 105,5,8,2,50,7,-1,100,66 }; int n = sizeof(a) / sizeof(a[0]); HeapSort(a, n); Print(a, n); } int main() { TestHeapSort(); }
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
