首页 > 编程笔记 > C语言笔记 > C语言编程实例

C语言快速排序算法

用快速排序法对一组数据由小到大进行排序，数据分别为 99、45、12、36、69、22、62、 796、4、696。

实现过程：

(1)自定义一个函数 qusort()，实现快速排序。

(2) main() 函数为程序的入口函数。程序代码如下：
  1. #include <stdio.h>
  2. int qusort(int s[],int start,int end)    //自定义函数 qusort()
  3. {
  4.     int i,j;    //定义变量为基本整型
  5.     i=start;    //将每组首个元素赋给i
  6.     j = end;    //将每组末尾元素赋给j
  7.     s[0]=s[start];    //设置基准值
  8.     while(i<j)
  9.     {
  10.         while(i<j&&s[0]<s[j])
  11.         j--;    //位置左移
  12.         if(i<j)
  13.         {
  14.             s[i]=s[j];    //将s[j]放到s[i]的位置上
  15.             i++;    //位置右移
  16.         }
  17.         while(i<j&&s[i]<=s[0])
  18.             i++;    //位置左移
  19.         if(i<j)
  20.         {
  21.             s[j]=s[i];    //将大于基准值的s[j]放到s[i]位置
  22.             j--;    //位置左移
  23.         }
  24.     }
  25.     s[i]=s[0];    //将基准值放入指定位置
  26.     if (start<i)
  27.         qusort(s,start,j-1);    //对分割出的部分递归调用qusort()函数
  28.     if (i<end)
  29.         qusort(s,j+1,end);
  30.     return 0;
  31. }
  32.  
  33. int main()
  34. {
  35.     int a[11], i;    //定义数组及变量为基本整型
  36.     printf("请输入10个数：\n");
  37.     for(i=1;i<=10;i++)
  38.         scanf("%d",&a[i]);    //从键盘中输入10个要进行排序的数
  39.     qusort(a,1,10);    //调用qusort()函数进行排序
  40.     printf("排序后的顺序是：\n");
  41.     for(i=1;i<=10;i++)
  42.         printf("%5d",a[i]);    //输出排好序的数组
  43.     printf("\n");
  44.     return 0;
  45. }

运行结果：

请输入10个数：
99 45 12 36 69 22 62 796 4 696
排序后的顺序是：
    4   12   22   36   45   62   69   99  696  796

技术要点：

快速排序是冒泡排序的一种改进，主要的算法思想是在待排序的 n 个数据中取第一个数据作为基准值，将所有记录分为 3 组，使第一组中各数据值均小于或等于基准值，第二组做基准值的数琚，第三组中各数据值均大于或等于基准值。这便实现了第一趟分割，然后再对第二组和第兰组分别重复上述方法，依次类推，直到每组中只有一个记录为止。