快速排序算法

快速排序介绍

快速排序（QuickSort）是一种 分治法 排序算法，基本思想是通过一个 基准元素 将待排序的数组分成两部分，使得一部分元素小于基准元素，另一部分元素大于基准元素，然后递归地对这两部分进行排序。

快速排序的步骤：

1. 选择基准：选择一个基准元素，通常是数组的第一个元素、最后一个元素或者中间的元素。

2. 划分数组：根据基准元素，将数组分成两部分：

   • 左边部分：所有小于基准元素的元素。
   • 右边部分：所有大于基准元素的元素。

3. 递归排序：分别对左边和右边的子数组递归进行快速排序。

代码解析：

public static void quickSort(int[] arr, int l, int r) {
    if (l >= r) return;  // 递归终止条件：当左右指针交叉时，停止递归
    int x = arr[(r - l >> 1) + l], i = l - 1, j = r + 1;  // 选择基准元素（数组中间的元素）
    while (i < j) {
        // 从左边开始，找到第一个大于等于基准元素的数
        while (arr[++i] < x);
        // 从右边开始，找到第一个小于等于基准元素的数
        while (arr[--j] > x);
        // 如果左指针小于右指针，则交换元素
        if (i < j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    // 递归排序左半部分
    quickSort(arr, l, j);
    // 递归排序右半部分
    quickSort(arr, j + 1, r);
}

代码详解：

1. 终止条件：if (l >= r) return;
   当左指针大于或等于右指针时，说明数组已经是一个元素或者没有元素需要排序，所以递归终止。

2. 选择基准元素：int x = arr[(r - l >> 1) + l];
   这行代码选择了数组的中间元素作为基准。具体的实现方法是 (r - l >> 1) + l，这相当于 (l + r) / 2，即取数组的中间元素。

3. 初始化指针：int i = l - 1, j = r + 1;

   • i 初始化为 l - 1，指向数组的左侧。
   • j 初始化为 r + 1，指向数组的右侧。

4. 划分过程：

   • while (i < j)：只要 i 小于 j，就继续交换。
   • while (arr[++i] < x);：从左到右遍历，找到第一个大于或等于基准元素的数。
   • while (arr[--j] > x);：从右到左遍历，找到第一个小于或等于基准元素的数。
   • 如果 i < j，说明需要交换这两个元素的位置，确保左边的数小于基准元素，右边的数大于基准元素。

5. 递归排序：

   • quickSort(arr, l, j);：递归对左边子数组进行排序。
   • quickSort(arr, j + 1, r);：递归对右边子数组进行排序。

示例：

假设你有一个数组 arr = {3, 2, 1, 5, 4}，你想对其进行排序。

初始时，l = 0，r = 4，即整个数组范围。选择基准元素为 arr[2] = 1。

1. 第一次划分：

   • 选择 x = 1，i = -1，j = 5。
   • 左指针从 0 开始，找到第一个大于等于 1 的元素 arr[0] = 3。
   • 右指针从 4 开始，找到第一个小于等于 1 的元素 arr[4] = 4。
   • 交换 arr[0] 和 arr[4]，得到 {4, 2, 1, 5, 3}。
   • 继续调整，直到所有元素都正确划分。

2. 递归排序：

   • 递归地对左右子数组分别进行排序，直到每个子数组只有一个元素或为空，最终得到排序好的数组。

快速排序的优缺点：

• 优点：

  • 平均时间复杂度为 O(n log n)，在实际应用中表现优秀。
  • 不需要额外的空间，空间复杂度为 O(log n)。

• 缺点：

  • 最坏情况下时间复杂度为 O(n^2)，当数组已经是有序的或者选择的基准不合适时，性能会退化。
  • 不稳定排序：相等的元素排序后可能会交换顺序。

总结：

快速排序是一个非常高效的排序算法，尤其在大多数情况下，它的表现远远优于其他简单排序算法。通过合理选择基准元素，并且利用分治法的递归思想，快速排序能在平均情况下提供 O(n log n) 的性能。