1. 基本思想

从需要排序的部分中取一个数作为切分值，以此为基准对数组进行切分，使其左边部分的元素小于等于该基准值，右边的元素大于等于基准值，再递归地对其左右两边的数组进行快速排序

2. 代码实现

  1. int partition(vector<int>& vec, int lo, int hi){
  2.     int val = vec[lo];
  3.     int l = lo, r = hi +1; 
  4.     while(true){
  5.         while(vec[++l] < val && l < hi); //防止越界
  6.         while(vec[--r] > val);           //因为第一个数为val，所以不会越界
  7.         if (l >= r) break;
  8.         swap(vec[l], vec[r]);
  9.     }
  10.     swap(vec[r], vec[lo]); //将基准值移动到适当位置
  11.     return r;
  12. }
  14. void quickSort(vector<int>& vec, int lo, int hi){
  15.     if (lo >= hi) return;
  16.     int p = partition(vec, lo, hi);
  17.     quickSort(vec, lo, p - 1);
  18.     quickSort(vec, p + 1, hi);
  19. }

3. 效率分析

  • 普遍情况下时间复杂度为 O(nlogn)，如果数组有序时，未优化时间复杂度为 O(n2)。空间复杂度为函数栈的深度，最好情况为 O(logn)，最坏情况下为 O(n)
  • 选取基准值时从排序范围中随机选择数字而不是总选取第一个数字可以防止有序情况下复杂度变为 O(n2)
  • 选择排序是不稳定的排序算法，例如有两个大于基准值的相同元素在基准值应该处于的位置的左边，在切分过程中，这两个元素中左边的那个会被交换到数组靠后的位置，右边那个元素会被交换到数组靠前的位置