结合文章 堆结构的实现 服用更佳。
1、堆排序的过程堆排序的过程：（此处以大根堆为例）
- 先让整个数组变成大根堆结构，建立堆的过程：
1）从上到下的方法，时间复杂度为 O ( N ∗ l o g N ) O(N * logN) O(N∗logN)
2）从下到上的方法，时间复杂度为 O ( N ) O(N) O(N) - 把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为 O ( N ∗ l o g N ) O(N * logN) O(N∗logN)
- 把堆的大小减小成 0 后，排序完成
#include3、 堆排序的时间复杂度#include #include using namespace std; void swap(vector &arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } void heapInsert(vector &arr, int ind) { while (arr[ind] > arr[(ind - 1) / 2]) { swap(arr, ind, (ind - 1) / 2); ind = (ind - 1) / 2; } } void heapify(vector &arr, int ind, int heapSize) { int left = ind * 2 + 1; while (left < heapSize) { int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; largest = arr[largest] > arr[ind] ? largest : ind; if (largest == ind) break; swap(arr, largest, ind); ind = largest; left = ind * 2 + 1; } } //堆排序 void heapSort(vector &arr) { if (arr.size() < 2) return ; //建堆： //方法一——从上到小建堆 O(NlogN) //for (int i = 0; i < arr.size(); i++) { //O(N) // heapInsert(arr, i); //O(logN) //} //方法二——从下往上建堆 O(N) for (int i = arr.size() - 1; i >= 0; i--) { heapify(arr, i, arr.size()); } int heapSize = arr.size(); swap(arr, 0, --heapSize); //O(NlogN) while (heapSize > 0) { //O(N) heapify(arr, 0, heapSize); //O(logN) swap(arr, 0, --heapSize); //O(1) } } //for test void comparator(vector &arr) { sort(arr.begin(), arr.end()); } vector generateRandomArray(int maxSize, int maxVal) { vector arr(rand() % (maxSize + 1)); for (int i = 0; i < arr.size(); i++) { arr[i] = (rand() % (maxVal + 1)) - (rand() % (maxVal + 1)); } return arr; } vector copyArray(vector &arr) { vector backUp(arr.size()); for (int i = 0; i < arr.size(); i++) { backUp[i] = arr[i]; } return backUp; } bool isEqual(vector &arr1, vector &arr2) { if (arr1.size() != arr2.size()) return false; for (int i = 0; i < arr1.size(); i++) { if (arr1[i] != arr2[i]) return false; } return true; } void printArray(vector &arr) { for (int i = 0; i < arr.size(); i++) { cout << arr[i] << " "; } cout << endl; } int main() { srand(time(0)); int testTime = 500000; int maxSize = 100; int maxValue = 100; bool success = true; for (int i = 0; i < testTime + 1; i++) { vector arr1 = generateRandomArray(maxSize, maxValue); vector arr2 = copyArray(arr1); heapSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { success = false; break; } if (i && i % 1000 == 0) cout << i << " cases passed!" << endl; } cout << (success ? "Nice!" : "Fucking fucked!") << endl; vector arr = generateRandomArray(maxSize, maxValue); printArray(arr); heapSort(arr); printArray(arr); return 0; }
O ( N l o g N ) O(NlogN) O(NlogN)
4、问：为什么建堆的时候从下到上的时间复杂度为 O ( N ) O(N) O(N) ?假设一棵树有 N N N 个节点：
- 那么它的叶子节点（最底层）从数量级上来说有 N / 2 N/2 N/2 个，这些节点在 heapify 的时候只看了自己，所以总的操作次数是 N / 2 ∗ 1 N/2 * 1 N/2∗1
- 倒数第二层节点从数量级上来说有 N / 4 N/4 N/4 个，每个节点在 heapify 时只看了 2 个节点，所以总的次数是 N / 4 ∗ 2 N/4 * 2 N/4∗2
- 倒数第三层节点从数量级上来说有 N / 8 N/8 N/8 个， heapify 到底也就是3个节点，所以总的操作次数是 N / 8 ∗ 3 N/8 * 3 N/8∗3
- 所以总的时间复杂度为： T ( N ) = N / 2 ∗ 1 + N / 4 ∗ 2 + N / 8 ∗ 3 + N / 16 ∗ 4 + . . . . . . T(N) = N/2 * 1 + N/4 * 2 + N/8 * 3 + N/16 * 4 + ...... T(N)=N/2∗1+N/4∗2+N/8∗3+N/16∗4+......
- 而 2 ∗ T ( N ) = N + N / 2 ∗ 2 + N / 4 ∗ 3 + N / 8 ∗ 4 + . . . . . . 2 * T(N) = N + N/2 * 2 + N/4 * 3 + N/8 * 4 + ...... 2∗T(N)=N+N/2∗2+N/4∗3+N/8∗4+......
- 错位相减得： 2 ∗ T ( N ) − T ( N ) = T ( N ) = N + N / 2 + N / 4 + N / 8 + N / 16 + . . . . . . 2 * T(N) - T(N) = T(N) = N + N/2 + N/4 + N/8 + N/16+ ...... 2∗T(N)−T(N)=T(N)=N+N/2+N/4+N/8+N/16+...... ，等比数列一定收敛于 O ( N ) O(N) O(N)
从上往下的时候，随着插入的节点越来越多，树越来越高，更多的节点需要调整的树高越来越高；而从下往上，需要承载的更多操作次数而调整的节点越来越少。
