## 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);
}
}
~~~
兩種形式的分割算法的單詞輸出為:
非隨機算法:

隨機算法:

- 前言
- STL經典算法集錦
- STL經典算法集錦<一>之list::sort
- STL經典算法集錦<二>之堆算法
- STL經典算法集錦<三>之partition與qsort
- STL經典算法集錦<四>之rotate
- STL經典算法集錦<五>之查找(lower_bound/upper_bound/binary_search)
- STL經典算法集錦<六>之排列(next_permutation/prev_permutation)
- STL經典算法集錦<七>之隨機洗牌(random_shuffle)
- STL經典算法集錦<八>之IntroSort