编程问题…………

设有关键码序列（66,13,51,76,81,26,57,69,23），要按关键码值递增的次序排序，若采用快速排序法，并以第一个元素为划分的基准，那么第一趟划分后的结果为（）

答案是：（23,13,51,57,66,26，81,69,76）

我就想问一下，这些小于66的数在左边，大于66的数在右边之后   左右的那些数的顺序是怎么排的，即23,13,51,57              26，81,69,76   为什么是这个顺序？

给你个我们上这个递归快排的资料，看了就能明白的

2. 快速排序设计要点

快速排序又称为分区交换排序，其基本思想是分治，即分而治之：在待排序的n个数据r[1,2,…,n]中任取一个数（例如r[1]）作为基准，把其余n-1个数据分为两个区，小于基准的数放在左边，大于基准的数放在右边。

这样分成的两个区实际上是待排序数据的两个子列。然后对这两个子列分别重复上述分区过程，直到所有子列只有一个元素，即所有元素排到位后，输出排序结果。

分区交换描述如下：

while(i!=j)

    { while(r[j]>=r[0] && j>i)   // 从左至右逐个检查是否大于基准

    j=j-1;

    if(i<j) {r[i]=r[j];i=i+1;} // 把小于基准的一个数赋给r(i)

    while(r[i]<=r[0] && j>i)   // 从右至左逐个检查是否小于基准

       i=i+1;

    if(i<j) {r[j]=r[i];j=j-1;} // 把大于基准的一个数赋给r(j)

    }

为了解分区交换的实施，以具体数据稍加剖析如下。

设n=12，参与排序的12个整数为：

r[1]=25,45,40,13,30,27,56,23,34,41,46,r[12]=52

  调用qk(r,1,12):

i=1,j=12,选用r[1]=25为基准，并赋给r[0]，即r[0]=25，进入1——12实施分区交换的while循环：

  从右至左逐个检查小于基准25的数，至j=8,r[8]=23小于基准，则r[1]=23,i=2；

  从左至右逐个检查大于基准25的数，至i=2,r[2]=45大于基准，则r[8]=45,j=7；

  i=2,j=7,i≠j，继续while循环：

  从左至右逐个检查大于基准25的数，至j=4,r[4]=13小于基准，则r[2]=13,i=3；

  从右至左逐个检查小于基准25的数，至i=3,r[3]=40大于基准，则r[4]=40,j=3；

  i=3,j=3,i=j，结束while循环，由r[i]=r[0]定位基准为r[3]=25。

  至此，完成qk(r,1,12)的分区，即为：

r[1]=23,13,25,40,30,27,56,45,34,41,46,r[12]=52

  进一步调用qk(r,1,2)与qk(r,4,12)，继续细化分区。

  例如调用qk(r,1,2)：

i=1,j=2,选用r[1]=23为基准，并赋给r[0]，即r[0]=23，进入1——2实施分区交换的while循环：

从左至右逐个检查大于基准23的数，至j=2,r[2]=13小于基准，则r[1]=13,i=2；

从右至左未检查出小于基准23的数；

  i=2,j=2,i=j，结束while循环，由r[i]=r[0]定位基准为r[2]=23。

  至此，完成qk(r,1,2)的分区，即为：

r[1]=13,r[2]=23

  而调用qk(r,4,12)，还需作多次分区。

  所有分区完成，即升序排序完成，返回调用qk(r,1,12)处，输出排序结果。

3. 快速排序程序实现

// 递归实现快速排序

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

void main()

{ int i,n,t,r[20001];

  void qk(int r[],int m1,int m2);   // 函数声明

  t=time(0)%1000;srand(t);    //  随机数发生器初始化

  printf("  input n:");

  scanf("%d",&n);

  printf("  参与排序的%d个整数为：\n",n);

  for(i=1;i<=n;i++)

    {r[i]=rand()%(4*n)+10;    // 随机产生并输出n个整数

    printf("%d ",r[i]);

    }

  qk(r,1,n);

  printf("  \n  以上%d个整数从小到大排序为：\n",n);

  for(i=1;i<=n;i++)

    printf("%d ",r[i]);    // 输出排序结果

  printf("\n");

}

void qk(int r[],int m1,int m2)    // 快速排序递归函数

{ int i,j;

  if(m1<m2)

   { i=m1;j=m2;r[0]=r[i];    // 定义第i个数作为分区基准

    while(i!=j)

    { while(r[j]>=r[0] && j>i)   // 从左至右逐个检查是否大于基准

    j=j-1;

    if(i<j) {r[i]=r[j];i=i+1;} // 把小于基准的一个数赋给r(i)

    while(r[i]<=r[0] && j>i)   // 从右至左逐个检查是否小于基准

       i=i+1;

    if(i<j) {r[j]=r[i];j=j-1;} // 把大于基准的一个数赋给r(j)

    }    // 通过循环完成分区

    r[i]=r[0];    // 分区的基准为r(i)

    qk(r,m1,i-1); qk(r,i+1,m2);    // 在两个区中继续分区

   }

 return;

}

4. 快速排序运行示例

input n:20

参与排序的20个整数为：

78 81 25 88 32 59 19 30 72 57 52 27 34 56 69 54 61 42 43 44

以上20个整数从小到大排序为：

19 25 27 30 32 34 42 43 44 52 54 56 57 59 61 69 72 78 81 88

这是快速排序法：

就是以66,为标准:  先从右往左 找 x<66，再从左往右 找x>66

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息