快排
1. 要點:
**i. partition: **將整個數(shù)組切成兩片淤堵，切片返回index:
[l, h] ==> [l,index-1], index, [index+1, h]
ii. 遞歸partition
2. 具體偽代碼
i. partition
key = nums[l];
i=l;
j=h;
while(i < j) {
每個loop 目標找到一對i, j; 使得nums[i] > key > nums[j]
尋找方法：
沿著<-------- j-- 方向找比key 小的位置逼侦，就找到了j;
沿著---------> i++ 方向找 比key 大的位置试躏，就找到了i;
找到后，交換swap nums[i],nums[j]
}
最后nums[i]=key
ii. 遞歸的sort [l, index-1]和 sort [index+1,h]
3.實現(xiàn)代碼
int partition(int *nums, int l, int h)
{
int i=l;
int j=h;
int key = nums[l];
while(i < j) {
while(i<j && key < nums[j]) j--;
while(i<j && key > nums[i]) i++;
swap(&nums[i], &nums[j]);
}
nums[i]=key;
return i;
}
void quicksort(int *nums, int l, int h)
{
if (l < h) {
int index = partition(nums, l, h);
quicksort(nums, l, index -1 );
quicksort(nums, index +1, h);
}
}
