十大排序之堆排序-技术圈

十大排序之堆排序（HeapSort）

4.14

简介

堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。

堆排序的时间复杂度是：O(nlogn) 空间复杂度：O(1).

说到堆排序就不得不提到完全二叉树了。什么是完全二叉树呢？

完全二叉树定义：

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

一颗普通的完全二叉树：

我们把堆又分为大根堆和小根堆，

大根堆：根结点的键值是所有堆结点键值中最大者，在堆排序算法中用于升序排列。

小根堆：根结点的键值是所有堆结点键值中最小者，在堆排序算法中用于降序排列；

4.14

图解步骤

利用堆排序的实现排序的思路也很简单：

第一步、将待排序数组构建成一个堆（大根堆或者小根堆，一般用大根堆来升序排序）；

第二步、把堆首（最大值）和堆尾互换；取出最大的元素（此时堆个数减一）；

第三步、重新构建大根堆；

第四步、重复第二步，第三步，知道堆的大小为1，完成排序。

图解：

假设待排序数组：1，5，2，12，10，9

假设我们使用大根堆来排序：

将堆首元素和堆尾元素交换：

剔除最后一个元素，然后将剩下的元素，重新构建成一个堆。

继续交换堆首元素和堆尾元素

剔除最后一个元素，然后将剩下的元素，重新构建成一个堆。

交换：

剔除，构建堆。

交换，剔除。

最终完成排序：

1 2 5 9 10 12

4.14

代码实现

package com.znzz.heapSort;

import java.util.Arrays;
public class HeapSort {    public static void main(String[] args) {        int[] arr = {2,4,1,8,20,3,6};       new HeapSort().heap_sort(arr, arr.length);        System.out.println(Arrays.toString(arr));    }
    /**     *     * @param arr  待排数组     * @param n    数组元素     * @param i    对哪个节点做heapify     */    void heapify(int arr[], int n, int i){
        if(i >= n){            return;        }           int c1 = 2 * i + 1;           int c2 = 2 * i + 2;
           int max = i;           if(c1 < n && arr[c1] > arr[max]){               max = c1;           }           if(c2 < n && arr[c2] > arr[max]){             max = c2;           }           if(max != i){               swap(arr,max ,i);               heapify(arr,n,max);           }

}
    private void swap(int[] arr, int i, int j) {        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;
    }

    void build_heap(int arr[], int n){        int last_node = n -1;        int parent = (last_node -1) /2;        int i;        for (i = parent; i >= 0; i--) {            heapify(arr,n,i);        }
    }

  void  heap_sort(int arr[], int n){        build_heap(arr,n);      for (int i = n -1; i >= 0 ; i--) {            swap(arr,i,0);            heapify(arr,i ,0);      }    }
}

小根堆排序（即降序排列）只需要把arr[c1] > arr[max] 和arr[c2] > arr[max] 中条件改为小于即可。

如果该文章对你有帮助，"再看"和"点赞"是对我最大的鼓励！

扫二维码｜关注我们

谢谢观看

把城市夜晚的喧嚣，点出来

▼