参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int partition(int a[] , int l , int r){
    int povit = a[l] , i = l , j = r ; 
    while(i<j){
        while(i<j && a[j] >= povit)j-- ; 
        swap(a[i],a[j]);
        while(i<j && a[i] <= povit)i++ ;
        swap(a[i],a[j]);
    }
    a[i] = povit ; 
    return i ; 
}

void Quicksort(int a[] , int l , int r ){
    if(l<r){
        int mid = partition(a,l,r) ; 
        Quicksort(a , l , mid-1);
        Quicksort(a , mid + 1 , r);
    }
}

步骤讲解

  1. 设基准为$ povit = a[l] $ , $ i = l , j = r $

  2. 先从右端$(j)$开始,向左移动，直到$a[j] < povit $ , 交换$ a[i] , a[j]$ 。

  3. 再从左端$ (i)$开始，向右移动，直到$a[i] > povit $ , 交换$ a[i] , a[j]$ 。

  4. 不停重复，直到 $ i = j $停下。

  5. 先不停向左边重复，计算完左边再计算右边。

老师例题讲解

初始序列

{501, 89, 512, 61, 90, 908, 170, 897, 276, 653, 462}

第1趟排序（pivot=501）

当前处理区间：[0,10] ➔ {501, 89, 512, 61, 90, 908, 170, 897, 276, 653, 462}

  1. 从右找<501：

    • j=10 : 462<501 → 交换0和10
      {462, 89, 512, 61, 90, 908, 170, 897, 276, 653, 501}

  2. 从左找>501：

    • i=2 : 512>501 → 交换2和10
      {462, 89, 501, 61, 90, 908, 170, 897, 276, 653, 512}

  3. 从右找<501：

    • j=8 : 276<501 → 交换2和8
      {462, 89, 276, 61, 90, 908, 170, 897, 501, 653, 512}

  4. 从左找>501：

    • i=5 : 908>501 → 交换5和8
      {462, 89, 276, 61, 90, 501, 170, 897, 908, 653, 512}

  5. 从右找<501：

    • j=6 : 170<501 → 交换5和6
      {462, 89, 276, 61, 90, 170, 501, 897, 908, 653, 512}

第1趟结果：
{462, 89, 276, 61, 90, 170} |501| {897, 908, 653, 512}

第2趟排序（左区间，pivot=462）

当前处理区间：[0,5] ➔ {462, 89, 276, 61, 90, 170}

  1. 从右找<462：

    • j=5 : 170<462 → 交换0和5
      {170, 89, 276, 61, 90, 462}

  2. 从左找>462：

    • 未找到 → i=j=5

第2趟结果：
{170, 89, 276, 61, 90} |462| |501| {897, 908, 653, 512}

第3趟排序（左区间，pivot=170）

当前处理区间：[0,4] ➔ {170, 89, 276, 61, 90}

  1. 从右找<170：

    • j=3 : 61<170 → 交换0和3
      {61, 89, 276, 170, 90}

  2. 从左找>170：

    • i=2 : 276>170 → 交换2和3
      {61, 89, 170, 276, 90}

  3. 从右找<170：

    • j=2 → i=j=2

第3趟结果：
{61, 89} |170| {276, 90} |462| |501| {897, 908, 653, 512}

第4趟排序（左子区间，pivot=61）

当前处理区间：[0,1] ➔ {61, 89}

  1. 从右找<61：
    • 未找到 → i=j=0

第4趟结果：
|61| {89} |170| {276, 90} |462| |501| {897, 908, 653, 512}

第5趟排序（右子区间，pivot=276）

当前处理区间：[3,4] ➔ {276, 90}

  1. 从右找<276：
    • j=4 : 90<276 → 交换3和4
      {90, 276}

第5趟结果：
|61| {89} |170| |90| |276| |462| |501| {897, 908, 653, 512}

第6趟排序（右大区间，pivot=897）

当前处理区间：[7,10] ➔ {897, 908, 653, 512}

  1. 从右找<897：

    • j=10 : 512<897 → 交换7和10
      {512, 908, 653, 897}

  2. 从左找>897：

    • i=1 : 908>897 → 交换1和10
      {512, 897, 653, 908}

  3. 从右找<897：

    • j=2 : 653<897 → 交换1和2
      {512, 653, 897, 908}

最终结果：
|61| |89| |90| |170| |276| |462| |501| |512| |653| |897| |908|

尾声

1
a[i] = povit ;

其实已经在swap中被我们处理了，因为swap函数是双向交换，不是单向赋值，povit并没有丢失，所以是不需要另外强调的。