xietao3

探索之旅,学习之路

你好,我是谢涛!欢迎来到我的个人主页.
90后代码搬运工,目前就职于上海天天果园,任职iOS高级开发工程师。


算法-堆排序

赶紧让你的大脑来一套广播体操

前言

慢慢的,我们脱离了”小学生“算法,开始接触一些需要绕圈子的思路,赶紧沉浸入堆排序的头脑风暴当中吧。

简介

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

核心思想

  1. 先将初始的R[0…n-1]建立成最大堆,此时是无序堆,而堆顶是最大元素。
  2. 再将堆顶R[0]和无序区的最后一个记录R[n-1]交换,由此得到新的无序区R[0…n-2]和有序区R[n-1],且满足R[0…n-2].keys ≤ R[n-1].key
  3. 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。
  4. 直到无序区只有一个元素为止。

示例

建立最大堆

  1. 这里有一个数组{100,5,3,11,33,6,8,7},首先我们将数组我们将数组从上至下按顺序排列,转换成二叉树:一个无序堆。 堆排序-原始数组.png
  2. 每一个三角关系都是一个堆,上面是父节点,下面两个分叉是子节点,两个子节点俗称左孩子、右孩子;如果一个孩子都没有的,不形成堆,只能做别人的孩子(啧啧啧) 堆排序-无序堆.png

  3. 转换成无序对之后,我们要努力让这个无序堆变成最大堆或是最小堆,本文是建最大堆—即每个堆里,都实现父节点的值都大于任何一个子节点的值。要实现最大堆并不简单。 堆排序-4个堆.png
  4. 从最后一个堆开始,即左下角那个没有右孩子的那个堆开始;首先对比左右孩子,由于这货没有右孩子(真是惨),所以只能用左孩子了,左孩子的值比父节点的值小所以不需要交换。如果发生交换,要检测子节点是否为其他堆的父节点,如果是,递归进行同样的操作。

  5. 第二次对比红色三角形内的堆,取较大的子节点,右孩子8胜出,和父节点比较,右孩子8大于父节点3,升级做爸爸,与3交换位置,3的位置没有子节点,这个堆建成最大堆。 堆排序-第二次排序.png
  6. 对黄色三角形内堆进行排序,过程和上面一样,最终是右孩子33占领爸爸宝座,被交换的右孩子下面也没有子节点,所以直接结束对比。 堆排序-第三次排序.png

  7. 最顶部绿色的堆,堆顶100比左右孩子都大,所以不用交换,至此最大堆建成。

扩大有序区

  1. 下面进入第二阶段,扩大有序区,首先将堆顶100交换至最底部7的位置,7升至堆顶(终于做爸爸了),100所在的底部位置即为有序区,有序区不参与之后的任何对比。 堆排序-有序区1.png

  2. 在7升至顶部之后,对顶部重新做最大堆调整,左孩子33代替7的位置。 堆排序-第四次排序.png

  3. 在7被交换下来后,下面还有子节点,所以需要继续与子节点对比,左孩子11比7大,所以11与7交换位置,交换位置后7下面为有序区,不参与对比,所以本轮结束,无序区再次形成一个最大堆。 堆排序-第五次排序.png

  4. 将最大堆堆顶33交换至堆末尾,扩大有序区; 堆排序-第六次排序.png

  5. 不断建立最大堆,并且扩大有序区,最终全部有序。 堆排序-全部有序.png

C语言代码

#pragma mark - 堆排序
void printfHeap (int arr[], int len) {
    int line = 0;
    for (int i = 0; i<len; i++) {
        printf("%d\t",arr[i]);
        if (i==line) {
            printf("\n");
            line = line==0?2:line+line*2;
        }
    }
    printf("\n");
}

void adjustHeap (int arr[], int len, int parentIndex) {
    
    int targetChildIndex = -1;
    
    // 左右孩子的索引
    int leftChildIndex  = parentIndex*2+1;
    int rightChildIndex = parentIndex*2+2;
    
//    printf("未完成调整堆 %d\n",parentIndex);
//    printfHeap(arr,len);
    
    // 找出最大的孩子 先左后右
    if (leftChildIndex > len-1) {
        // 没有左右孩子 退出循环
        return;
    }else if (rightChildIndex > len-1) {
        // 只有左孩子 直接用左孩子
        targetChildIndex = leftChildIndex;
    }else{
        // 左右孩子都有 取出大的那个孩子
        targetChildIndex = arr[leftChildIndex]>arr[rightChildIndex]?leftChildIndex:rightChildIndex;
    }
    
    // 如果孩子大于父节点 则互相交换
    if (arr[targetChildIndex] > arr[parentIndex]) {
        int temp = arr[targetChildIndex];
        arr[targetChildIndex] = arr[parentIndex];
        arr[parentIndex] = temp;
        
//        printf("完成调整堆\n");
//        printfHeap(arr,len);
        adjustHeap(arr, len, targetChildIndex);
    }
}

void heapSort (int arr[], int len) {
    if (len < 2) {
        return;
    }
    printf("原始数据\n");
    printfArr(arr, len);

    // 初始化最大堆
    for (int i = (len-1)/2; i >= 0; i--) {
        adjustHeap(arr, len, i);
    }
    printf("初始化完成\n");
    printfHeap(arr,len);
    

    for (int i = len - 1; i > 0; --i) {
        if (arr[0] > arr[i]) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
        }
        printf("交换后\n");
        printfHeap(arr, len);

        adjustHeap(arr, i - 1, 0);
        printf("调整后\n");
        printfHeap(arr, len);
    }
    printf("最终堆\n");
    printfHeap(arr,len);
    
    printfArr(arr, len);
}

时间复杂度

堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的,平均时间复杂度为:O(N*logN)。

总结

是不是看着就觉得复杂呢,个人觉得有时候直接看代码加画图能更快地了解算法的思路。

最近的文章

算法-归并排序

阅读量真是少,又不想投稿,怎么办前言归并排序思路简单,速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。核心思想比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1;否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直到其中一个有序表取完,然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现,先把待排序...…

继续阅读
更早的文章

算法-快速排序

这个排序算法的命名有点随意啊,这种态度怎么行前言这个算法感觉脱离了简单算法的范畴,脑袋稍微要转那么一点儿弯,排序代码倒是多了不少。核心思想通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。示例 首先,我们枪打出头鸟,把第一个数10给拎出来,留下一个坑位(坑位很重要*),做参照物:基数。 有了基数之后,我们建立左右指针各...…

继续阅读