平均排序/k排序

如果一个数组针对下式成立:

我们就称该数组是k排序的

对上式处理,消去中间项,我们可得,

所以我们只需将

这些位置排序即可.

代码

#include
using namespace std;
//数组大小
#define n 10
//k大小
#define k 2
void k_sort(vector&arr) {
	for (int i = 0; i < k; i++) {
		int s = (arr.size() - i) % k == 0 ? (arr.size() - i) / k : (arr.size() - i) / k + 1;
        //创建临时数组储存A[1...1+k...]
		vectorb(s);
        //提取待排序序列
		for (int j = 0; j < s; j++) {
			b[j] = arr[i + j * k];
		}
        //使用你喜欢的排序方式
		sort(b.begin(), b.end());
        //存储排序结果
		for (int j = 0; j < s; j++) {
			arr[i + j * k] = b[j];
		}
	}
}
int main() {
    //数组创建
	vector A(n,0);
	srand((unsigned)time(NULL));
    //数组随机化
	for (int i = 0; i < n; i++) {
		A[i] = rand() % 100;
	}
	for (auto i : A) {
		cout << i << " ";
	}
	cout << "n";
	k_sort(A, k);
	for (auto i : A) {
		cout << i << " ";
	}
	cout << "n";
    return 0;
}