快速排序思想：
快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。——百度百科；
通俗一点就是：
①：如果数据是链式的，就声明两个指针low high分别指向链表的首尾，如果数据是数组形式，就声明两个值low high分别表示数组的首尾下标。
②：若low所指向的值小于等于high指向的值，则high做自减，如果low指向的值大于high指向的值，则交换low指向的值和high指向的值；
③：若low所指向的值小于等于high指向的值，则low做自加【和步骤二不同】，如果low指向的值大于high指向的值，则交换low指向的值和high指向的值；
④：若low 小于 high 则循环步骤二和步骤三；
⑤：做完以上步骤表示第一次排序成功，然后分割数组，重新对low和high赋值，重复步骤二到步骤四【是个递归过程】。
附上代码：
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 5 void show_arry(int *arry) 6 { 7 int i = 0; 8 int *tmp; 9 tmp = arry; 10 for( ; i < 8; i++) 11 printf("%d ",*tmp++); 12 13 putchar(' '); 14 } 15 16 void change_val(int *a, int *b) 17 { 18 int tmp; 19 tmp = *a; 20 *a = *b; 21 *b = tmp; 22 } 23 24 void sort(int *arry, int low, int high) 25 { 26 int *tmp; 27 int val; 28 int i = low, j = high; 29 if(low >= high) 30 return; 31 tmp = arry; 32 while(low < high){ 33 while(low < high && tmp[low] <= tmp[high]){ 34 high--; 35 } 36 change_val(&tmp[low], &tmp[high]); 37 38 while(low < high && tmp[low] <= tmp[high]) 39 low++; 40 change_val(&tmp[low], &tmp[high]); 41 } 42 43 sort(arry, i, low - 1); //now low = high;you can use high too; 44 45 sort(arry, low + 1, j); 46 } 47 48 int main(int argc, char *argv[]) 49 { 50 int arry[8] = {49,38,65,97,76,13,27,49}; 51 int low,high; 52 53 low = 0; 54 high = 7; 55 show_arry(arry); 56 sort(arry,low,high); 57 show_arry(arry); 58 59 return 0; 60 }
有些代码喜欢定义一个关键字来进行对数组的首尾数据的比较，有助于代码的可读性。笔者写的程序中没有设计到关键字，主要是循环比较tmp[low] 和 tmp[high]只不过一个是low做自加，一个结果是high做自减，效果和使用关键字是相同的！
修改一下sort的代码，改成使用关键字的方式：
1 void sort2(int *arry, int low, int high) 2 { 3 int *tmp; 4 int val; 5 int i = low, j = high; 6 int key = arry[low]; 7 8 if(low >= high) 9 return; 10 tmp = arry; 11 while(low < high){ 12 while(low < high && tmp[high] >= key) 13 high--; 14 tmp[low] = tmp[high]; 15 16 while(low < high && tmp[low] <= key) 17 low++; 18 tmp[high] = tmp[low]; 19 } 20 21 tmp[low] = key; 22 23 sort2(arry, i, low - 1); //now low = high;you can use high too; 24 25 sort2(arry, low + 1, j); 26 }
可以发现用了关键字，则多付出一个int空间，但是减少了对change_val函数的调用，减少了系统的开销。