c - 如何在线性时间内对 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

如果你知道数组元素的范围，一种方法是使用另一个数组来存储每个数组元素的频率(所有元素都应该是 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) 时间内对数组进行排序。

Counting sort :¹

Counting sort assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. When k = O(n), the sort runs in Θ(n) time. Counting sort determines, for each input element x, the number of elements less than x. It uses this information to place element x directly into its position in the output array. For example, if 17 elements are less than x, then x belongs in output position 18. We must modify this scheme slightly to handle the situation in which several elements have the same value, since we do not want to put them all in the same position.

In the code for counting sort, we assume that the input is an array A[1...n] and thus A.length = n. We require two other arrays: the array B[1....n] holds the sorted output, and the array C[0....k] provides temporary working storage.

这个算法的伪代码:

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。内容取自Introduction to Algorithms经过Thomas H. Cormen 等人。