Question

关于C++中快速排序的一个问题，大家来看看啊~~

给定一个关键字序列（24,19,32,43,38,6,13,22），进行快速排序，扫描一趟的结果是——————————
答案：（22,19,13,6,24,38,43,32）
能解释一下为什么吗？？越详细越好~~谢谢了

Answer 1

常规的快速排序是这样的：
1、从序列中选第一个关键字，作为筛选关键字。在此处为24
2、比24小的在24前面，比24大的在24后面
3、这样就完成了第一趟排序
4、接着以后每趟都是把24前面的数和24及24后面的数分为两块，分别用以上步骤再排序一次。
5、直到所有粒度都为长度1或2（就是无序再划分为止）.

第一趟如下：
（24,19,32,43,38,6,13,22）
（（24）,19,32,43,38,6,13,22）
（19,（24）,32,43,38,6,13,22）
（19,6,（24）,32,43,38,13,22）
（19,6,13,（24）,32,43,38,22）
（19,6,13,22（24）,32,43,38）

第二趟（把24归为左边）：
分割为两部分：
（19,6,13,22,24 ）（32,43,38）
分别用以上算法：
（（19）,6,13,22,24 ）（（32）,43,38）
（6,（19）,13,22,24 ）（（32）,43,38）
（6,13（19）,22,24 ）（（32）,43,38）

第二趟结束，第三趟把两部哗轮分划分进4部分：
（6,13（19）,22,24 ）（（32）,43,38）
（6,13,19）（22,24） （32） （43,38）
（（6）,13,19）（（22）,24） （（32）） （（43）,38）

第三趟划分了，但没有可以筛选的，进入第四趟，把4部分划分：

（（6）,13,19）（（22）,24） （（32）） （（43）,38）

（（6）,13,19）（（22）,24） （（32）） （（43）,38）

（（6））（（13）,19） （（御芦隐22））（（24）） （（32）） （（43）,38）
（（6））（（13）,19） （（22））（（24）） （（32）） （ 38，（43））

已经全部划分到了最小粒度（每个部分最多2个或者1个数镇厅据）

这时候全部合并：
（6,13,19,22,24,32,38,43）

Answer 2

快速排序基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数森羡据都比另外一此答部分的所有数据都要小，然后再按此方法对此扒拍这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
（24,19,32,43,38,6,13,22）是以首地址数来 分块，所以就变成
（22,19,13,6,24,38,43,32）

Answer 3

你看看 */
#include <stdio.h>

static int a[8] = ;

void swap (int *m, int *n)
{
int temp = *m;
*m = *n;
*n = temp;
}

int partition (int p, int r)
{
int j;
int x = a[r];
int i = p - 1;

for (j=p; j<r; j++)
{
if (a[j] <槐答吵= x)
{
i++;
swap(&a[i], &a[j]);
}
}
swap(&a[i+1], &a[r]);

return i+1;
}

void quicksort (int p, int r)
{
int q;

if (p < r)
{
q = partition (p, r);
quicksort (p, q - 1);
quicksort (q+1, r);
}
}

int main ()
{
int i;
int len = sizeof(a) / 4;

for (i=0; i<len; i++)
printf ("%d ", a[i]);
printf ("\n");

quicksort (0, len - 1);

for (i=0; i<len; i++)
printf ("%d ", a[i]);
printf ("\n");

return 0;
}
/* 我空间里还有一篇文章是关于qsort的，glibc里的源码，我也没怎么看懂，感兴趣可以研究下 */
刚才看了举圆楼铅侍上给出的网址，文章写的不错，里面给的网址对qsort的分析也很透彻，感觉人外有人，学习的路还很长阿。

Answer 4

首先取K1=24为基准，将比24大的关键码移到后面去，将比24小的关键码移到前面。为了节省空间，移动枣仿的方法竖岩歼可采用从两端往中间夹入的方法，即先取出K1，空出前段第一个关键码的位置。用K1，Kn相比较，若Kn>K1，则Kn不动，继续K1与Kn-1的比较；若Kn<=K1，则将Kn移到K1的位置，空出Kn的位余冲置，这时用K1的值再与K2，K3，…相比，找出一个大于K1的关键码，将它移动到后面刚空出的位置，如此往复。