STL经典算法集锦<三>之partition与qsort

## STL经典算法集锦<三>之partition与qsort STL的分割算法主要使用了仿函数来实现。而此处的分割则不，此处实现了两种形式的分割算法：非随机分割算法、随机分割算法(随机算法是在非随机算法的基础上封装而成)。而快速排序则只需简单依赖分割算法就能实现。 **非随机分割算法：** ~~~ int partition(int array[],int left,int right) { //选择最右侧的元素作为分割标准 int index = left; int pivot = array[right]; //将所有小于标准的点移动到index的左侧 for (int i=left; i<right; i++) { if (array[i] < pivot) swap(array[index++],array[i]); } //将标准与index指向的元素交换，返回index，即分割位置 swap(array[right],array[index]); return index; } ~~~ **随机分割算法：** ~~~ int random(int floor,int ceil) { srand(time(0)); return floor+random()%(ceil-floor+1); } int randomizedPartition(int array[],int left,int right) { //随机一个元素作为分割的标准 int i=random(left,right); //将标准移动到最右侧 swap(array[right],array[i]); partition(array,left,right); } ~~~ **快速排序：** ~~~ void qsort(int array[],int left,int right) { if(left<right) { int mid; //mid=randomizedPartition(array,left,right); mid=partition(array,left,right); qsort(array,left,mid-1); qsort(array,mid+1,right); } } ~~~ 两种形式的分割算法的单词输出为： 非随机算法：  随机算法：