如何在线性时间内对int数组进行排序？

Question

我被要求做一个按升序对数组进行排序的程序。我这样做了：

#include <stdio.h>
int main()
 {
    int a[100],i,n,j,temp;
    printf("Enter the number of elements: ");
    scanf("%d",&n);
    for(i=0;i<n;++i)
      {
       printf("%d. Enter element: ",i+1);
       scanf("%d",&a[i]);
     }
    for(j=0;j<n;++j)
    for(i=j+1;i<n;++i)
     {
         if(a[j]>a[i])
          {
             temp=a[j];
             a[j]=a[i];
             a[i]=temp;
         }
    }
    printf("Ascending order: ");
    for(i=0;i<n;++i)
        printf("%d  ",a[i]);
    return 0;
}

输入不会超过10个数字。这可以用比我这里更少的代码完成吗？我希望代码尽可能短。任何帮助都将不胜感激。谢谢！

Answer 1

您有10行进行排序。如果允许您使用其他人的工作（后续注释表明您不能这样做），您可以通过编写比较器函数并调用标准C库qort（）函数来减少这种情况：

static int compare_int(void const *v1, void const *v2)
{
    int i1 = *(int *)v1;
    int i2 = *(int *)v2;
    if (i1 < i2)
        return -1;
    else if (i1 > i2)
        return +1;
    else
        return 0;
}

然后呼叫是：

qsort(a, n, sizeof(a[0]), compare_int);

现在，我这样编写函数是有原因的。特别是，它避免了写这个不会的算术溢出：

static int compare_int(void const *v1, void const *v2)
{
    return *(int *)v1 - *(int *)v2;
}

此外，原始模式推广到比较结构等。您比较第一个字段的不等式以返回适当的结果；如果第一个字段不相等，则比较第二个字段；然后是第三个，然后是N^th，只有在每次比较都显示值相等时才返回0。

显然，如果您应该编写排序算法，那么您必须比调用qort（）做更多的工作。您的算法是气泡排序。这是最低效的排序技术之一——它是O（N²）。您可以查找插入排序（也是O（N²）），但比气泡排序更有效），或选择排序（也是二次），或Shell排序（非常粗略地O（N^3/2）），或堆排序（O（NlgN）），或平均快速排序（O（NlgN），但在最坏的情况下为O（N²），或Intro排序。唯一可能比你写的短的是插入和选择排序；对于大量数据，其他的会更长，但速度更快。对于10或100个数字这样的小集合，效率并不重要——所有的排序都可以。但是当你面对1000或100万个条目时，排序算法真的很重要。你可以在Stack Overflow上找到很多关于不同排序算法的问题。你可以很容易地在维基百科上找到提到的任何和所有算法的信息。

顺便提一下，如果输入不超过10个数字，则不需要大小为100的数组。

Answer 2

如果您知道数组元素的范围，一种方法是使用另一个数组来存储每个数组元素的频率（所有元素都应该是int），并打印排序后的数组。我张贴了大量的元素（106）。您可以根据需要减少：

#include <stdio.h>
#include <malloc.h>

int main(void){
    int t, num, *freq = malloc(sizeof(int)*1000001);

    memset(freq, 0, sizeof(int)*1000001);   // Set all elements of freq to 0
    scanf("%d",&t);                         // Ask for the number of elements to be scanned (upper limit is 1000000)

    for(int i = 0; i < t; i++){
        scanf("%d", &num);
        freq[num]++;
    }

    for(int i = 0; i < 1000001; i++){
        if(freq[i]){
            while(freq[i]--){
                printf("%d\n", i);
            }
        }
    }
}  

该算法可以进一步修改。修改后的版本称为计数排序，它在θ（n）时间内对数组进行排序。

计数排序假设对于某些整数，每个输入元素都是0到k范围内的整数。当k=O（n）时，排序以时间运行。计数排序确定每个输入元素x小于x的元素数。它使用此信息将元素x直接放置到其在输出数组中的位置。例如，如果17个元素小于x，则x属于输出位置18。我们必须稍微修改此方案，以处理多个元素具有相同值的情况，因为我们不想将它们全部放在同一位置。

在计数排序的代码中，我们假设输入是一个数组A[1... n]，因此A. long=n。我们需要另外两个数组：数组B[1...... n]保存已排序的输出，数组C[0...... k]提供临时工作存储。

此算法的伪代码：

for i ← 1 to k do
c[i] ← 0
for j ← 1 to n do
    c[A[j]] ← c[A[j]] + 1
//c[i] now contains the number of elements equal to i
for i ← 2 to k do
    c[i] ← c[i] + c[i-1]
// c[i] now contains the number of elements ≤ i
for j ← n downto 1 do
    B[c[A[i]]] ← A[j]
    c[A[i]] ← c[A[j]] - 1  

_{1.内容摘自Thomas H. Cormen等人的《算法导论》。}