建议参考这张图和下面的注释来看,图画得很垃圾
顺序是左-》右-》左下-》下-》下-》右上-》下-》下
#include <iostream>
using namespace std;
/*q是传上来的数组 l是0,q[0]就是第一个元素,也就是x(基准数)
* i和j分别代表左指针和右指针,左指针负责找比x小的数,右指针负责找比x大的数
* 因为当两个指针都停下来的时候,会交换两个数值,然后指针各自往前一步,所以i和j分别左移一位
* 如果左指针小于右指针。那么这两个指针就还没有交换,执行while循环
* 先让左指针左移,如果指向的数字小于基准数,满足条件,继续让左指针右移
* 如果大于或者等于基准数,跳出循环,也就是让左指针i停下来
* 接下来移动右指针j,让j指针左移,判断j指针指向的值是不是大于基准数x,如果大于,满足条件,继续左移
* 直到移动到指向不大于x的数,跳出循环,判断左指针i和右指针j的大小,如果i < j,那说明左指针还在右指针的左侧
* 说明二者并没有错开,就把两个指针指向的值进行交换
* 直到二者指向错开,跳出循环
* 再把第一次排好的排序传值到quicksort函数之中,把基准数左边的数进行快速排序,然后再把基准数右边的数进行快速排序
* 这样,我们就把一个数组排好序了
*/
void quicksort(int q[], int l, int r)
{
if (l >= r)
return;
int x = q[l], i = l - 1, j = 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]);
}
quicksort(q, l, j);
quicksort(q, j + 1, r);
}
int main(void)
{
int n;
const int N = 1e6 + 10;
static int q[N];
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &q[i]);
}
quicksort(q, 0, n - 1);
for (int i = 0; i < n; i++)
{
printf("%d ", q[i]);
}
return 0;
}