房地产市场最新消息_精品课程网站的设计与实现_定制网站和模板建站_深圳网站关键词排名优化

快速排序与归并排序青铜挑战

快速排序的原理和实现

 快速排序（Quick Sort）是一种分治法（Divide and Conquer）策略的排序算法，它通过选择一个“基准”元素，将数组分成两个部分，左边部分小于基准元素，右边部分大于基准元素，然后递归地对这两个部分进行排序。

• 选择基准元素：可以选择数组中的任何一个元素作为基准，通常选择第一个元素、最后一个元素、随机元素或中间元素。
• 分区过程：重新排列数组，使得比基准元素小的元素排在基准元素的左边，比基准元素大的元素排在右边。最后，基准元素在排序后的数组中会处于其最终位置。
• 递归排序：递归地对基准元素左侧和右侧的子数组进行快速排序。

public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {// 获取分区点int pi = partition(arr, low, high);// 对基准元素左侧部分递归排序quickSort(arr, low, pi -1);// 对基准元素右侧部分递归排序quickSort(arr, pi + 1, high);}}private static int partition(int[] arr, int low, int high){// 选择最后一个元素作为基准int pivot = arr[high];// i 指向小于基准的区域的最右端int i = low - 1;// 遍历数组，将小于基准的元素放到左边for(int j = low; j < high; j++){if (arr[j] <= pivot) {i++;swap(arr, i, j);}}// 把基准元素放到正确的位置swap(arr, i + 1, high);// 返回基准元素的位置return i + 1;}private static void swap(int[] arr, int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {int[] arr = {10, 80, 30, 90, 40, 50, 70};System.out.println("原始数组:");printArray(arr);quickSort(arr, 0, arr.length - 1);System.out.println("\n排序后的数组:");printArray(arr);}private static void printArray(int[] arr) {for (int i : arr) {System.out.print(i + " ");}System.out.println();}
}

• quickSort方法：这是快速排序的核心递归函数，它接受数组和当前处理的低、高索引。递归地对数组进行排序，直到子数组的长度为1。
• partition方法：这是分区函数，它通过选择数组的最后一个元素作为基准，并调整数组，使得所有小于基准的元素放到左边，所有大于基准的元素放到右边。最后返回基准元素的位置。
• swap方法：用于交换数组中的两个元素。
• printArray方法：辅助方法，打印数组内容。

时间和空间复杂度：

• 最佳和平均时间复杂度：O(n log n)，当分区均匀时，算法的时间复杂度为 O(n log n)。
• 最坏时间复杂度：O(n^2)，当数组已经是有序的或者所有元素相等时，最坏情况下会退化为冒泡排序。
• 空间复杂度：O(log n)，递归调用栈的空间
• 稳定性：快速排序是不稳定的排序算法，即相等元素的相对顺序可能在排序后改变。

快速排序与归并排序白银挑战

快速排序的应用

数组中的第K个最大元素

leetcode215

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

• 使用快速选择（QuickSelect）
  快速选择算法是快速排序的变种，它使用 分区（Partition） 技术，每次选择一个 基准值（pivot），然后调整数组，使得：

  • 左侧的元素都大于等于 pivot
  • 右侧的元素都小于 pivot

  如果 pivot 的索引正好是 k-1，那么它就是第 k 个最大的元素；否则，就在相应的部分继续递归查找。

• 如何调整 k 的位置

  • 转换为第 (n-k) 小的数（因为数组是从 0 开始索引的）。
  • 例如：在 [3,2,1,5,6,4] 中找第 2 大的数，实际上是找 第 (6-2=4) 小的数（索引 3）。

import java.util.Random;public class KthLargestElement {public int findKthLargest(int[] nums, int k) {int n = nums.length;return quickSelect(nums, 0, n - 1, n - k);}private int quickSelect(int[] nums, int left, int right, int kSmallest) {if (left == right) return nums[left]; // 只有一个元素时返回它Random rand = new Random();int pivotIndex = left + rand.nextInt(right - left + 1); // 随机选择pivotpivotIndex = partition(nums, left, right, pivotIndex);if (pivotIndex == kSmallest) {return nums[pivotIndex];} else if (pivotIndex < kSmallest) {return quickSelect(nums, pivotIndex + 1, right, kSmallest);} else {return quickSelect(nums, left, pivotIndex - 1, kSmallest);}}private int partition(int[] nums, int left, int right, int pivotIndex) {int pivotValue = nums[pivotIndex];swap(nums, pivotIndex, right); // 先把 pivot 移到最后int storeIndex = left;for (int i = left; i < right; i++) {if (nums[i] < pivotValue) { // 这里是 "<"，保证小的在左swap(nums, storeIndex, i);storeIndex++;}}swap(nums, storeIndex, right); // 把 pivot 放回正确位置return storeIndex;}private void swap(int[] nums, int i, int j) {int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}public static void main(String[] args) {KthLargestElement solution = new KthLargestElement();int[] nums = {3,2,3,1,2,4,5,5,6};int k = 4;System.out.println("第 " + k + " 大的元素是：" + solution.findKthLargest(nums, k));}
}

• 平均时间复杂度: O(n)（每次减少一半的搜索空间）
• 最坏时间复杂度: O(n²)（如果每次选到的 pivot 都是最小/最大的值）
• 空间复杂度: O(1)（原地交换，不需要额外空间）

快速排序与归并排序黄金挑战

归并排序

归并排序是一种 分治（Divide and Conquer） 算法，它的核心思想是：

1. 分解（Divide）： 递归地将数组分成两半，直到每个子数组只包含一个元素。
2. 合并（Merge）： 将两个已经排序的子数组合并为一个有序数组。

归并排序的特性

• 时间复杂度： O(nlog⁡n)O(n \log n)O(nlogn)（无论是最优、最坏还是平均情况）
• 空间复杂度： O(n)O(n)O(n)（需要额外的临时数组）
• 稳定性： 稳定排序（不会改变相同元素的相对位置）
• 适用场景： 适用于需要稳定排序、数据规模较大且不要求原地排序的情况。

public void mergeSort(int[] array, int start, int end, int[] temp) {//2.直至每个序列只包含一个元素，停止划分if (start >= end) {return;}//1.从中间开始，每次划分为两个序列mergeSort(array, start, (start + end) / 2, temp);mergeSort(array, (start + end) / 2 + 1, end, temp);//3。进行有序数组的合并merge(array, start, end, temp);
}public void merge(int[] array, int start, int end, int[] temp) {//找到序列中点int mid = (start + end) / 2;//left遍历左边的序列int left = start;//right遍历右边的序列int right = mid + 1;//index遍历临时数组，存储合并结果int index = 0;//两个序列均从起点到终点进行遍历while (left <= mid && right <= end) {//将两个序列中较小的元素放入临时数组中if (array[left] < array[right]) {temp[index++] =array[left++];}else {temp[index++] =array[right++];}}//此时仅剩一个序列未遍历结束，直接赋值while (left <= mid){temp[index++] =array[left++];}while (right<=end){temp[index++] =array[right++];}//将归并的结果拷贝到原数组for (int i=start;i<=end;i++){array[i] = temp[i];}
}

用归并排序解决 "第 k 大的元素" 问题

我们可以使用 归并排序 对数组进行排序，然后直接返回第 k 大的元素。

步骤

1. 使用归并排序对 nums 进行排序。
2. 排序后，第 k 大的元素就是 倒数第 k 个 (nums[n - k])。

import java.util.Arrays;public class KthLargestMergeSort {public int findKthLargest(int[] nums, int k) {mergeSort(nums, 0, nums.length - 1);return nums[nums.length - k]; // 取倒数第 k 个元素}private void mergeSort(int[] nums, int left, int right) {if (left >= right) return; // 递归终止条件int mid = left + (right - left) / 2;mergeSort(nums, left, mid);      // 递归排序左半部分mergeSort(nums, mid + 1, right); // 递归排序右半部分merge(nums, left, mid, right);   // 归并两个有序数组}private void merge(int[] nums, int left, int mid, int right) {int[] temp = new int[right - left + 1]; // 临时数组int i = left, j = mid + 1, k = 0;// 归并左右两部分while (i <= mid && j <= right) {if (nums[i] <= nums[j]) {temp[k++] = nums[i++];} else {temp[k++] = nums[j++];}}// 处理剩余元素while (i <= mid) temp[k++] = nums[i++];while (j <= right) temp[k++] = nums[j++];// 复制回原数组System.arraycopy(temp, 0, nums, left, temp.length);}public static void main(String[] args) {KthLargestMergeSort solver = new KthLargestMergeSort();int[] nums = {3, 2, 3, 1, 2, 4, 5, 5, 6};int k = 4;System.out.println("第 " + k + " 大的元素是：" + solver.findKthLargest(nums, k));}
}

• findKthLargest()

  • 先对 nums 进行归并排序。
  • 由于 nums 排序后是升序，所以第 k 大的元素在 nums[nums.length - k] 位置。

• mergeSort()（递归排序）

  • 计算中点 mid，将数组 一分为二，然后分别对左右部分递归排序。
  • 递归到最小单元后，开始调用 merge() 进行合并。

• merge()（合并两个有序数组）

  • 通过 双指针 比较两个有序数组的元素，把较小的值放入 temp 数组。
  • 处理剩余元素并复制回原数组。

时间复杂度和空间复杂度：

• 时间复杂度： O(nlog⁡n)O(n \log n)O(nlogn)
  • 归并排序的 拆分 需要 O(log⁡n)O(\log n)O(logn)，每次合并需要 O(n)O(n)O(n)。
• 空间复杂度： O(n)O(n)O(n)
  • 需要额外的 temp 数组存放合并后的结果（非原地排序）。