堆排序

2019-01-24 本文已影响0人 MoneyRobber

堆排序过程图示

大根堆

除了根节点以外的所有节点都要满足
A[parent(i)] >= A[i]
二叉堆是一个数组，可以被看成一个近似的完全二叉树，树上的每一个节点都对应数组中一个元素，我们假设有某一个节点的下标为i，我们很容易计算出他的父节点，左孩子，右孩子

parent[i]
return (i+1)/2-1
left[I]
return 2i+1
right[I]
return 2i+2

创建大根堆

给定一个列表array=[16,7,3,20,17,8]，对其进行堆排序，首先根据该数组元素构建一个完全二叉树
然后需要构造初始堆，则从最后一个非叶节点开始调整(假设有n个元素，最后一个非叶节点的下标为n/2)，调整过程如下：
第一步: 初始化大顶堆(从最后一个有子节点开始往上调整最大堆)
20和16交换后导致16不满足堆的性质，因此需重新调整，调整完之后就得到了初始堆

堆顶元素R[1]与最后一个元素R[n]交换，交换后堆长度减一

重新调整堆

此时3位于堆顶不满堆的性质，则需调整继续调整(从顶点开始往下调整)
重复上面的步骤

堆排序时间复杂度

创建大根堆时间复杂度

从二叉树的非叶子节点开始从右向左，从下往上调整元素，那么每一层的调整的时间为s = $2^{i-1}$ * ( k - i )，其中i表示层数，k表示总层数，k-i表示下调的深度，n表示元素个数，s表示总时间
s = $2^{k-2}$ x1 + $2^{k-3}$ x2 + $2^{k-4}$ x3 + ... + 2x(k-1)
对等式左右两边进行两次升幂操作，得出
s = n - 1 - $\log_2{n}$
由于logn是n的低阶
所有创建大根堆的时间复杂度为O(n)

重新调整堆的时间复杂度

创建大根堆/调整堆时间都会排好一个数，所以每次参与调整的元素个数都会减1，n表示元素个数，s表示总时间
s = $\log_2{n}$ + $\log_2{n-1}$ + $\log_2{n-2}$ + ... + log1
s = $\log_2{n!}$
因为 ${n/2}^{n/2}$ <= n! <= ${n}^{n}$
推导 n/4 $\log_2{n}$ <= log(n!) <= n $\log_2{n}$
所以时间复杂度为O(n $\log_2{n}$ )
总时间复杂度为n $\log_2{n}$ + n去掉常数，总时间复杂度为O(n $\log_2{n}$ )

Talk is cheap,show me the code

void swap(int* a, int* b) {
    int temp = *b;
    *b = *a;
    *a = temp;
}

//堆调整
void adjustHeap (int arr[],int start,int len) {
    while (1) {
        int leftSon  =start*2 +1;
        int rightson = start*2+2;
        
        if (leftSon > len - 1) {
            return;
        }
        int maxSonIndex = leftSon;
        if (rightson <= len -1 && arr[rightson] > arr[leftSon]) {
            maxSonIndex = rightson;
        }
        if (arr[start] < arr[maxSonIndex]) {
            swap(&arr[start], &arr[maxSonIndex]);
        } else {
            break;
        }
        start = maxSonIndex;
    }
}

//创建大根堆
void maxHeapSort (int arr[],int len) {
    int parent = len/2 - 1;
    while (parent >= 0) {
        int leftSon  =parent*2 +1;
        int rightson = parent*2+2;
        int maxSonIndex = leftSon;
        if (rightson <= len -1 && arr[rightson] > arr[leftSon]) {
            maxSonIndex = rightson;
        }
        if (arr[parent] < arr[maxSonIndex]) {
            swap(&arr[parent], &arr[maxSonIndex]);
            adjustHeap(arr, maxSonIndex,len);
        }
        parent --;
    }
}

//堆排序
void heapSort (int arr[],int len) {
    maxHeapSort (arr,len);
    for (int i = len -1; i>0; i--) {
        swap(&arr[0], &arr[i]);
        adjustHeap(arr, 0, i-1);
    }
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
        int len = (int) sizeof(arr) / sizeof(*arr);
        heapSort(arr,len);
        for (int i = 0; i < len; i++)
            printf("%d ", arr[i]);
    }
    return 0;
}

console

0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 Program ended with exit code: 0

堆排序