快排讲解

FengSiYuan1 · 2024-07-11 15:40:07 · 个人记录

总结

快速排序是一种高效的排序算法

• 基本思想

  它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，直到整个序列有序。

• 代码展示

  #include <iostream>
  using namespace std;
  // 分区函数，将数组分为两部分，左边小于 pivot，右边大于 pivot
  int partition(int arr[], int low, int high) {
  int pivot = arr[high]; // 选择最右侧的元素作为基准值
  int i = (low - 1); // 指针 i 从左侧开始
  for (int j = low; j <= high - 1; j++) {
      if (arr[j] < pivot) {
          i++; // 如果当前元素小于 pivot，则向右移动指针并交换
          swap(arr[i], arr[j]);
      }
  }
  swap(arr[i + 1], arr[high]); // 将 pivot 放到正确的位置
  return (i + 1);
  }
  // 快速排序主函数
  void quick_Sort(int arr[], int low, int high) {
  if (low < high) {
      // 找到分区点并将元素放到正确位置
      int pi = partition(arr, low, high);
      // 对分区左右两边分别递归排序
      quick_Sort(arr, low, pi - 1);
      quick_Sort(arr, pi + 1, high);
  }
  }
  // 示例
  int main(){
  int arr[] = {9, 7, 5, 11, 12, 2, 14, 3};
  int n = sizeof(arr) / sizeof(arr);
  cout << "Original array: ";
  for (int i=0; i < n; i++)
      cout << arr[i] << " ";
  quick_Sort(arr, 0, n-1); // 从第一个元素开始排序
  cout << "\nSorted array: ";
  for (int i=0; i < n; i++)
      cout << arr[i] << " ";
  return 0;
  }

• 实现逻辑

  选取基准（pivot）：通常选择数组的最后一个元素，但也可以随机选取。
  分区操作：从左到右遍历数组，当遇到比基准小的元素，就将其与i指向的元素交换，并将i加一。遍历结束后，基准会位于其最终应处的位置。
  递归调用：对于基准左边的小于基准的部分和右边的大于基准的部分，分别对它们进行同样的快速排序过程。
  结束条件：当低索引大于等于高索引时停止，表示已排序完成。

• 思维导图