快速排序法是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; }