nth_element基于修改后的quick_sort实现，无法按预期工作

Question

为了理解quick_sort我正在尝试实现nth_element。
作为测试的基本事实，我正在使用std::nth_element
我的算法在许多输入上失败，例如 a = {6,1,7,5,3,8,2,4,9}
如何解决？

std::random_device dev;
std::mt19937 rng(dev());
int kth_element(vector<long long> a, int l, int r, int k) {
if(l >= r) return a[l];
int i = l, j = r;
uniform_int_distribution<int> dist(l,r);
int X = a[dist(rng)];
while(i < j) {
while(a[i] < X) ++i;
while(a[j] > X) --j;
if(i < j) {
swap(a[i], a[j]);
++i;
--j;
}
}
if(k >= l && k < i)
return kth_element(a, l,i-1,k);
else if (j < k && k <= r)
return kth_element(a,j+1,r,k);
return X;
}
int kth_element(vector<long long> a, int k) {
int n = a.size();
return kth_element(a,0,n-1,k);
}
int main(int argc, char* argv[]) {
vector<long long> a = {1,2,3,4,5,6,7,8,9};
int n = a.size();
for(int i = 0; i < n; ++i)
cout << kth_element(a,i) << 'n';
random_device rd;
mt19937 rng(rd());
shuffle(a.begin(), a.end(), rng);
show_vars(a);
for(int i = 0; i < n; ++i) {
cout << i << ": " << kth_element(a,i);
nth_element(a.begin(), a.begin()+i,a.end());
cout << ", " << a[i] << 'n';
assert(kth_element(a,i) == a[i]);
}
return 0;
}

如果我在循环中进行测试，则更新，算法失败：

int main(int argc, char* argv[]) {
vector<long long> a = {1,2,3,4,5,6,7,8,9};
int n = a.size();
// for(int i = 0; i < n; ++i)
//   cout << kth_element(a,i) << 'n';
random_device rd;
mt19937 rng(rd());
for(int t = 0; t < 1000; ++t) {
shuffle(a.begin(), a.end(), rng);
// show_vars(a);
for(int i = 0; i < n; ++i) {
// show_vars(i);
long long kth = kth_element(a,i);
cout << i << ": " << kth;
nth_element(a.begin(), a.begin()+i,a.end());
cout << ", " << a[i] << 'n';
// show_vars(kth, a[i]);
assert(kth == a[i]);
}
}
return 0;
}

Answer 1

如果有人试图实现基于 Hoar 分区的nth_element：

使用 2 个指针 i，j 并保持循环不变性：对于 k = 0..i-1 a[k] <= X
和对于 z = j+1 .. n-1 a[z]>= X
循环后，数组可能以 2 种方式进行分区：...|
j | i |...
或 ...|J |X |我 |... 所有在 [L，j] 中带有 idx 的元素(左侧部分( <= X 在 [i，R] 中带有 idx(右侧(>= X

基于左侧/右侧部分中的元素数量在所需路径上重复出现

std::random_device dev;
std::mt19937 rng(dev());
long long kth(vector<long long>& a, int L, int R, int k) {
if(L>=R) return a[L];
int i = L,j = R;
std::uniform_int_distribution<std::mt19937::result_type> dist(L,R);
long long X = a[dist(rng)];
while(i <= j) {
while(a[i] < X) ++i;
while(a[j] > X) --j;
if(i <= j) {
swap(a[i], a[j]);
++i;
--j;
}
}

if(k <= j)
return kth(a, L,j,k);
if (k >=i)
return kth(a,i,R,k);
return X;
}