快排（二）—-寻找第k小的数

之前的快排采用了一个指针和for循环，这次使用的是双指针，相对比较正规，不过这次是使用快排来实现寻找第k小的数，去掉quickSort里面的判断，可以实现快排。

原来的代码：快排（一）
[c language=”++”]
int partition(vector<int>&arr, int l, int r)
{
int pivot = arr[l];
int i = l + 1;
int j = r;

while (i <= j)
{
while (i <= j&&arr[i] <= pivot)
i++;
while (i <= j&&arr[j] >= pivot)
j–;
if (i <= j)
swap(arr[i], arr[j]);
}
swap(arr[j], arr[l]);
return j;
}

void quickSort(vector<int>&arr, int l, int r,int idx,int&target)
{
if (l > r) return;
int k = partition(arr, l, r);
if (k == idx)
{
target = arr[k];
return;
}
else if (k < idx)
quickSort(arr, k + 1, r, idx, target);
else
quickSort(arr, l, k – 1, idx, target);
}
[/c]