转载

堆排序

堆排序

知识点

堆分为大顶堆,小顶堆。

大顶堆的定义:每个节点的值都不大于其父节点的值

小顶堆的定义:每个节点的值都不小于其父节点的值

左边大顶堆,右边小顶堆

定理一: 假设二叉数的父节点索引值为 k k , 则其左节点索引值为 2 k + 1 2k+1 ,右节点索引值为 2 k + 2 2k+2 (证明见参考文章)

定理二:如果树有 n n 个元素,索引值从0开始,那么二叉树最后非叶子节点索引值为 n 2 ? 1 \frac {n}{2}-1

最后的叶节点 n ? 1 n-1 的父节点是最后的非叶子节点, n n 为奇数的时候,最后非叶子节点索引值

n ? 2 2 \frac{n-2}{2} ,n为偶数时,最后非叶子节点索引值 n ? 3 2 \frac{n-3}{2} .所以可以归纳为 ? n 2 ? ? 1 \lfloor \frac {n}{2} \rfloor -1

堆排序的整个流程分一下几步

  • 为整个数组构建一个堆

    • 找到最后一个非叶子节点 (索引值为 ? n 2 ? ? 1 \lfloor \frac {n}{2} \rfloor -1 )

    • 从最后一个非叶子节点开始,至根节点, 进行下沉操作

      下沉操作,简单得理解就是小的数沉到树的底下去(相对大顶堆而言)

      如下图所示是一次下沉操作

  • 将树中最后一个叶节点与根节点进行交换(已经找到了数组最大数)

  • 继续调整余下的 n ? 1 n-1 个元素为大顶堆, 其实操作就是下沉新的根节点

  • 循环执行第二步和第三步直到,树中仅剩一个元素,这时已经排好序.

时间复杂度的证明:每次调整堆的时候,时间复杂度是O(log(n)),所以堆排序的复杂度 O(nlog(n))

堆排序是一种选择排序,时间复杂度是O(n*log(n)), 也是一种不稳定的排序方法

JAVA代码:

public class Main {
    //下沉操作
    private void sink(int []arr, int k, int len){
        int j = 0; int temp = 0;
        while(2*k+1 <= len) {
            j = 2*k + 1;
            if(j < len && arr[j] < arr[j+1]) j++;
            if(arr[k] < arr[j]) {
                temp = arr[k];
                arr[k] = arr[j];
                arr[j] = temp;
                k = j
            }else break;
        }
    }
    //构建堆
    private void createHeap(int []arr) {
        //最后一个非叶子节点
        int start = arr.length/2 - 1;
        for(int i = start; i >= 0; i--){
            sink(arr, i, arr.length-1);
        }
    }

    public void  heapSort(int[]arr) {
        //构建堆
        createHeap(arr);
        int len = arr.length-1;
        int temp = 0;
        while(len > 0) {
            //交换位置根节点和最大节点的位置
            temp = arr[0];
            arr[0] = arr[len];
            arr[len] = temp;
            sink(arr, 0, --len);
        }
    }
    public static void main(String args[]) {
        int []arr = new int[]{3, 1, 2, 5, 4, 0};
        new Main().heapSort(arr);
        for(int i = 0; i < arr.length; i++) System.out.println(arr[i] + " ");
    }
}
正文到此结束
本文目录