快速排序与归并排序

快速排序基本实现

双指针应用

快速排序里的递归过程本质上就是二叉树的前序递归调用

快速排序基本思想是 ：通过一个标记pivot元素将n个元素的序列划分为左右两个子序列left和right，其中left中的元素都比pivot小，right的都比pivot的大。这样处理完之后pivot就在一个固定的位置了。

然后再次对pivot左右两侧递归执行快速排序。

上述过程是递归执行的，在将所有子区间排好序之后，整个序列就有序了。

// 理解变量是理解程序的关键
// i 指针 指的是 比pivot小的元素 位置
// i的左侧 到j  比pivot大的元素
// 最后，i+1的位置与pivot的元素互换位置
// 能够保证i+1 的左边比当前元素小；右边比当前元素大。
// 但是左边 右边 区域的元素是无序的哦

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int pivot = arr[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        //哨兵移动到位置pivotIndex上
        int pivotIndex = i + 1;
        int temp = arr[pivotIndex];
        arr[pivotIndex] = arr[right];
        arr[right] = temp;

        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
}

// 以 中间值作为 参照物
// 确保中间值的左侧 值均小于右侧值
void quickSort(int[] array, int start, int end) {
    if (start >= end) {
        return;
    }
    //这里就是一个对撞的双指针操作
    int left = start, right = end;
    int pivot = array[(start + end) / 2];

    while (left <= right) {
        while (left <= right && array[left] < pivot) {
            left++;
        }
        while (left <= right && array[right] > pivot) {
            right--;
        }
        if (left <= right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
            left++;
            right--;
        }
    }
    //先处理元素再分别递归处理两侧分支，与二叉树的前序遍历非常像
    quickSort(array, start, right);
    quickSort(array, left, end);   
}

复杂度分析

快速排序的时间复杂度计算比较麻烦一些。从原理来看，如果我们选择的pivot每次都正好在中间，效率是最高的，但是这是无法保证的，因此我们需要从最好、最坏和中间情况来分析

• 最坏情况就是如果每次选择的恰好都是low结点作为pivot，如果元素恰好都是逆序的，此时时间复杂度为O(n^2)

• 如果元素恰好都是有序的，则时间复杂度为O(n)

• 折中的情况是每次选择的都是中间结点，此时序列每次都是长度相等的序列，此时的时间复杂度为(O(nlogn))

数组中第K大的数字

数组中的第K个最大元素。给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

在快排中，pivot的元素位置是不是能够反映元素是第几大。

总共6个元素，比方当前pivot 索引为2

说明他是 第 6-2 + 1 大的元素，即第5大。

要想找第4大，比当前pivot大的元素？ 在他的右侧啦！反之。

int quickselect(int[] nums, int l, int r, int k) {
    if (l == r) return nums[k];
    int x = nums[l], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (nums[i] < x);
        do j--; while (nums[j] > x);
        if (i < j){
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
    if (k <= j) return quickselect(nums, l, j, k);
    else return quickselect(nums, j + 1, r, k);
}
public int findKthLargest(int[] _nums, int k) {
    int n = _nums.length;
    return quickselect(_nums, 0, n - 1, n - k);
}

归并排序

思想：将大的序列先视为若干个小数组，分成比较小的结构，利用归并的思想实现排序的方法。经典的分治策略。分——将问题先分解成小的问题，治——将小问题的答案逐步汇总。

  static void mergeSort(int[] array, int start, int end, int temp[]) {
        if (start >= end) {
            return;
        }
        mergeSort(array, start, (start + end) / 2, temp);
        mergeSort(array, (start + end) / 2 + 1, end, temp);
        merge(array, start, end, temp);
    }

     /**
 * 合并两个已排序的子数组 [start...middle] 和 [middle+1...end] 到原数组中
 * @param array 原数组，包含两个待合并的子数组
 * @param start 合并区间的起始索引
 * @param end 合并区间的结束索引
 * @param temp 临时数组，用于存储合并结果，避免覆盖原数组数据
 */
static void merge(int[] array, int start, int end, int[] temp) {
    // 计算中间点，将区间分为左右两个子数组
    int middle = (start + end) / 2;
    // 左子数组的遍历指针，初始指向左子数组的起始位置（start）
    int left = start;
    // 右子数组的遍历指针，初始指向右子数组的起始位置（middle+1）
    int right = middle + 1;
    // temp数组的填充指针，初始指向合并区间的起始位置（start）
    int index = start;

    // 遍历左右子数组，按升序将元素放入temp
    while (left <= middle && right <= end) {
        // 比较左右子数组当前元素，较小者优先放入temp
        if (array[left] < array[right]) {
            temp[index++] = array[left++];  // 左子数组元素较小，移动左指针
        } else {
            temp[index++] = array[right++]; // 右子数组元素较小，移动右指针
        }
    }

    // 处理左子数组的剩余元素（如果有）
    while (left <= middle) {
        temp[index++] = array[left++];
    }

    // 处理右子数组的剩余元素（如果有）
    while (right <= end) {
        temp[index++] = array[right++];
    }

    // 将合并后的数据从temp复制回原数组的[start...end]区间
    for (int i = start; i <= end; i++) {
        array[i] = temp[i];
    }
}

// 测试方法
   public static void main(String[] args) {
        int[] array = {6, 3, 2, 1, 4, 5, 8, 7};
        int[] temp = new int[array.length];
        mergeSort(array, 0, array.length - 1, temp);
        System.out.println(Arrays.toString(array));
    }