有關排序sort

如何在O(N)的時間內,排序range在1到n^2的n個整數

2 個解答

評分
  • 1 0 年前
    最佳解答

    pass1.以(key i) mod n為key實施counting sort或radix sort

    這樣執行【range < n => O(n)】

    pass2.以[key i / n ] mod n為key實施counting sort或radix sort

    這樣執行【range < n => O(n)】

    簡單舉例:

    range為1~10^2 有11、3、88、50、6、27、23

    pass1.

    11mod 10= 1

    3 mod 10= 3

    88 mod 10 = 8

    50 mod 10 = 0

    6 mod 10 = 6

    27 mod 10 = 7

    23 mod 10 = 3

    進行radix sort的話

    50、11、3、23、6、27、88 等於先排個位數

    pass2.

    [50 / 10] mod 10 = 5

    [11 / 10] mod 10 = 1

    [ 3 / 10] mod 10 = 0

    [23 / 10] mod 10 = 2

    [ 6 / 10] mod 10 = 0

    [27 / 10] mod 10 = 2

    [88 / 10] mod 10 = 8

    進行radix sort的話

    3、6、11、23、27、50、88 等於再排十位數

    時間複雜度: radix sort的時間複雜度為 O(d*(n+r))

    (r:基底 n:資料個數 d:最大鍵值位數個數)

    再來討論時間複雜度為

    O(d*(n+n)) + O(d*(n+n))

    = O(dn + dn) + O(dn + dn)

    = O(2dn) + O(2dn) 因為d在這可視為常數

    = O(n) + O(n)

    = O(n)

    推廣如果是range 1~100^2的話

    例如9812這個數

    先從12進行radix sort

    再從98進行radix sort

    range有幾次方就pass幾回 再實施counting sort或radix sort

    因為這不是使用comparison & swap 技巧 所以可以突破 nlogn

    以radix sort來說是使用distribution & merge

    不過要MAX值確定才可以有linear time sorting method

    再來for loop裡面擺n^2 就已經不是O(n)了吧

    2007-02-14 15:20:07 補充:

    用這個方法

    會使用radix sort的話主要是確定最大值位數就夠了

    確定最小值在說明O(n)這裡意義不大

    不過在寫程式上最小值就有意義

    2007-02-14 15:25:43 補充:

    就如 Jacob Lee 所說方法很多

    個人也沒那麼強

    所以在這只用比較基本簡單的sort來說明

  • 1 0 年前

    #include <stdio.h>

    #include <stdlib.h>

    #include <time.h>

    int main(int argc, char **argv)

    { int i, n, n2;

    int *A, *B;

    srand(time(0));

    n = 6;

    n2 = n * n;

    A = (int *) malloc(sizeof(*A) * n);

    B = (int *) malloc(sizeof(*B) * n2 + 1);

    for (i=1; i<=n2; i++)

    B[i] = 0;

    for (i=0; i<n; i++)

    A[i] = rand()%(n*n) +1;

    for (i=0; i<n; i++)

    B[A[i]]++;

    for (i=1; i<=n2; i++)

    if (B[i]) { printf("%4d", i); B[i]--, i--; }

    return 0;

    }

    2007-02-13 13:19:13 補充:

    第一個 Loop:清為 0。

    這是這個方法的大問題:它要O(n^2)!

    第二個 Loop:產生亂數,O(n),但,不應計時。

    第三個 Loop:排序!

    這應該是 O(n) 排序的唯一解!

    我見過好幾次,沒見過另外的解法。

    第四個 Loop:顯示答案。

    main( ) 裡的 int argc, char **argv 可以去掉

    你老師應該是忘了要把 n^2 的部份去掉!

    因為我見過的 O(n) sort 的唯一解,是在 constant range, 不是在 n^2 range。

    2007-02-13 13:20:56 補充:

    你老師應該是忘了要把 n^2 的部份去掉!(我是指時間。)

    你若是碩士,要小心畢業考時的一題:

     這方法為何可以突破 O( n log n) 的上限?

    要準備好如何回答!

    2007-02-13 13:41:17 補充:

    應該說:其它見過的解法都是這解法的變化。

     不是沒見過其它的解法。

    2007-02-13 13:43:25 補充:

    要是沒有人在這裡解出來,而你的老師後來有公佈真正 O(n) 的 sort,請在意見處告知。

    謝謝。

    2007-02-14 07:35:38 補充:

    #include <stdio.h>

    #include <stdlib.h>

    #include <time.h>

    2007-02-14 07:35:44 補充:

    int **dim2(int x, int y)

    { int *buf, **A, i, j;

    if ( A = (int **) malloc(sizeof(int*) * y) ) // if (!NULL)

    if ( buf = (int *) malloc(sizeof(int) * x * y) )

    { for (j=i=0; i<y; i , j =x) A[i] = &buf[j]; }

    else { free(A); A=0; } // Can not alloc the 2nd, free the 1st

    return A;

    }

    2007-02-14 07:37:44 補充:

    int main(int argc, char **argv)

    { int i, j, k, n;

    int *A, *B, *S, **V;

    srand(time(0));

    if (argc==2) n = atoi(argv[1]);

    if (n < 2 || n > 999) n = 5;

    A = (int *) malloc(sizeof(*A) * n);

    for (i=0; i<n; i ) A[i] = rand()%(n*n) 1;

    for (i=0; i<n; i ) printf("M", A[i]);

    printf("\n");

    2007-02-14 07:43:34 補充:

    V = dim2(n, n 1); // 索引陣列

    B = (int *) malloc(sizeof(*B) * (n 1)); // 索引陣列使用量

    S = (int *) malloc(sizeof(*S) * n); // 排序後儲存在這

    2007-02-14 07:46:32 補充:

    // 第一次排序:耗時 O(3n) = O(n)

    for (i=0; i<=n; i ) B[i] = 0; // 索引用量為0, O(n)

    for (i=0; i<n; i ) // 放入索引,O(n)

    { j = A[i]%n;

    V[j][B[j] ] = A[i]; }

    for (i=j=0; i<=n && j<n; i ) // 從索引中取回,O(n)

    { for (k=0; k<B[i]; k ) // 因為 Sigma(i=0~n)B[i] = n。所以,loop i 才會是 O(n)

    S[j ] = V[i][k]; }

    2007-02-14 07:48:04 補充:

    // 第二次排序:耗時 O(n)。註解同上。

    for (i=0; i<=n; i ) B[i] = 0;

    for (i=0; i<n; i )

    { j = S[i]/n;

    V[j][B[j] ] = S[i]; }

    for (i=j=0; i<=n && j<n; i )

    { for (k=0; k<B[i]; k )

    A[j ] = V[i][k]; }

    2007-02-14 07:55:15 補充:

    for (i=0; i<n; i ) printf("M", A[i]); // 印出結果

    return 0;

    }

    這種 sort (radix sort) 需要:

     1. 已知數值上下限。(光知道上限不夠)

     2. 數值總數有上限且不會太大。

    如:

     3 ~ 9 這是有上下限。(上面 1. 在說的是這個)

    但還得要是     (以下是 2. 在說的)

     3, 4, 5, 6, 7, 8, 9

     3.0, 3.1, 3.2, ..., 8.9, 9.0

    不可以是〝實數〞

    2007-02-14 07:58:59 補充:

    我忘了可以給它來個 2次、n次。

    但,我也有說:for (n^2) 就已經不是O(n)了

    2007-02-14 08:02:53 補充:

    第二次補上的程式,是類似 online 的方法,只是稍再簡單一點:

     先把每個值按 Ai % n去排序。

     再把每個值按 Ai / n 去排序。(不用 [(Ai / n) %n])

    2007-02-14 08:29:59 補充:

    不是用比較來排序的排序法至少有:

     格子排序法 (Pigeonhole sort)

     水桶排序法 (Bucket sort)

     計數排序法 (Counting sort)

     LSD基數排序法 (Least Significant Dight first Radix sort)

     MSD基數排序法 (Most Significant Dight first Radix sort)

     延伸排序法(Spread sort)

    這類排序法多數至少在最差狀況下是 O(n);

    Bucket sort 甚至在最差狀況下還是 O(n)!

    所以,方法其實很多。

還有問題?馬上發問,尋求解答。