排序算法 --- 堆排序

1. 堆排序介绍:

  • 堆排序是利用“堆”这种数据结构设计的,也是一种选择排序,时间复杂度为O(nlogn),属于不稳定排序。
  • 堆,其实就是具有某些特征的完全二叉树。特点就是:每个节点的值都大于其左右孩子节点的值,这样的叫大顶堆;反之叫小顶堆。

大顶堆

如果我们以图中黑色数字作为索引将值依次存到数组里,那么数组就是:

50, 45, 40, 20, 26, 35, 30, 10, 15

可以发现,arr[i] > arr[2*i + 1]arr[i] > arr[2*i + 2]

在用堆排序的时候,如果要升序,那就使用大顶堆,如果要降序,那就使用小顶堆。··

2. 排序思想:

  • 将待排序列构造成一个最大堆。不需要真正地构建二叉树,之前说了二叉树的顺序存储,这里就派上用场了;
  • 此时,整个序列的最大值就是堆顶的根节点;
  • 将堆顶元素与末尾元素进行交换,此时末尾元素就是最大值;
  • 将剩余的(n - 1)个元素,重新构造成一个堆,如此反复执行……

3. 代码实现:

首先写个方法,将树调整成大顶堆,具体步骤看代码注释:

/**
* 把以index为父节点的子树调整成大顶堆
* @param arr 数组
* @param index 非叶子节点的索引
* @param length 对多少个元素进行调整
*/
private static void buildHeap(int[] arr, int index, int length) {
    // 保存index对应的值,其实就是要调整子树的父节点的值
    int temp = arr[index];
    // 开始调整,i就是index节点的左子节点
    for (int i=(index * 2 + 1); i<length; i = (i * 2 + 1)) {
        // 如果左子节点小于右子节点,那就让i指到右子节点
        if (i + 1 < length && arr[i] < arr[i+1]) {
            i++;
        }
        // 经过上面操作,arr[i]就是最大的子节点
        if (arr[i] > temp) {
            // 如果最大子节点的值比父节点更大,就把这个子节点的值赋给父节点
            arr[index] = arr[i];
            // 然后就以刚才那个最大子节点为父节点,再循环进行调整
            index = i;
        } else {
            break;
        }
    }
    // 循环结束,就是调整结束,要把刚才保存的父节点的值赋给当前节点,这才完成了父节点与子节点值的交换
    arr[index] = temp;
}

然后就可以写排序方法了,首先调用一次调整大顶堆的方法,然后将堆顶元素放到最后,此时最后那个元素就是最大的了,然后再进行调整,就可以少调整一个数了,具体代码如下:

public static void sort(int[] arr) {
    // 遍历数组,找到非叶子节点,对以非叶子节点为父节点的子树进行调整
    // (arr.length / 2 - 1)就可以找到完全二叉树的最后一个非叶子节点
    for(int i=(arr.length / 2 - 1); i>=0; i--) {
        buildHeap(arr, i, arr.length);
    }
    // 调整成大顶堆后,让堆顶元素与末尾元素进行交换,此时末尾元素就是最大值
    int temp;
    for(int j=arr.length-1; j>0; j--) {
        temp = arr[j];
        arr[j] = arr[0];
        arr[0] = temp;
        // 交换完后,将剩余的(n-1)个元素再调整成大顶堆
        buildHeap(arr, 0, j);
    }
}
举报

扫码关注云+社区

领取腾讯云代金券