之前的快排采用了一个指针和for循环,这次使用的是双指针,相对比较正规,不过这次是使用快排来实现寻找第k小的数,去掉quickSort里面的判断,可以实现快排。
原来的代码:快排(一)
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); }