堆排序的实现_C

结合文章堆结构的实现服用更佳。

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 后，排序完成

2、代码实现

/*************************************************************************
	> File Name: 013.堆排序.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 四  5/12 14:34:50 2022
 ************************************************************************/

#include 
#include 
#include 
using namespace std;

void swap(vector<int> &arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

void heapInsert(vector<int> &arr, int ind) {
    while (arr[ind] > arr[(ind - 1) / 2]) {
        swap(arr, ind, (ind - 1) / 2);
        ind = (ind - 1) / 2;
    }
}


void heapify(vector<int> &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<int> &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<int> &arr) {
    sort(arr.begin(), arr.end());
}

vector<int> generateRandomArray(int maxSize, int maxVal) {
    vector<int> arr(rand() % (maxSize + 1));
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = (rand() % (maxVal + 1)) - (rand() % (maxVal + 1));
    }
    return arr;
}

vector<int> copyArray(vector<int> &arr) {
    vector<int> backUp(arr.size());
    for (int i = 0; i < arr.size(); i++) {
        backUp[i] = arr[i];
    }

    return backUp;
}

bool isEqual(vector<int> &arr1, vector<int> &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<int> &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<int> arr1 = generateRandomArray(maxSize, maxValue);
        vector<int> 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<int> arr = generateRandomArray(maxSize, maxValue);
    printArray(arr);
    heapSort(arr);
    printArray(arr);

    return 0;
}

3、堆排序的时间复杂度

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)