常用排序算法之--快速排序

浏览数：19 / 时间：2015年06月08日

个人认为，数据结构与算法是部分程序员的软肋，而对于非科班出身的程序员来说，更是软肋中的软肋。

纠其原因，大部分是因为作为应用层面的程序开发，算法（尤其是查找算法）并不是影响程序性能的最关键的因素。同时作为一个完整的系统，从数据存储到获取都提供了

相应的调用接口，如果要获取数据，我们只需要调用外部接口就可以了。模块化、工厂化导致了我们对算法的依赖降低了。依赖降低了，就导致这部分知识的退化。只是在找工作的时候，又得重拾这部分代码。唉，不说了，要不然又该挨广大园友们喷了。

欢迎与广大朋友交流学习，qq:792911374

网上介绍快速排序的文章很多，个人认为比较优秀的有：

http://blog.csdn.net/morewindows/article/details/6684558

http://developer.51cto.com/art/201403/430986.htm

下面的内容，适合于看完了上面两篇文章后，思路清晰，但在编写代码过程中又有些疑惑的朋友们.....

其实快速排序算法，就是以一个特定的元素作为基准值，把比它大的元素放在左边，比它小的元素放在右边。第一回快排后，形成的结果是基准值右边的元素都比基准值大，左边的元素都比基准值小。然后把基准值左边和右边的元素分别递归调用快排函数，进行周而复始的排序工作。

需要注意的两点是：

1、基准值要取快排函数中的low(最低索引)的元素，不能取索引为0的元素，博主就是在代码过程中一时疏忽取了0值，桑心了好几个小时^_^

2、high一定是数组元素数减1，从0开始的嘛，地球人都知道的。

编译与调试环境为：qt, c语言代码

上代码：

  1 #include <QCoreApplication>
  2 #include <stdlib.h>
  3 #include <time.h>
  4 //数组数量
  5 const int ARRAY_NUM = 10;
  6 const int CHAR_NUM = 20;
  7 //结构类型信息
  8 struct RecordInfo{
  9     char name[CHAR_NUM];
 10     int key;
 11 };
 12 
 13 //生成待排数组
 14 void genrateArrayList(struct RecordInfo recList[]);
 15 //快速排序主体函数
 16 void quickSort(struct RecordInfo recList[], int low, int high);
 17 //打印排好序的数组
 18 void printArrayList(struct RecordInfo recList[]);
 19 
 20 int main(int argc, char *argv[])
 21 {
 22     QCoreApplication a(argc, argv);
 23     //待排序数组
 24     struct RecordInfo info[ARRAY_NUM];
 25     //生成待排序数组
 26     genrateArrayList(info);
 27     printf("排序之前的顺序为：\r\n");
 28     //打印待排数组
 29     printArrayList(info);
 30     //数组排序
 31     quickSort(info, 0, ARRAY_NUM-1);
 32     printf("排序之后的顺序为：\r\n");
 33     //打印数组内容
 34     printArrayList(info);
 35     return a.exec();
 36 }
 37 
 38 /**
 39   * @函数名：genrateArrayList
 40   * @参数：recList[]要生成的数组
 41   * @返回值：无
 42   * @用途：生成待排数组
 43   * @作者：yangfy
 44   */
 45 void genrateArrayList(struct RecordInfo recList[])
 46 {
 47     for(int i = 0; i < ARRAY_NUM; i++){
 48         if(i % 3 == 0 && i > 0){
 49             recList[i].key = recList[i - 3].key;
 50         }
 51         else{
 52             //srand(time(NULL));
 53             //生成ARRAY_NUM以内的随机数
 54             recList[i].key = rand() % ARRAY_NUM;
 55         }
 56         snprintf(recList[i].name, CHAR_NUM - 1, "第%d个元素。", i);
 57     }
 58 }
 59 
 60 /**
 61   * @函数名：quickSort
 62   * @参数：recList[]待排数组
 63   *       low：排序的开始元素索引
 64   *       high:排序的结束元素索引
 65   * @返回值：无
 66   * @用途：快速排序主体函数
 67   * @作者：yangfy
 68   */
 69 void quickSort(struct RecordInfo recList[], int low, int high)
 70 {
 71     //高值如果等于低值，则退出不用比较了。
 72     if(low < high){
 73         int i = low, j = high;
 74         //枢轴记录(也就是记录被覆盖之前的值),通常是第1个元素
 75         struct RecordInfo pivotInfo;
 76         pivotInfo = recList[low];
 77         while (i < j) {
 78             //找到比基准值小的索引
 79             while (i < j && recList[j].key >= pivotInfo.key)
 80                 j--;
 81             if(i < j){
 82                 //把j的值赋予i，同时把i加1
 83                 recList[i++] = recList[j];
 84             }
 85             //找到比基准值大的元素
 86             while (i < j && recList[i].key <= pivotInfo.key) {
 87                 i++;
 88             }
 89             if(i < j){
 90                 //把i的值赋予j,同时把j减1
 91                 recList[j--] = recList[i];
 92             }
 93         }
 94         //把准值赋予i,此时i左边的元素比基准值小，右边的比基准值大
 95         recList[i] = pivotInfo;
 96         //对基准值左边的元素进行递归排序，除去基准值i
 97         quickSort(recList, low, i - 1);
 98         //对基准值右边的元素进行递归排序,除去基准值i
 99         quickSort(recList, i + 1, high);
100     }
101 }
102 /**
103   * @函数名：printArrayList
104   * @参数：recList[] 要打印的数组
105   * @返回值：无
106   * @用途：打印数组
107   * @作者：yangfy
108   */
109 void printArrayList(struct RecordInfo recList[])
110 {
111     for(int i = 0; i < ARRAY_NUM; i++){
112         printf("第%d个元素的索引为：%d, ->：%s\r\n", i, recList[i].key, recList[i].name);
113     }
114 }