快速排序（Quick Sort）

  • 平均时间复杂度：O(nlogn)
  • 最好情况：O(nlogn)
  • 最坏情况：O(n)
  • 空间复杂度：O(logn)
  • 排序方式：内部

  • 稳定性：不稳定

    C++代码实现

    1. //严蔚敏《数据结构》标准分割函数
    2. Paritition1(int A[], int low, int high) {
    3.  int pivot = A[low];
    4.  while (low < high) {
    5.    while (low < high && A[high] >= pivot) {
    6.      --high;
    7.    }
    8.    A[low] = A[high];
    9.    while (low < high && A[low] <= pivot) {
    10.      ++low;
    11.    }
    12.    A[high] = A[low];
    13.  }
    14.  A[low] = pivot;
    15.  return low;
    16. }
    18. void QuickSort(int A[], int low, int high) //快排母函数
    19. {
    20.  if (low < high) {
    21.    int pivot = Paritition1(A, low, high);
    22.    QuickSort(A, low, pivot - 1);
    23.    QuickSort(A, pivot + 1, high);
    24.  }
    25. }

1. 算法步骤

  1. 从数列中挑出一个元素，称为 “基准”（pivot）;
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

    优化步骤

    ①
    ②

2. 动图演示

quickSort.gif