快速排序法是C.A.R.Hoare于1962年发明的。 对于一个给定的数组，将其按递归方法排序。 快速排序法思路： 1.取数组第中间个数的值，以它为分界线将这个数组分为两个部分。 2.将这个数移到最左边，遍历数组，把小于该值的数移动到该值的左边，大于该值的数不动。 3.记录发生移动的个数a，遍历结束后将所取的中间值置于第a+1个（此时该值左边的数都小于该值，右边的数都大于该值，但左右两边并不是升序排列的）。 4.分别将左右两边视为两个新的数组，重复1-3步，直至数组个数小于2。 程序如下：《c程序设计语言》p74
void qsort (int v[], int left, int right) { int i, last; void swap (int v[], int i, int j);//交换v[i]、v[j]的值 if(left >= right) //判断数组内元素个数小于2 return; swap(v, left, (left + right) / 2);//取数组第中间个数的值，并把这个值移动到最左边 last = left; //记录比该值小的数的个数（其实是位置） for(i = left + 1; i <= right; i++) if(v[i] < v[left]) swap(v, ++last, i); //遍历数组，移动小的到标志值左边 swap(v, left, last); //把标志值移到比他小的数的左边，此时右边的数都比他大 qsort(v, left, last - 1); qsort(v, last + 1, right); //递归 } void swap(int v[], int i, int j)//v[i] v[j]交换函数 { int temp; temp = v[i]; v[i] = v[j]; v[j] = temp; }