Talk is cheap, show me the code

• 参照中C++实现(递归)方式, 略改一点点, 更容易理解. 代码如下:

void quick_sort_recursive(vector
    
      &a, int start, int end) {    if (start >= end) return;    int base = a[end];    int left = start, right = end - 1;  // 从right=end开始也无妨, 因为`>=`就--right    while (true) {        while (a[left] < base) ++left;        while (a[right] >= base) --right;        if (left >= right) break;        swap(a[left], a[right]);    // 原wiki的代码方式将出现多次浪费的swap,如swap(a[1],a[1])这种形式    }    if (a[left] >= a[end]) swap(a[left], a[end]);   // 将base放到指定位置    else ++left;    quick_sort_recursive(a, start, left - 1);    quick_sort_recursive(a, left + 1, end);}
    

需要说明的是:

• while (arr[right] >= mid) right--; 如果>=换成>会导致陷入无限循环
• 第一个while之后的if else语句作用是将mid放到指定位置(不会再变的位置), 完成左右划分,左边都是<mid,右边都是>=mid.
• 上述实现过程和<算法导论>思路有差异, 和<数据结构/算法/C++实现> 思路一致,但是实现上略有差异

示例

int main() {    vector
    
      a{4, 8, 1, 3, 7, 5, 6, 2, 4, 4};    quick_sort_recursive(a, 0, a.size() - 1);    return 0;}
    

if a[left]>base, ++left;

if a[right]<=base, --right;

内层while第1次swap

第2, 3次变化过程

跳出while后

注意

该示例中, 如果if a[right]<=base, --right;没有=号将陷入死循环, 亲自演算一下排序过程大有裨益!