堆排序#

算法思维#

堆排序也是一种选择排序，每次选出无序序列中一个最大或最小的元素并放到有序序列中去
因为堆排序是从后往前放的，所以升序要用大根堆，降序要用小根堆
堆排序在最坏的情况下时间复杂度也是 $O(n \log n)$ ，并且只需要一个辅助空间

算法设计#

创建变量 i ，表示未排序序列的末尾
从未排序序列末尾开始，把未排序序列视作完全二叉树，从右往左，从下往上遍历每个非叶子节点，并对结构混乱（节点与其孩子比较，不是最大或最小）的结点进行调整（与最大或最小的孩子进行交换）
然后把推顶的元素与无序序列最后一个元素交换
未排序序列长度 i 减 1，重复2，直到整个序列有序

算法实现#

1
// 堆排序
2
/*
3
mode: 非0：升序， 0：降序
4
*/
5
void sort_heapSort(int *arr, int len, int mode)
6
{
7
    int i = len - 1;
8
    int heap, judge_index;
9

10
    while(i > 0)
11
    {
12
        // 从最后一个结点开始
13
        for(int j = i; j > 0; j -=2)
14
        {
15
            // 找到双亲
16
            heap = (j - 1) / 2;
17

18
            // 找到要到堆顶的元素
19
            if( (2*heap)+2 <= i )
20
            {
21
                // 如果有两个孩子节点
22
                // 这里不能确定j是第一个孩子还是第二个孩子，所以直接用 heap 来当参数
23
                judge_index = sort_judgeWithMode(arr[2*heap + 1], arr[2*heap + 2], mode) ? 2*heap + 2 : 2*heap + 1;
24
                judge_index = sort_judgeWithMode(arr[heap], arr[judge_index], mode)? judge_index : heap;
25
            }
26
            else
27
            {
28
                // 因为堆是完全二叉树，所以只有一个孩子必是左孩子
29
                judge_index = sort_judgeWithMode(arr[heap], arr[j], mode)? j: heap;
30
            }
31
            utils_exchange(arr, heap, judge_index);
32
        }
33

34
        // 堆顶元素放到未排序元素的最后
35
        utils_exchange(arr, i, 0);
36

37
        // 结点个数减1
38
        i--;
39
    }
40
}

运算结果#

测试代码

1
#define N 8
2

3
int main()
4
{
5
    int arr[N] = {49,38,65,97,76,13,27,49};
6

7
    printf("升序排列结果:\n");
8
    sort_heapSort(arr, N, 1);
9
    utils_print_arr(arr, N, "%d ");
10

11
    printf("\n\n降序排列结果:\n");
12
    sort_heapSort(arr, N, 0);
13
    utils_print_arr(arr, N, "%d ");
14
    return 0;
15
}

运算结果

原文链接：CSDN