堆排序与快速排序的奥妙

清疚 2022-09-10 04:11 130阅读 0赞

### 堆排序 ###

堆排序的核心思想是构建大（小）顶堆，然后与末尾元素交换值，并且，堆大小减一；

这里面的重点是如何构建大（小）顶堆，这是最核心的部分，其实总结起来也很简单，首先明白大（小）顶堆的定义，每个子树的根节点，都必须大于（小于）等于子节点，所以大顶堆的根节点，就是整个堆的最大值，小顶堆的根节点就是整个堆的最小值；

其构建的核心步骤是，从最末尾非叶子节点开始构建堆，为什么要从最末尾非叶子节点开始，因为如果直接从其他节点开始，构建的话，无法保证所有的子树都符合堆的定义，就会有遗漏，交换值之后的子节点也只会比较交换后的那颗子树，无法保证所有的子树。

**根据完全二叉树的定义，数组下标n为根节点对应的左右子树分别为，2n+1,2n+2**

**最末尾的非叶子节点的根节点为length/2-1**

知道了这两个，就能写出算法代码

第一步，从最末尾非叶子节点开始构建堆，然后依次递减，知道根节点；

第二步，把根节点与堆末尾值交换，然后再从根节点开始构建；因为只改变了根节点的值，其他子树不受影响，只用从根开始构建就可以，构建算法会把交换过值的所有子树都构建好。依次直到只剩下跟节点，排序结束

代码如下：

/**
         * 选择排序
         * 堆排序
         * 不稳定排序，最坏时间复杂度nlogn，平均时间复杂度nlogn，最好时间复杂度nlogn
         *
         * @param arr
         */
        public static void heapSort(int[] arr) {
            //1.构建大顶堆
            for (int i = arr.length / 2 - 1; i >= 0; i--) {
                //从第一个非叶子结点从下至上，从右至左调整结构
                adjustHeap(arr, i, arr.length);
            }
            //2.调整堆结构+交换堆顶元素与末尾元素
            for (int i = arr.length-1; i > 0; i--) {
                // 将堆顶元素与末尾元素进行交换
                arr[i] = arr[i] ^ arr[0];
                arr[0] = arr[i] ^ arr[0];
                arr[i] = arr[i] ^ arr[0];
                // 重新对关联根节点的堆进行调整
                adjustHeap(arr, 0, i);
            }
        }
    
        private static void adjustHeap(int[] arr, int i, int length) {
            // 挖坑填值法
            //先取出当前元素i
            int temp = arr[i];
            //从i结点的左子结点开始，也就是2i+1处开始
            for (int j = 2 * i + 1; j < length; j = 2 * j + 1) {
                //如果左子结点小于右子结点，k指向右子结点
                if (j + 1 < length && arr[j + 1] > arr[j]) {
                    j++;
                }
                if (arr[j] > temp) {
                    //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                    arr[i] = arr[j];
                    i = j;
                }else{
                    break;
                }
            }
            //将temp值放到最终的位置
            arr[i] = temp;
        }

### 快速排序 ###

快速排序的核心思想是找出一个目标值的位置，一个递归找出一个目标值的位置，直到区间等于0

直接上代码

/**
         * 交换排序
         * 快速排序
         * 号称是最快的排序，元素越多，排序效率越高
         * 最坏时间复杂度O(n^2)，平均时间复杂度O(nlogn)，最好时间复杂度(nlogn)
         */
        public static void quickSort(int[] arr, int start, int end) {
            // 挖坑填值法
            // 递归出口
            if (start >= end) {
                return;
            }
            int left = start,right= end;
            // 此处采用第一个元素当做目标值，优化可以采用随机值
            int target = arr[left];
            while (left < right) {
                // 要先遍历右边，左边刚好存了一个坑位
                while (left < right && arr[right] >= target) {
                    right--;
                }
                arr[left] = arr[right];
                // 再来遍历左边，右边的坑位剩余下来
                while (left < right && arr[left] <= target) {
                    left++;
                }
                arr[right] = arr[left];
            }
            // 确定目标值位置
            arr[right] = target;
            // 遍历左边区间
            quickSort(arr, start, right - 1);
            // 遍历右边区间
            quickSort(arr, right + 1, end);
        }