选择排序（直接选择排序、堆排序）

直接选择排序

直接选择排序是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

我们这里直接给出选择排序的优化，一次选出两个数据。

void SelectSort(int *arr, int n) { for (int i = 0; i < n; ++i) { int begin = i; int end = n; int min = i; int max = i; while (begin < end) { if (arr[begin] < arr[min]) { min = begin; } else { max = begin; } ++begin; } if (i == max) { max = min; } swap(arr[i], arr[min]); swap(arr[--end], arr[max]); } }

直接选择排序的时间复杂度：O(N^2)[最好情况：O(N^2) 最坏情况：O(N^2)] 空间复杂度：O(1) 直接选择排序是一种不稳定的排序算法。

堆排序

void AdjustDown(int *arr, int root, int n) { int parent = root; int child = parent * 2 + 1; while (child<n) { if (child + 1 < n&&arr[child] < arr[child + 1]) { ++child; } if (arr[child] > arr[parent]) { swap(arr[child], arr[parent]); } parent = child; child = parent * 2 + 1; } } void HeapSort(int *arr, int n) { int *p = arr; for (int i = (n - 2) / 2; i >= 0; --i) { AdjustDown(arr, i, n); } int end = n - 1; while (end > 0) { swap(arr[0], arr[end]); AdjustDown(arr, 0, end); --end; } }

堆排序的时间复杂度：O(N*lgN)[最好情况：O(N*lgN) 最坏情况：O(N*lgN) ] 空间复杂度：O(1) 堆排序是一种不稳定的排序算法。