排序算法专题

1.快速排序

@Test
public void test() {
    int[] nums = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
    quickSort(nums, 0, nums.length - 1);
    for (int num : nums) System.out.println(num);
}


private void quickSort(int[] nums, int low, int high) {
    /*
    快速排序:原理每一轮选一个基准元素pivot
    利用两个指针分别将<=pivot和>pivot的元素分别放在pivot的左边与右边
    最后递归调用原函数直至区间长度缩小为1
     */
    if (low >= high) return; //  区间长度<=1直接结束
    int l = low, r = high;  // 左右指针
    int pivot = nums[low];  // 以nums[low]为基准
    while (l < r) {
        // r指针先行可以确保最后停留的位置必定是<=基准，再不济就移动到pivot位置上；而l指针先行会找到首个大于基准的位置
        // 例如在[1,2,3,4,5]这种情况会停在2处，此时r指针想找小于等于基准的元素但是也只能移动到2处结束
        // 循环退出->将1与2的位置交换，此时有[2,1,3,4,5] 这个就违反了快排的宗旨了，再递归左右子区间就出错。
        // 归根到底右指针先行，是为了避免左指针主动时导致停留在比基准大的地方，与基准交换后直接导致基准左边有元素大于基准。
        // 右指针先行会主动占据<=基准的元素，再不济就是移动到基准位置，这两种情况符合快排目的.
        while (l < r && nums[r] > pivot) r--;  // r停留在首个<=基准的元素处
        while (l < r && nums[l] <= pivot) l++;  // l停留在首个>基准的元素处
        if (l < r) {    // 交换nums[l]与nums[r]
            // nums[l] ^= nums[r];
            // nums[r] ^= nums[l];
            // nums[l] ^= nums[r];
            int t = nums[l];
            nums[l] = nums[r];
            nums[r] = t;
        }
    }
    // l == r 将nums[low]与nums[l]交换
    nums[low] = nums[l];
    nums[l] = pivot;
    // 递归排序左右子区间
    quickSort(nums, low, r - 1);
    quickSort(nums, r + 1, high);
}

2.归并排序

public class Merge_Sort {
    @Test
    public void test() {
        int[] nums = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
        mergeSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    /*
    归并排序:分区间排序+合并两个有序数组
     */
    private void mergeSort(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        int[] tmp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1, tmp);
    }

    /*
    重载的带区间端点的归并排序方法
     */
    private void mergeSort(int[] nums, int l, int r, int[] tmp) {
        if (l == r) return;
        int mid = l + (r - l) / 2;
        mergeSort(nums, l, mid, tmp);   // 递归排序[l,mid]
        mergeSort(nums, mid + 1, r, tmp);   // 递归排序[mid+1,r]
        // 合并两个有序数组[l,mid]和[mid+1,r]
        merge(nums, l, mid, r, tmp);
    }

    /*
    合并nums两个区间内的两个有序数组
     */
    private void merge(int[] nums, int l, int mid, int r, int[] tmp) {
        int idx = l;    // 合并后的指针
        int i = l, j = mid + 1; // 左右指针
        // 将[l,mid]和[mid+1,r]元素按照大小拷贝到tmp对应位置中
        while (i <= mid && j <= r) {    // 等于的时候还没赋值!
            if (nums[i] <= nums[j]) {
                tmp[idx++] = nums[i++];
            } else {
                tmp[idx++] = nums[j++];
            }
        }
        // 走完还没有走完的一边
        while (i <= mid) tmp[idx++] = nums[i++];
        while (j <= r) tmp[idx++] = nums[j++];
        // 将临时数组拷贝至nums对应位置
        System.arraycopy(tmp, l, nums, l, r - l + 1);
    }

3.堆排序

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；

或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

参考资料：堆排序（超详细图解 java版）

主要步骤：

1.将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆（升序一般用大顶堆）

2.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端

3.重新调整结构,使其满足堆定义，然后继续交换堆顶元素与当前末尾元素

4.反复执行调整+交换步骤，直到整个序列有序

public class Heap {
    @Test
    public void test() {
        int[] nums = {4, 5, 6, 3, 2, 1};
        HeapSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    /*
     堆排序主方法:
     一般来说升序排列就构造大顶堆(堆顶最大&&当前节点比左右子节点都大->但是左右节点的大小没有要求)
     堆的索引统一从0开始,因此总的范围在[0,len-1]
     */
    private void HeapSort(int[] nums) {
        int len = nums.length;
        // 叶子节点肯定堆的最底层,不用下沉
        // 这里用了一个结论:只下沉非叶子节点间接也上浮了所有叶子节 因此只下沉前半部分即可保证堆有序
        for (int i = len / 2 - 1; i >= 0; i--) {    // len÷2-1是首个非叶子结点索引
            sink(nums, i, len - 1);
        }
        // 下沉完后整个堆有序 堆顶元素就是最大元素
        
        // 注:索引为[0, i]之间为要调整的堆结范围
        for (int i = len - 1; i >= 1; i--) {
            // 将堆中最后一个元素与堆顶元素交换,让最大值放到最后
            swap(nums, 0, i);
            // 此时堆顶是下面换上去的元素很小,堆结构被破坏了,通过sink()方法让该元素下沉至适合位置
            // 注意此时要把最后一个排除在外,因为nums的最大值已经确定->此时堆范围变为[0,i-1]
            sink(nums, 0, i - 1);
            // 下沉完之后[0,i-1]又是一个有序的堆
        }
    }

    /**
     * 调整堆方法(在大顶堆中表现为下沉)
     * 将指定索引target的元素在[0, end]范围内进行下沉操作至正确位置
     * 比较当前节点值与左右子节点最大值,若前节点值小于左右子节点最大值必须下沉(交换)
     *
     * @param nums   待排序的数组
     * @param target 下沉目标元素索引
     * @param end    要调整的堆范围最大索引
     */
    private void sink(int[] nums, int target, int end) {
        int idx = target;   // 下沉指针
        // 若存在左子节点就进入循环(否则表明下沉到底层了)
        while (2 * idx + 1 <= end) {
            // maxLR为左右子节点最大值对应的索引,初始化为左子节点索引
            int maxLR = 2 * idx + 1;
            // 如果有右子节点 && 右子节点的值比左子节点大
            if (maxLR + 1 <= end && nums[maxLR + 1] > nums[maxLR]) {
                // 更新maxLR的值为右子节点索引
                maxLR++;
            }
            // 判断 当前节点值 与 左右子节点最大值maxLR 的大小
            // 正确的堆结构应为:当前节点值nums[idx]>=nums[maxLR] 若这里nums[idx]<nums[maxLR]那就要交换了
            if (nums[idx] < nums[maxLR]) {
                // 将idx位置与maxLR位置元素进行交换
                swap(nums, idx, maxLR);
            } else {
                // nums[idx]>=nums[maxLR]表明target元素位置已经正确->退出
                break;
            }
            // idx指针往maxLR方向走
            idx = maxLR;
        }
    }

    /*
    交换nums[i]与nums[j]的值
     */
    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}