假设 n 条记录的键在 1 到 k 的范围内。
- 编写一个算法，在 O(n+k) 时间内对记录进行排序。
- 您可以在输入数组之外使用 O(k) 存储。
- 你的算法稳定吗？
如果我们使用计数排序，我们可以在 O(n+k) 时间内完成，并且稳定但不到位。
如果 k=2，它可以就地完成，但它不稳定（使用两个变量来维护数组中 k=0 和 k=1 的索引）
但是对于 k>2，我想不出任何好的算法
问问题
8407 次
4 回答
11
首先，让我们重新讨论计数排序的工作原理：
- 计算要排序的数组中每个键存在的频率。这些计数被写入 size 的数组
k。 - 计算键计数的部分总和。这给出了排序数组中每个相等键的起始位置。
- 将数组中的项目移动到它们的最终位置，增加每个项目的相应 bin 的起始位置。
现在的问题是如何就地执行最后一步。就地排列的标准方法是选择第一个元素并将其与占据正确位置的元素交换。对交换的元素重复此步骤，直到我们找到属于第一个位置的元素（一个循环已完成）。然后对第二、第三等位置的元素重复整个过程，直到处理完整个数组。
计数排序的问题是最终位置不容易获得，而是通过在最终循环中增加每个 bin 的起始位置来计算的。为了永远不会将元素的起始位置增加两次，我们必须找到一种方法来确定某个位置的元素是否已经移动到那里。这可以通过跟踪每个箱的原始起始位置来完成。如果一个元素位于原始起始位置和 bin 的下一个元素的位置之间，则它已经被触摸过。
这是 C99 中的一个实现，O(n+k)它只需要两个大小的数组k作为额外的存储空间。最后的置换步骤是不稳定的。
#include <stdlib.h>
void in_place_counting_sort(int *a, int n, int k)
{
int *start = (int *)calloc(k + 1, sizeof(int));
int *end = (int *)malloc(k * sizeof(int));
// Count.
for (int i = 0; i < n; ++i) {
++start[a[i]];
}
// Compute partial sums.
for (int bin = 0, sum = 0; bin < k; ++bin) {
int tmp = start[bin];
start[bin] = sum;
end[bin] = sum;
sum += tmp;
}
start[k] = n;
// Move elements.
for (int i = 0, cur_bin = 0; i < n; ++i) {
while (i >= start[cur_bin+1]) { ++cur_bin; }
if (i < end[cur_bin]) {
// Element has already been processed.
continue;
}
int bin = a[i];
while (bin != cur_bin) {
int j = end[bin]++;
// Swap bin and a[j]
int tmp = a[j];
a[j] = bin;
bin = tmp;
}
a[i] = bin;
++end[cur_bin];
}
free(start);
free(end);
}
编辑：k这是基于 Mohit Bhura 方法的仅使用单个大小数组的另一个版本。
#include <stdlib.h>
void in_place_counting_sort(int *a, int n, int k)
{
int *counts = (int *)calloc(k, sizeof(int));
// Count.
for (int i = 0; i < n; ++i) {
++counts[a[i]];
}
// Compute partial sums.
for (int val = 0, sum = 0; val < k; ++val) {
int tmp = counts[val];
counts[val] = sum;
sum += tmp;
}
// Move elements.
for (int i = n - 1; i >= 0; --i) {
int val = a[i];
int j = counts[val];
if (j < i) {
// Process a fresh cycle. Since the index 'i' moves
// downward and the counts move upward, it is
// guaranteed that a value is never moved twice.
do {
++counts[val];
// Swap val and a[j].
int tmp = val;
val = a[j];
a[j] = tmp;
j = counts[val];
} while (j < i);
// Move final value into place.
a[i] = val;
}
}
free(counts);
}
于 2013-03-30T15:04:42.533 回答
4
这是我在 O(n+k) 时间内运行的代码，并且仅使用 1 个额外的大小为 k 的数组（除了大小为 n 的主数组）
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main(int argc, char const *argv[])
{
int n = atoi(argv[1]);
int k = atoi(argv[2]);
printf("%d\t%d",n,k);
int *a,*c;
int num,index,tmp,i;
a = (int*)malloc(n*sizeof(int));
c = (int*)calloc(k,sizeof(int));
srand(time(NULL));
for(i=0;i<n;i++)
{
num = (rand() % (k));
a[i] = num;
c[num]++;
}
printf("\n\nArray is : \n");
for(i=0;i<n;i++)
{
printf("\t%d",a[i]);
if(i%8==7)
printf("\n");
}
printf("\n\nCount Array is : \n");
for(i=0;i<k;i++)
{
printf("\t%d(%d)",c[i],i);
if(i%8==7)
printf("\n");
}
//Indexing count Array
c[0]--;
for(i=1;i<k;i++)
{
c[i] = c[i-1] + c[i];
}
printf("\n\nCount Array After Indexing is : \n");
for(i=0;i<k;i++)
{
printf("\t%d(%d)",c[i],i);
if(i%8==7)
printf("\n");
}
// Swapping Elements in Array
for(i=0;i<n;i++)
{
index = c[a[i]];
//printf("\na[%d] = %d, going to position %d",i,a[i],index);
c[a[i]]--;
if(index > i)
{
tmp = a[i];
a[i] = a[index];
a[index] = tmp;
i--;
}
}
printf("\n\n\tFinal Sorted Array is : \n\n");
for(i=0;i<n;i++)
{
printf("\t%d",a[i]);
if(i%8==7)
printf("\n");
}
printf("\n\n");
return 0;
}
即使这个算法也不稳定。所有元素的顺序相反。
Ps : 键在 0 到 (k-1) 的范围内
于 2014-08-27T06:51:31.553 回答
0
整数值序列的示例。排序不稳定。虽然它不像 Mohit 提供的答案那么简洁，但通过跳过已经在正确 bin 中的元素（时间渐近相同），它的速度略快（对于 k << n 的常见情况）。在实践中，我更喜欢 Mohit 的排序，因为它的循环更紧凑、更简单。
def sort_inplace(seq):
min_ = min(seq)
max_ = max(seq)
k = max_ - min_ + 1
stop = [0] * k
for i in seq:
stop[i - min_] += 1
for j in range(1, k):
stop[j] += stop[j - 1]
insert = [0] + stop[:k - 1]
for j in range(k):
while insert[j] < stop[j] and seq[insert[j]] == j + min_:
insert[j] += 1
tmp = None
for j in range(k):
while insert[j] < stop[j]:
tmp, seq[insert[j]] = seq[insert[j]], tmp
while tmp is not None:
bin_ = tmp - min_
tmp, seq[insert[bin_]] = seq[insert[bin_]], tmp
while insert[bin_] < stop[bin_] and seq[insert[bin_]] == bin_ + min_:
insert[bin_] += 1
使用更紧密的循环但仍然跳过已经重新定位的元素：
def dave_sort(seq):
min_ = min(seq)
max_ = max(seq)
k = max_ - min_ + 1
stop = [0] * k
for i in seq:
stop[i - min_] += 1
for i in range(1, k):
stop[i] += stop[i-1]
insert = [0] + stop[:k - 1]
for meh in range(0, k - 1):
i = insert[meh]
while i < stop[meh]:
bin_ = seq[i] - min_
if insert[bin_] > i:
tmp = seq[insert[bin_]]
seq[insert[bin_]] = seq[i]
seq[i] = tmp
insert[bin_] += 1
else:
i += 1
编辑：Mohit 在 Python 中的方法带有额外的位来验证对排序稳定性的影响。
from collections import namedtuple
from random import randrange
KV = namedtuple("KV", "k v")
def mohit_sort(seq, key):
f = lambda v: getattr(v, key)
keys = map(f, seq)
min_ = min(keys)
max_ = max(keys)
k = max_ - min_ + 1
insert = [0] * k
for i in keys:
insert[i - min_] += 1
insert[0] -= 1
for i in range(1, k):
insert[i] += insert[i-1]
i = 0
n = len(seq)
while i < n:
bin_ = f(seq[i])
if insert[bin_] > i:
seq[i], seq[insert[bin_]] = seq[insert[bin_]], seq[i]
i -= 1
insert[bin_] -= 1
i += 1
def test(n, k):
seq = []
vals = [0] * k
for _ in range(n):
key = randrange(k)
seq.append(KV(key, vals[key]))
vals[key] += 1
print(seq)
mohit_sort(seq, "k")
print(seq)
if __name__ == "__main__":
test(20, 3)
于 2015-11-03T06:47:38.717 回答
0
我真的不知道为什么这里发布的所有源代码都如此不必要地复杂化。
这是一个python解决方案：
def inplaceCtsort(A):
b, e = min(A), max(A)
nelems = e - b + 1
CtsBeforeOrIn = [0]*nelems
for i in A:
CtsBeforeOrIn[i-b] += 1
for i in range(1, nelems):
CtsBeforeOrIn[i] += CtsBeforeOrIn[i-1]
for i in range(0, len(A)):
while i < CtsBeforeOrIn[A[i]-b] - 1:
validPosition = CtsBeforeOrIn[A[i]-b] - 1
A[i], A[validPosition] = A[validPosition], A[i]
CtsBeforeOrIn[A[i]-b] -= 1
于 2020-06-26T16:00:47.057 回答