题目：P1177 【模板】排序

题目描述

将读入的 $N$ 个数从小到大排序后输出。

输入格式

第一行为一个正整数 $N$。

第二行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数。

输出格式

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例 #1

输入 #1

5
4 2 4 5 1

输出 #1

1 2 4 4 5

说明/提示

对于 $20\%$ 的数据，有 $1\le N\le 10^3$；

对于 $100\%$ 的数据，有 $1\le N\le 10^5$，$1\le a_i\le 10^9$。

题目链接

P1177 【模板】快速排序

---

完整代码实现

#include <stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quick_sort(int q[], int l, int r) {
    if(l >= r) return;
    int i = l-1, j = r+1, x = q[(l+r)>>1];
    while(i < j) {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(&q[i], &q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j+1, r);
}

int main() {
    int n;
    scanf("%d", &n);
    int a[n];
    for(int i=0; i<n; i++) scanf("%d", &a[i]);
    
    quick_sort(a, 0, n-1);
    
    for(int i=0; i<n; i++) 
        printf("%d ", a[i]);
    return 0;
}

---

我的思路

1. 基本思想

• 分区：选择一个基准值，将数组分为两部分。
• 递归：对左右两部分分别进行快速排序。

2. 实现细节（记忆）

// 核心代码片段
void quick_sort(int q[], int l, int r) {
    if(l >= r) return;
    int i = l-1, j = r+1, x = q[(l+r)>>1];
    while(i < j) {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j+1, r);
}

3.解释代码，用快递架举例

我们可以用快递架来理解这个代码。假设快递架子上有很多个快递，这由你提供的 q[] 这个数组里有多少个数决定。我们需要确定左侧和右侧的头和尾的位置，即 l 和 r。然后选择一个基准值来对这堆快递进行初步的排列。基准值我们选择中间的部分（中间值），可以看作是一个质量适中的快递。

x=q[(l+r)>>1] //实际上也等同于x=q[(l+r)/2]，也就是取中间值

我们同时从左边和右边开始，检查快递

int i=l-1,j=r+1 //这里就是从左边和右边开始的指针，用来指出现在检查到哪个快递了

检查的过程中：取出目前指针指着的快递，拿去与基准的快递进行比较。在基准快递的左边区域，要看看拿出来的快递是否轻于基准值；在基准快递的右边区域，要看看拿出来的快递是否重于基准值。如果没有，就把指针移到下一个快递，继续检测（使用 do-while）。

这里的检测会一直检测，直到遇到另一个指针

（左侧）如果这个快递，轻于基准值，则指针停在这里
（右侧）如果这个快递，重于基准值，则指针停在这里

while(i < j) {                          //指针不相交
        do i++; while(q[i] < x);        //这里使用do-while，从左找大于x的数
        do j--; while(q[j] > x);        //从右找大于x的数
    }

然后就是交换环节，把左边重于基准值的快递与右边轻于基准值的快递，这里要注意，指针不要交叉（相互经过）在了一起

if(i < j) swap(q[i], q[j]);      //交换数值 

这里也可以写成

if(i < j){
int temp=q[i];         //交换数值
q[i]=q[j];
q[j]=temp;
}

那么，这里就有一个问题了：为什么不能交换呢？
在代码中

while(i<j)
if(i<j)

都是左右指针不相交的
原理也很简单：若此时强行交换，会把已经归位的快递重新打乱
举例：假设基准是5kg的快递（中间值），当前快递架状态：（指针i，j在初始位置）

[3kg, 4kg | 5kg | 7kg, 6kg]
 ↑i                     ↑j

当i超过j的位置时：

[3kg, 4kg | 5kg | 7kg, 6kg]
      ↑j           ↑i    

强行交换后

[3kg, 7kg | 5kg | 4kg, 6kg] 
      ↑j           ↑i

这样强行交换，就会把原有的排序给打乱了
所以指针不能相交：

正常分区： [ ≤x | ≥x ]
指针交叉： [ ≤x ] [ ≥x ]
              j   i

那么最后，就是把分化好的区域再次进行这个操作（递归），把左边的区域再次选择基准值进行排序，右边的同样

quick_sort(q, l, j);
quick_sort(q, j+1, r);

这里新区域要注意一下：

• 左区域的头部不变，仍然是 l（left），但是尾部就变成了 j，这是上一次右边指针最后指向的位置；

• 右区域的尾部不变，仍然是 r（right），但是头部就变成了 j+1，这是上一次右边指针最后指向的位置后一个。

理由就是：指针 j 最终会停在一个合适的位置，使得 j 左边的元素都小于等于基准元素，j 右边的元素都大于等于基准元素。

还有重要的一点别忘了:
一直在递归下去的话，数组会越来越小，那么什么时候停止呢，便是

if(l >= r) return;

这个意思是：当l >= r 时，意味着当前子数组已经为空或者只有一个元素