二维数组实现:
class RadixSort {
public:
int* radixSort(int* A, int n) {
// write code here
vector<deque<int> > bucket(10);
int divisor[] = {1,10,100,1000,10000};
for (int i = 0;i < 4;i++) {
for (int j = 0;j < n;j++) {
int unit = (A[j]%divisor[i+1])/divisor[i];
bucket[unit].push_back(A[j]);
}
for (int j = 0, k = 0;j < 10;j++) {
while (!bucket[j].empty()) {
A[k++] = bucket[j].front();
bucket[j].pop_front();
}
}
}
return A;
}
};
10、小范围排序
已知一个几乎有序的数组,几乎有序是指,如果把数组排好顺序的话,每个元素移动的距离可以不超过k,并且k相对于数组来说比较小。
选择改进的堆排序。根据题意,最小值一定在A的前k(0~k-1)个元素内、次小值一定在A的第二组k(1~k)个元素内,以此类推,每次取原数组A的k个元素进行堆排序,然后把堆顶元素放入A的已排序序列中,(0~k-1)排序的堆顶赋值给A[0],(1~k)排序的堆顶赋值给A[1],以此类推。最后剩下A中最后的k个元素(k-n~n-1),进行标准的堆排序,第一次是K个元素的堆,排序后将堆顶赋值给A[n-k],紧接着把堆尾元素赋值给堆顶,再排序,此时只是k-1个元素的堆,依次类推,每次把堆顶元素放入A中已排序序列后,都把堆尾元素赋值到堆顶,同时堆的元素个数减1,直到堆的元素个数为1,整个排序结束。
class ScaleSort {
public:
void heapify(int* B,int i,int k) {
int j,ex;
ex = B[i];
j = 2*i + 1;
while (j < k) {
if (j + 1 < k && B[j + 1] < B[j])
j++;
if (B[j] >= ex) break;
B[i] = B[j];
i = j;
j = 2*i + 1;
}
B[i] = ex;
return;
}
vector<int> sortElement(vector<int> A, int n, int k) {
// write code here
int m = 0,exc;
int *temp = new
int[k];
for (int l = 0;l < k;l++) {
temp[l] = A[l];
}
for (int i = k/2-1;i >= 0;i--)
heapify(temp,i,k);
for (int i = k;i < n;i++) {
A[i-k] = temp[0];
temp[0] = A[i];
heapify(temp,0,k);
}