堆排序

2018-06-14 本文已影响0人 stoneyang94

指标

时间复杂度 O(logn)
空间复杂度O(n)

堆

是脑海中的结构

我们进行堆排序的时候，其实并不是真的要用到二叉树（完全二叉树），而知识借用这个知识来理解，可以将一个数组想象成一棵树

堆分为大根堆和小根堆

大根堆就是所有的根节点都比他的子节点都要大
小根堆就是所有的根节点都比他的子节点都要小

父子树节点关系

由于堆是完全二叉树

父i => 左子树2i+1，右子树2i+2
子树 i => 父节点（i-1）/2

构建和维护堆

heapInsert

用途
已经有堆，要加新的节点进堆
做法
向上（父）依次比对：刚进来的i位置的数与他的父节点比较，如果大于父节点就交换，然后i位置变成了他的父节点的位置，然后再比较i位置与他的父节点大小，如此类推
步骤
1. 将数组的0到1位置的数变成一个大根堆
2. 然后加入2位置的数
3. 如此类推

while (arr[index] > arr[(index - 1) / 2]) {//边界arr[o]>arr[0]不成立
    swap(arr, index, (index - 1) / 2);
    index = (index - 1) / 2;
}

heapify

用途
已经有堆，节点的值发生变化
做法
向下（子）依次比对：i位置的数与他的两个子节点中比较大的值交换，然后i也变成他的大的子节点的位置，然后再与子节点比较，如此类推，堆就调整好了。
步骤

int left = index * 2 + 1;
while (left < size) {
    int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
    largest = arr[largest] > arr[index] ? largest : index;
        if (largest == index) {
          break;
        }
        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
}

size是堆的大小，堆可能只是数组的一部分，最大是数组大小

堆排序

1.建堆
堆排序首先是把数组中的所有数，建成一个大小为n的大根堆，堆顶是所有元素中的最大值
2.换位置，缩小堆范围
把堆顶与第n-1位置的元素进行交换，剥离出整个堆结构，放在数组最后的位置

调整堆

接下来再把n-1大小的堆，从堆顶位置开始，进行大根堆的调整
再把堆顶元素与第n-2位置的元素进行交换，放在数组的最后位置，作为数组的有序部分
依次进行，当堆的大小为1的时候，整个数组就变得有序了

完整代码

public class HeapSort {

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int size = arr.length;
        swap(arr, 0, --size);
        while (size > 0) {
            heapify(arr, 0, size);
            swap(arr, 0, --size);
        }
    }

    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int size) {
        int left = index * 2 + 1;
        //size是堆的大小；堆可能只是数组的一部分，最大是数组大小
        while (left < size) {
            //左 右  孩子先比出来一个大的
            //left + 1 < size  右孩子不越界
            int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
            //父节点加入 比较
            largest = arr[largest] >  arr[index] ? largest : index;
            if (largest == index) {//是自己，不动
                break;
            }
            swap(arr, largest, index);
            index = largest;//父节点下沉
            left = index * 2 + 1;//left下沉
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = new int[] { 3, 5, 4, 2, 6, 7, 1, 9, 8 };
        heapSort(arr);
        printArray(arr);
    }
}

输出

排序后

堆排序

指标

堆