排序之堆排序

堆排序

• 原理：
  • 堆排序也是选择出无序区间的最大值/最小值，将其放在无序区间的后面
  • 但是是通过遍历获取最大值/最小值，是通过建堆的方式来获取无序区间中的最大值/最小值
  • 将堆顶元素和最后一个元素交换，然后对无序区间进行向下调整
  • 重复交换直至排序结束
• 排升序需要建大堆
• 排降序需要建小堆
• 插入排序是一个不稳定的排序

实现方式

1.排升序，建大堆

        public static void heapSort(int[] array) {
                //将数组建成大堆
                heapify(array);
                for(int i = 0; i < array.length - 1; i++) {
                        //交换前
                        //无序区间[0, array.length - i);
                        //有序区间[array.length - i, array.length);

                        swap(array, 0, array.length - 1 - i);

                        //交换后
                        //无序区间[0, array.length - i - 1)
                        //有序区间[array.length - i - 1, array.length)
                        //无序区间的长度 array.length - i - 1
                        siftDown(array, array.length - i - 1, 0);
                }
        }

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

        private static void heapify(int[] array) {
                //array.length - 1 是堆的最后一个结点的下标，
                //则最后一个非叶子结点的下标就是 (array.length - 1 - 1) >>> 1
                for(int i = (array.length - 1 - 1) >>> 1; i >= 0; i--) {
                        siftDown(array, array.length, i);
                }
        }

        private static void siftDown(int[] array, int length, int index) {
                int left = (index << 1) + 1;

                while(left < length) {
                        int right = (index << 1) + 2;
                        int max = left;

                        //右结点存在且值比左节点的值大时，值最大的结点才是右结点
                        if(right < length && array[right] > array[max]) {
                                max = right;
                        }

                        //如果需要调整的结点的值比子结点中值最大的结点的值都大时，向下调整结束
                        if(array[index] >= array[max]) {
                                break;
                        }

                        swap(array, index, max);

                        index = max;
                        left = (index << 1) + 1;
                }
        }

2.排降序，建小堆

        public static void heapSort(int[] array) {
                //将数组建成小堆
                heapify(array);
                for(int i = 0; i < array.length - 1; i++) {
                        //交换前
                        //无序区间[0, array.length - i);
                        //有序区间[array.length - i, array.length);

                        swap(array, 0, array.length - 1 - i);

                        //交换后
                        //无序区间[0, array.length - i - 1)
                        //有序区间[array.length - i - 1, array.length)
                        //无序区间的长度 array.length - i - 1
                        siftDown(array, array.length - i - 1, 0);
                }
        }

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

        private static void heapify(int[] array) {
                //array.length - 1 是堆的最后一个结点的下标，
                //则最后一个非叶子结点的下标就是 (array.length - 1 - 1) >>> 1
                for(int i = (array.length - 1 - 1) >>> 1; i >= 0; i--) {
                        siftDown(array, array.length, i);
                }
        }

        private static void siftDown(int[] array, int length, int index) {
                int left = (index << 1) + 1;

                while(left < length) {
                        int right = (index << 1) + 2;
                        int min = left;

                        if(right < length && array[right] < array[min]) {
                                min = right;
                        }

                        if(array[index] <= array[min]) {
                                break;
                        }

                        swap(array, index, min);

                        index = min;
                        left = (index << 1) + 1;
                }
        }

性能分析

• 时间复杂度：O(N*logN)
• 空间复杂度：O(1)
• 稳定性：不稳定

排序之堆排序

原文：https://blog.51cto.com/14233687/2472009