快排

快排

1. 要点:
**i. partition: **将整个数组切成两片，切片返回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.实现代码

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);
  }
}