快速排序基本概念

快速排序(QuickSort)是由英国计算机科学家Tony Hoare在1960年提出的一种高效排序算法,它采用分治法(Divide and Conquer)策略。快速排序的基本思想是:

  1. 选择基准值(Pivot):从数组中选择一个元素作为基准值。
  2. 分区操作(Partition):将数组中的元素重新排列,使得所有小于基准值的元素放在基准值的左边,所有大于基准值的元素放在基准值的右边。这个过程称为分区(Partitioning)。
  3. 递归排序子数组:对基准值左右两侧的子数组分别递归地应用快速排序。

快速排序的平均时间复杂度为O(n log n),最坏情况下为O(n²),但通过合理选择基准值(如三数取中法),可以有效避免最坏情况的发生。它是一种原地排序算法(不需要额外的存储空间),因此在实际应用中非常高效。

快速排序的C++实现

下面是一个用C++实现的快速排序算法,包含详细的注释:

#include <iostream>
#include <vector>
using namespace std;

// 分区函数:将数组的一部分进行分区,返回基准值的最终位置
int partition(vector<int>& arr, int low, int high) {
    // 选择最后一个元素作为基准值
    int pivot = arr[high];
    // i 指向当前小于基准值的元素序列的末尾
    int i = low - 1;

    // 遍历从 low 到 high-1 的所有元素
    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于基准值
        if (arr[j] < pivot) {
            // i 向前移动一位
            i++;
            // 交换 arr[i] 和 arr[j]
            swap(arr[i], arr[j]);
        }
    }
    // 将基准值放到正确的位置
    swap(arr[i + 1], arr[high]);
    // 返回基准值的位置
    return (i + 1);
}

// 快速排序函数:对数组的 [low, high] 区间进行排序
void quickSort(vector<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);
    }
}

// 辅助函数:打印数组
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}

int main() {
    // 测试数据
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    cout << "原始数组: ";
    printArray(arr);

    // 调用快速排序
    quickSort(arr, 0, arr.size() - 1);

    cout << "排序后的数组: ";
    printArray(arr);

    return 0;
}

代码解释

  1. partition函数

    • 该函数选择最后一个元素作为基准值(pivot)。
    • 使用变量i来跟踪小于基准值的元素应该放置的位置。
    • 遍历数组,将所有小于基准值的元素交换到左边。
    • 最后将基准值放到正确的位置,并返回该位置。
  2. quickSort函数

    • 递归地对数组进行排序。
    • 如果low小于high,说明子数组中至少有两个元素,需要继续排序。
    • 通过调用partition函数获取基准值的位置,然后分别对左右两部分递归排序。
  3. main函数

    • 创建测试数组并打印原始数据。
    • 调用quickSort函数进行排序。
    • 打印排序后的结果。

快速排序示例

让我们通过一个简单的例子来演示快速排序的工作过程。假设我们有一个数组:[5, 3, 8, 4, 2]

  1. 选择基准值:选择最后一个元素2作为基准值。

  2. 分区操作

    • 遍历数组:5大于2,不交换;3大于2,不交换;8大于2,不交换;4大于2,不交换。
    • 最后将基准值2与第一个大于它的元素5交换,得到:[2, 3, 8, 4, 5]
    • 基准值2的最终位置是索引0
  3. 递归排序子数组

    • 左子数组:[],无需排序。
    • 右子数组:[3, 8, 4, 5],继续排序。

对于右子数组[3, 8, 4, 5]

  • 选择基准值5
  • 分区后得到:[3, 4, 5, 8]
  • 递归排序左子数组[3, 4]和右子数组[8]

最终得到排序后的数组:[2, 3, 4, 5, 8]

快速排序的优化

虽然上面的实现很直观,但在实际应用中,我们可以通过以下方法优化快速排序:

  1. 随机选择基准值:避免最坏情况的发生,提高算法的稳定性。

  2. 三数取中法:选择数组的第一个、中间和最后一个元素的中间值作为基准值,进一步减少最坏情况的概率。

  3. 小数组使用插入排序:对于小规模数组,插入排序的性能更好,可以在子数组较小时切换到插入排序。

  4. 三路快排:将数组分为小于、等于和大于基准值三部分,处理包含大量重复元素的数据时效率更高。

快速排序是一种非常灵活的算法,通过不同的优化策略,可以适应各种不同的应用场景。

3 条评论

  • @ 2025-6-16 20:35:57

    将快速排序中的分区逻辑从 arr[j] > pivot 改为 arr[j] >= pivot 确实有区别,但两种实现都是正确的。它们的主要区别在于处理重复元素的方式和性能表现

    核心区别

    1. 右指针 j 的终止条件

      • 原代码(arr[j] > pivotj 会停在第一个 ≤ pivot 的元素上。
      • 修改后(arr[j] >= pivotj 会跳过所有 = pivot 的元素,直到遇到 < pivot 的元素或与 i 交叉。
    2. 重复元素的分布

      • 原代码:重复的 pivot 值可能被分散到左右两部分。
      • 修改后:更多重复的 pivot 值会被集中到左半部分(基准值最终的左侧)。

    正确性分析

    两种实现都能正确排序的原因:

    • 分区的本质:快速排序的核心是将数组分为两部分,使得左半部分 ≤ pivot,右半部分 ≥ pivot
    • 基准值归位:无论哪种实现,最终 pivot 都会被放到正确的位置(左侧元素 ≤ 它,右侧元素 ≥ 它)。

    性能差异

    修改后的版本(arr[j] >= pivot)在处理大量重复元素时更高效:

    • 三路划分思想:通过将相等元素集中在一侧,减少后续递归中对重复元素的处理。
    • 减少递归深度:重复元素越多,性能优势越明显。

    示例验证

    对于数组 [6, 3, 8, 2, 9, 1],两种实现的排序结果相同,但分区过程可能不同:

    • 原代码:分区后可能为 [1, 3, 2, 6, 9, 8](基准值 6 左侧有部分较小元素)。
    • 修改后:分区后可能为 [3, 2, 1, 6, 9, 8](基准值 6 左侧集中了更多 ≤6 的元素)。

    总结

    特性 原代码 (arr[j] > pivot) 修改后 (arr[j] >= pivot)
    正确性 ✅ 正确
    重复元素处理 分散到两侧 集中到左侧
    性能(大量重复元素) 一般 更优(减少递归)
    基准值位置 可能偏向右侧 可能偏向左侧

    建议

    如果数据中重复元素较多,推荐使用 arr[j] >= pivot,因为它更符合三路划分快速排序的思想(将数组分为 <pivot=pivot>pivot 三部分),能有效减少递归次数。对于随机数据,两种实现性能差异不大。

    • @ 2025-6-9 23:02:04

      C++ 快速排序教程

      一、什么是快速排序?

      快速排序(Quick Sort)是一种高效的排序算法,它基于**分治法(Divide and Conquer)**的思想:

      • 基本思想:
        • 从数组中选出一个“基准”元素(pivot)
        • 将所有比基准小的元素放到它的左边
        • 所有比基准大的元素放到它的右边
        • 然后对左右两个子数组递归地进行同样的操作

      这个过程称为分区(partition)


      二、快速排序的优点

      • 平均时间复杂度为 O(n log n)
      • 原地排序,空间复杂度为 O(log n)(因为递归调用栈)

      三、通俗易懂的图解思路

      假设我们要排序数组:[6, 3, 8, 2, 9, 1]

      1. 选一个基准数(比如选第一个数 6
      2. 把小于 6 的放左边,大于 6 的放右边 → [3, 2, 1, 6, 9, 8]
      3. 对左右两部分继续递归执行上述操作

      四、C++ 实现代码(带注释)

      #include <iostream>
      using namespace std;
      
      // 分区函数:将数组分成两部分
      int partition(int arr[], int left, int right) {
          int pivot = arr[left];  // 选取最左边的元素作为基准
          int i = left + 1;       // 左指针,找比 pivot 大的值
          int j = right;          // 右指针,找比 pivot 小的值
      
          while (true) {
              // 向右移动 i,直到找到比 pivot 大的数
              while (i <= j && arr[i] < pivot)
                  i++;
      
              // 向左移动 j,直到找到比 pivot 小的数
              while (i <= j && arr[j] > pivot)
                  j--;
      
              // 如果 i 和 j 还没交叉,交换它们指向的值
              if (i <= j) {
                  swap(arr[i], arr[j]);
                  i++;
                  j--;
              } else {
                  break;
              }
          }
      
          // 最后把 pivot 放到中间正确的位置
          swap(arr[left], arr[j]);
          return j; // 返回 pivot 的位置
      }
      
      // 快速排序主函数(递归)
      void quickSort(int arr[], int left, int right) {
          if (left >= right) return; // 递归终止条件
      
          // 分区操作,得到基准的位置
          int pivotIndex = partition(arr, left, right);
      
          // 递归排序左半部分
          quickSort(arr, left, pivotIndex - 1);
      
          // 递归排序右半部分
          quickSort(arr, pivotIndex + 1, right);
      }
      
      // 主函数测试
      int main() {
          int arr[] = {6, 3, 8, 2, 9, 1};
          int n = sizeof(arr) / sizeof(arr[0]);
      
          cout << "排序前:" << endl;
          for (int i = 0; i < n; ++i) {
              cout << arr[i] << " ";
          }
          cout << endl;
      
          quickSort(arr, 0, n - 1); // 调用快速排序
      
          cout << "排序后:" << endl;
          for (int i = 0; i < n; ++i) {
              cout << arr[i] << " ";
          }
          cout << endl;
      
          return 0;
      }
      

      五、代码解释

      函数说明:

      • partition()

        • 功能:选择基准,把小的放左边,大的放右边
        • 返回值:基准最终所在的位置
      • quickSort()

        • 功能:递归地对左右两边进行排序

      关键点:

      • 使用双指针 ij 来扫描数组
      • 每次交换不符合条件的元素
      • 最后把基准放到正确位置

      六、示例输出

      排序前:
      6 3 8 2 9 1 
      排序后:
      1 2 3 6 8 9
      

      七、常见问题解答

      Q1: 快速排序是稳定排序吗?

      不是。快速排序在交换过程中可能会打乱相同元素的相对顺序。

      Q2: 如何优化快速排序?

      • 随机选择基准(避免极端情况)
      • 三数取中法(mid of three)
      • 对小数组使用插入排序

      八、总结

      特性 描述
      时间复杂度 平均 O(n log n),最坏 O(n²)
      空间复杂度 O(log n)(递归栈)
      是否稳定
      是否原地排序

      如果你理解了“分区”的概念,快速排序就变得非常简单啦!希望这篇教程能帮你彻底掌握它 😊

      • @ 2025-6-9 22:59:44

        C++ 快速排序教程

        一、快速排序简介

        快速排序(Quick Sort)是一种高效的排序算法,采用分治策略(Divide and Conquer)。它通过一个称为“基准”(pivot)的元素将数组分成两个子数组:

        • 一部分比基准小
        • 一部分比基准大

        然后递归地对这两部分进行快速排序,最终实现整个数组的有序。

        特点:

        • 平均时间复杂度:O(n log n)
        • 最坏情况:O(n²)(当数组已基本有序或所有元素都相等时)
        • 原地排序(不需要额外空间)
        • 不稳定排序

        二、快速排序的基本思想

        1. 选择基准值(pivot):从数组中选一个元素作为基准。
        2. 分区(Partition):把数组划分为两部分,使得左边元素 ≤ pivot,右边元素 ≥ pivot。
        3. 递归处理左右两部分:对左半部分和右半部分分别进行快速排序。

        三、快速排序步骤详解

        我们以数组 [6, 3, 8, 2, 9, 1] 为例:

        1. 选基准:通常选最后一个元素 1 作为 pivot。
        2. 分区操作
          • 遍历数组,将小于等于 pivot 的数放到左边,大于 pivot 的数放到右边。
          • 最终 pivot 放到正确位置。
        3. 递归排序左右子数组

        四、C++ 实现代码(带详细注释)

        #include <iostream>
        using namespace std;
        
        // 打印数组函数
        void printArray(int arr[], int size) {
            for (int i = 0; i < size; ++i)
                cout << arr[i] << " ";
            cout << endl;
        }
        
        // 分区函数:将数组分为两部分,并返回基准的位置
        int partition(int arr[], int left, int right) {
            int pivot = arr[right];  // 选取最右边的元素作为基准
            int i = left - 1;        // i 是小于等于 pivot 的边界指针
        
            for (int j = left; j < right; ++j) {
                if (arr[j] <= pivot) {  // 如果当前元素小于等于 pivot
                    ++i;                // 边界指针右移
                    swap(arr[i], arr[j]);  // 将该元素放到左边去
                }
            }
        
            // 最后把 pivot 放到正确位置(即中间)
            swap(arr[i + 1], arr[right]);
            return i + 1;  // 返回 pivot 的位置
        }
        
        // 快速排序主函数(递归)
        void quickSort(int arr[], int left, int right) {
            if (left < right) {
                // 分区操作,获取基准的位置
                int pi = partition(arr, left, right);
        
                // 对左边子数组排序
                quickSort(arr, left, pi - 1);
        
                // 对右边子数组排序
                quickSort(arr, pi + 1, right);
            }
        }
        
        // 主函数测试
        int main() {
            int arr[] = {6, 3, 8, 2, 9, 1};
            int size = sizeof(arr) / sizeof(arr[0]);
        
            cout << "原始数组:" << endl;
            printArray(arr, size);
        
            quickSort(arr, 0, size - 1);  // 调用快速排序函数
        
            cout << "排序后数组:" << endl;
            printArray(arr, size);
        
            return 0;
        }
        

        五、代码说明

        函数名 功能
        partition() 将数组分为两部分,并返回 pivot 的位置
        quickSort() 递归调用自身,对左右子数组进行排序
        main() 测试代码,输入数组并输出排序结果

        六、示例运行结果

        原始数组:
        6 3 8 2 9 1 
        排序后数组:
        1 2 3 6 8 9
        

        七、优化建议

        1. 随机选择 pivot:避免最坏情况(如数组已经有序)。
        2. 三数取中法:选择首、中、尾三个元素的中间值作为 pivot。
        3. 小数组切换插入排序:对于长度较小的子数组(如 < 10),使用插入排序效率更高。

        八、总结

        快速排序是面试与实际开发中最常用的排序算法之一。掌握它的原理和实现方式,有助于你更好地理解分治思想以及递归编程技巧。

        如果你能自己默写一遍快排代码并解释清楚每一步的作用,那你就真正掌握了这个算法!


        如有需要,我还可以提供:

        • 随机 pivot 的版本
        • 非递归实现
        • 时间性能测试对比

        是否需要这些内容?

        • 1