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

Question

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

3

我被给予了一个作业，要编写一个程序以升序排序一个数组。我做了如下代码：

#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个数字。这个代码可以比我写的更短吗？我希望代码尽可能地短小。任何帮助将不胜感激。谢谢！

- Pruthvi Raj

代码高尔夫和效率是两个不同的事情。哪一个更重要？此外，如果减少SLOC会降低可读性/可维护性，那么这并不是一个好主意。 - C.B.

7

当然，你可以使用标准库函数qsort()编写一个C程序来对一个较短的数组进行排序。 :) 我猜你可能不允许这样做，但是因为它通常是实际程序中最好的方法，所以应该提及它。 - unwind

代码高尔夫优先级更高，不允许使用qsort。 - Pruthvi Raj

如果输入不超过10个数字，为什么声明为a[100]？ - abelenky

我是说这个程序不会被用很多数字进行测试，我只是取了a[100]。 - Pruthvi Raj

显示剩余2条评论

2个回答

4

如果您知道数组元素的范围，一种方法是使用另一个数组来存储每个数组元素的频率（所有元素都应该是int类型: )并打印排序后的数组。我正在发布大量元素（10⁶）。您可以根据需要进行减少。

#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是某个整数。当k=O(n)时，排序的运行时间为Θ(n)。对于每个输入元素x，计数排序确定小于x的元素数量。它使用这些信息将元素x直接放置在其在输出数组中的位置上。例如，如果有17个元素小于x，则x属于输出位置18。我们必须稍微修改此方案以处理具有相同值的几个元素的情况，因为我们不希望将它们全部放在同一位置。在计数排序的代码中，我们假设输入是一个数组A[1...n]，因此A.length=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等人的算法导论。}

- haccks

有趣；当然它有效，但是它不能很好地泛化。它不能处理负整数；它不能处理大于1,000,000的值。它受限于值的范围，而不是数量。你不能将此算法应用于排序浮点数，实际上，对于排序字符串也不起作用。 - Jonathan Leffler

或许 freq 的类型应该被改为 uint16_t *，并且在增加之前将 num 转换为 uint16_t，同时添加适当的偏移量以支持 int16_t 元素 - 鉴于原始类型 int 不能保证更大。你也可以优化掉 if (freq[i]) 这行代码，因为无符号下溢是可以的。 - Arkku

@JonathanLeffler; 同意。我发布了这个答案，考虑到OP想要对一个int数组进行排序。 - haccks

谢谢。那很有帮助 ;) - Pruthvi Raj

1

请注意，如果数组的元素为负数或大于1000000，则此答案中的第一个解决方案不会可靠地工作。由于C语言的特性，有时它可能会意外地看起来像是在这些情况下工作，因此请谨慎。 - Arkku

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jonathan Leffler · Accepted Answer

你有10行代码需要排序。如果允许使用别人的代码（但后续说明表示不可以），你可以编写一个比较函数并调用标准C库中的qsort()函数来实现排序：

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。

显然，如果您需要编写排序算法，则必须比调用qsort()更多地工作。您的算法是冒泡排序。这是最低效的排序技术之一 - 它是O(N²)。您可以查找插入排序（也是O(N²)但比冒泡排序更有效），或选择排序（也是二次的），或Shell排序（非常粗略地为O(N^3/2)），或堆排序（O(NlgN)），或快速排序（平均为O(NlgN)，但最坏情况下为O(N²)），或简介排序。唯一可能比您编写的更短的是插入和选择排序；其他排序将更长，但对于大量数据来说更快。对于像10或100个数字这样的小集合，效率不重要 - 所有排序都可以。但是，当您接近1,000或1,000,000个条目时，排序算法确实很重要。您可以在Stack Overflow上找到许多关于不同排序算法的问题。您可以在维基百科上轻松找到有关所提及的所有算法的信息。

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

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

计数排序：1

计数排序：¹