堆排序数据结构 [ 数据结构- C语言 ] 堆排序的优化算法

2023-04-03 271

到这里的老铁想必对堆和堆排序有了简单的了解，那么下面我们对之前所写的堆排序进行优化~ Let's go!

1.堆排序优化算法

要堆堆排序算法进行优化我们首先要明白之前我们所写的堆排序有什么可以优化的地方或者说哪里写的不够好？

void HeapSort(int* a, int size)

    {
        //小堆
        HP hp;
        HeapInit(&hp);
        //O(N*logN)
        for (int i = 0; i < size; ++i)
        {
            HeapPush(&hp, a[i]);
        }
        size_t j = 0;
        //O(N*logN)
        while (!HeapEmpty(&hp))
        {
            a[j] = HeapTop(&hp);
            j++;
            HeapPop(&hp);
        }
        HeapDestory(&hp);

这是我们之前写的堆排序，我们能够发现，如果我们要实现堆排序的前提是我们要写一堆。那这想想都很麻烦堆排序数据结构 [ 数据结构- C语言 ] 堆排序的优化算法，我们都知道排序算法那么多，我们何必选择这种算法呢？

其次我们再来分析一下建堆的时间复杂度：

1.1建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明 ( 时间复杂度本来看的就是近似值，多几个节点不影响最终结果) ：

因为我们要进行优化建堆，在这里分析一下向下调整建堆和向上调整建堆的时间复杂度。

1.1.1 向下调整建堆：O(N)

过程分析如下：

因此向下调整建堆的时间复杂度为O(n)。

1.1.2向上调整建堆：O(N*logN)

过程分析如下：

因此向上调整建堆的时间复杂度为O(N*logN)。

1.2堆排序的复杂度 1.2.1原堆排序的时间复杂度

我们来看原堆排序的代码中使用了向上调整建堆，因此原排序的时间复杂度为O(N*logN)

1.2.2原堆排序的空间复杂度

因为我们要建立一个堆，我们实现堆是使用数组实现，因此假设有要排序元素个数为N，空间复杂度为O(N)。

1.3堆排序优化算法的复杂度

堆排序的优化算法主要是对空间复杂度进行优化。由于我们之前建堆都要开辟新的数组，因此我们是否可以在原数组上直接建堆，无需再开辟新的空间建堆呢？答案当然是可以的。以下使用的正是在原数组上直接建堆。

1.3.1 堆排序优化算法的时间复杂度

由于使用堆排序，我们要利用堆的特点，每次取堆顶的元素。因此每次取完数据后都要对堆进行调整。再次我们有向上调整和向下调整两种算法堆排序数据结构堆排序数据结构，我们需要对这两种算法分别分析选出一个更优的调整算法。

1.3.1.1向上调整--建堆 O(N*logN)

由于我们是对原数组之间建堆，因此我们如果要是用向上调整，在刚刚我们所分析的建堆的时间复杂度是O(N*logN)。

实现代码：

向上调整--建堆 O(N*logN)

        int n = 1;
        while (n= 0; --i)
        {
            AdjustDown(a, size, i);

1.3.2堆排序优化算法的空间复杂度

由于我们是在原数组上进行遍历因此没有开辟新的空间。因此空间复杂度为O(1)。

1.4堆排序实现逻辑

如果升序建小堆，最小的数已经在堆顶,剩下的数关系打乱,需要重新建堆,建堆最好也要O(N)，再选出次小的,不断建堆选数,如果这样,还不如直接遍历选数！！因此升序要建大堆！！利用删除的思想来玩。

过程：

1、把第一个数和最后一个数交换，由于是大堆，堆顶的数据一定是最大的数据。和最后一个数交换后，最大的数据就到了最后一个。

2、再对前N-1个数进行向下调整建立新的大堆，次大的数放在了堆顶，我们再让堆顶的元素和最后一个元素交换（这个最后一个不是数组的最后一个，是堆中的最后一个，使用end进行控制）。

3、当end到0的时候，说明已经排完了。

//升序要建大堆,

        size_t end = size - 1;
        while (end > 0)
        {
            Swap(&a[0], &a[end]);
            AdjustDown(a, end, 0);
            end--;

1.5堆排序实现代码

void HeapSort(int* a, int size)

    {
        //向下调整--建堆  O(N)
        for (int i = (size - 1 - 1) / 2; i >= 0; --i)
        {
            AdjustDown(a, size, i);
        }
        //如果升序建小堆,最小的数已经在堆顶,剩下的数关系打乱,需要重新建堆,建堆最好也要O(N)
        //再选出次小的,不断建堆选数,如果这样,还不如直接遍历选数！！
        //升序要建大堆,
        size_t end = size - 1;
        while (end > 0)
        {
            Swap(&a[0], &a[end]);
            AdjustDown(a, end, 0);
            end--;
        }
    }
    int main()
    {
        int a[] = { 4,2,1,3,5,7,9,8,6};
        HeapSort(a,sizeof(a)/sizeof(int));
        for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
        {
            printf("%d ", a[i]);
        }
      
        return 0;

1.6演示结果

（本篇完）

文章来源:https://blog.csdn.net/qq_58325487/article/details/124068253

风也温柔