【算法】核心排序算法之堆排序原理及实战

1.什么是堆排序

• 指利用堆这种数据结构所设计的一种排序算法，将二叉堆的数据进行排序，构建一个有序的序列

• 排序过程中，只需要个【别临时存储】空间，所以堆排序是原地排序算法，空间复杂度为O(1)

  • 本身大顶堆和小顶堆里面的元素是无序的，只是有一定的规则在里面
  • 大顶堆，每个父节点的值都大于或等于其子节点的值，即根节点的值最大
  • 小顶堆，每个父节点的值都小于或等于其子节点的值，即根节点的值最小

• 过程分为建堆和排序两大步骤

  • 【建堆】过程的时间复杂度为O(n)，排序过程的时间复杂度为O(nlogn)，所以 堆排序整体的时间复杂度为O(nlogn）

  • 【堆排序】不是稳定的算法，在排序的过程中，将堆最后一个节点跟堆顶节点互换，可能改变值相同数据的原始相对顺序

• 流程

  • 把无序数组构建成二叉堆，建堆结束后，整个序列的最大值就是堆顶的根节点
  • 将其与末尾元素进行交换(删除操作), 堆顶a[1]与最后一个元素a[n]交换，最大元素放到下标为n的位置, 末尾就为最大值
  • 然后将剩余n-1个元素重新构造成一个堆（堆化操作），这样会得到n个元素的次小值
  • 反复执行上述步骤，得到一个有序的数组

2.编码实现

• 无序堆构建成二叉堆
• 利用二叉堆特性：数组索引一半后的都是叶子节点，不需要做下沉比较；一半前都是非叶子节点，才需要做下沉比较

/**
 * 堆排序
 */
public class HeapSort {

    public static void sort(int[] arr){
        //1.构建堆，数组下标0不存储数据
        int[] heap = new int[arr.length+1];

        //2.根据待排序数组，构建一个无序堆
        System.arraycopy(arr,0,heap,1,arr.length);

        //3.对堆中的元素做下沉操作，从长度一半开始，一半前都是非叶子节点，才需要做
        //二叉堆特性：数组索引一半后的都是叶子节点，不需要做下沉，一半前都是非叶子节点，才需要做
        for (int i = (heap.length)/2; i > 0; i--) {
            down(heap,i,heap.length - i);
        }

        //4.堆排序，把堆顶元素和数组最后一个索引元素交换；然后再堆化，然后堆顶又是最大元素，再和数组倒数第二索引处交换；持续进行直到最后
        //类似删除操作，只需要下沉操作重新堆化即可
        //记录未排序的元素中最大的索引
        int maxUnSortIndex = heap.length - 1;
        //通过循环，交换堆顶元素和最大未排序元素的下标
        while (maxUnSortIndex != 1) {
            //交换元素
            swap(heap, 1, maxUnSortIndex);
            //排序后最大元素所在的索引，不要参与堆的下沉，所以 递减1
            maxUnSortIndex--;

            //继续对堆顶处的元素进行下沉调整
            down(heap, 1, maxUnSortIndex);
        }

        //把heap中的数据复制到原数组source中
        System.arraycopy(heap, 1, arr, 0, arr.length);
    }

    /**
     * 使用下沉操作，堆顶和最后一个元素交换后，重新堆化
     * 不断比较 节点 arr[k]和对应 左节点arr[2*k] 和 右节点arr[2*k+1]的大小，如果当前结点小，则需要交换位置
     * 直到找到 最后一个索引节点比较完成  则结束
     * <p>
     * 数组中下标为 k 的节点
     * 左子节点下标为 2*k 的节点
     * 右子节点就是下标 为 2*k+1 的节点
     * 父节点就是下标为 k/2 取整的节点
     * @param heap
     * @param i
     * @param i1
     */
    private static void down(int[] heap, int k, int range) {
        // 最后一个节点的下标是range，即元素总个数
        while (2 * k <= range) {
            //记录当前节点的左右子节点，较大的节点
            int maxIndex;
            if (2 * k + 1 <= range) {
                if (rightBig(heap, 2 * k, 2 * k + 1)) {
                    maxIndex = 2 * k + 1;
                } else {
                    maxIndex = 2 * k;
                }
            } else {
                maxIndex = 2 * k;
            }
            //比较当前节点和较大接的值，如果当前节点大则结束
            if (heap[k] > heap[maxIndex]) {
                break;
            } else {
                //否则往下一层比较，当前节点的k变为子节点中较大的值
                swap(heap, k, maxIndex);
                k = maxIndex;
            }
        }
    }

    /**
     * 比较大小,item[left] 元素是否小于 item[right]的元素
     */
    private static boolean rightBig(int[] heap, int left, int right) {
        return heap[left] < heap[right];
    }

    /**
     * 交互堆中两个元素的位置
     */
    private static void swap(int[] heap, int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public static void main(String[] args) {
        //待排序数组
        int[] arr = {923,23,12,4,9932,11,34,49,123,222,880};
        System.out.println("排序前:"+Arrays.toString(arr));
        //堆排序
        HeapSort.sort(arr);
        //输出排序后数组中的元素
        System.out.println("堆排序:"+ Arrays.toString(arr));

    }
}