快速排序
介绍：通过多次划分实现操作
思想：每一趟选择当前说有子序列中的一个关键字（通常是第一个）作为枢轴，将子序列中比枢轴小的移到枢轴前边，比枢轴大的移到枢轴后边；当本趟所有子序列都被枢轴以规则划分完毕后会得到一组更短的子序列，它们成为下一趟划分的初始序列集
int quicksort(int R[],int low,int high) { int temp; int i=low,j=high; if(low<high) { temp=R[low]; while(i<j) { while(j>i&&R[j]>=temp) { --j;//右往左扫描 ，找第一个小于temp的 } if(i<j) { R[i]=R[j];//第一个比temp小的放在temp的左边 ++i;//低位i后移1位 } while(i<j&&R[i]<temp) { ++i;//从左往右扫描 ，找到第一个比temp大的 } if(i<j) { R[j]=R[i];//第一个比temp大的放在temp右边 --j;//高位j前移1位 } } R[i]=temp; quicksort(R,low,i-1); quicksort(R,i+1,high); //直到i遇到j之后结束，划分为不同的分区 } return 1; }
分治法： 快速排序采用分为治之。
最坏的时间复杂度O(n2) ——这里是平方
最好的时间复杂度O(n*long2n) ——这是以2为底取n的对数
