數組排序，找到最初的20數量最少

Question

可能重複：
Algorithm to find k smallest numbers in array of n items

你如何找到一個非常大的數組中的第20個最小的元素？

Answer 1

不確定它是否是最優的，但您可以嘗試運行20次迭代的無用排序。

Answer 2

你有兩個選擇

1. 排序的陣列和拉小端的20個元素（取決於你整理排列的方向上，對吧？）
2. 保持一個有序集合（可能不由於數組的非唯一性而導致的一組）。添加數組中的前20個元素。每當你找到一個小於'好集'中的最高元素時，用這個新元素替換最高元素。

第二個看起來較慢，但它確實取決於數組的大小。你可以在數組中通過一次，所以最好在一個80億的數組上做這件事。

編輯：第一個算法是O(n lg n)。第二種算法是O(k n)，其中k在這種情況下是20（您希望前20）。因此，第二種算法在lg n > 20或n > 2^20或n > ~1 million時速度更快。所以如果你有不到一百萬的話，你最好在排序。如果你有超過一百萬的話，你最好做外部列表並通過一次通過。

Answer 3

看在上帝的份上，不要整個排列。將大小爲20的數組初始化爲大數組的前20個元素。現在，通過大數組，逐步替換小數組中的任何元素，大於當前考慮的大數組中的元素。這是O（n）;比任何基於比較的排序都要好，並且可能比線性排序（無論如何總是不能被使用）更高效（具有良好的實現）。

編輯：

所以，出於好奇的，我實現的線性算法的幼稚版本，並將其相比於C++ STL sort（）函數。這裏是我的結果 - 他們表明，如我所料，線性算法平均總是優於排序 - 即使在線性算法的理論最壞情況下，您也需要一個更大的數組才能獲勝。這是我的性能數據：

 N  Sort  Linear  Common 
     32,  378,  170,  116 
     64,  831,  447,  237 
     128,  1741,  1092,  424 
     256,  5260,  2211,  865 
     512,  10955,  5944,  1727 
    1024,  20451,  10529,  3584 
    2048,  38459,  21723,  7011 
    4096,  77697,  41023,  14136 
    8192,  150630,  82919,  28083 
    16384,  311593,  166740,  55978 
    32768,  648331,  334612,  111891 
    65536, 1329827,  673030,  224665 
    131072, 2802540, 1342430,  449553 
    262144, 5867379, 2717356,  896673 
    524288, 12082264, 5423038, 1798905 
    1048576, 25155593, 10941005, 3658716 
    2097152, 62429382, 24501189, 8940410 
    4194304, 120370652, 44820562, 14843411 

N是問題的大小，排序是在微秒的排序時間，線性是以微秒爲線性算法時間，和常見的是花費每個試驗之前隨機化的陣列的時間。請注意，要獲得只需在排序和線性算法中花費的時間，您需要從第二列和第三列中的值中減去第四列中的值。如果你希望我這樣做，我會很高興。儘管如此，顯然線性比排序更快。每個N被測試100次，這些都是來自所有100個測試的總計數字（總計時間）。下面是我使用的代碼：

void randomize(unsigned char *data, int n) { 
    for(int i = 0; i < n; i++) 
     data[i] = (unsigned char)(rand() % 256); 

    } 

    void sorttest(unsigned char *data, int n) { 
    unsigned char results[20]; 
    sort(data, data + n); 
    for(int i = 0; i < 20; i++) 
     results[i] = data[i]; 
    } 

    void scantest(unsigned char *data, int n) { 
    unsigned char results[20]; 
    for(int i = 0; i < 20; i++) 
     results[i] = data[i]; 

    for(int i = 20; i < n; i++) 
     for(int j = 0; j < 20; j++) 
      if(data[i] < results[j]) { 
       results[j] = data[i]; 
       break; 
      } 
    } 


    void dotest(int n) 
    { 
    unsigned char *data = (unsigned char*)malloc(n); 
    timeval t1, t2, t3, t4, t5, t6; 

    gettimeofday(&t1, 0); 
    for(int i = 0; i < 100; i++) { 
     randomize(data, n); 
     sorttest(data, n); 
    } 
    gettimeofday(&t2, 0); 


    gettimeofday(&t3, 0); 
    for(int i = 0; i < 100; i++) { 
     randomize(data, n); 
     scantest(data, n); 
    } 
    gettimeofday(&t4, 0); 

    gettimeofday(&t5, 0); 
    for(int i = 0; i < 100; i++) 
     randomize(data, n); 
    gettimeofday(&t6, 0); 

    int dt1 = 1000000*(t2.tv_sec - t1.tv_sec) + (t2.tv_usec - t1.tv_usec); 
    int dt2 = 1000000*(t4.tv_sec - t3.tv_sec) + (t4.tv_usec - t3.tv_usec); 
    int dt3 = 1000000*(t6.tv_sec - t5.tv_sec) + (t6.tv_usec - t5.tv_usec); 
    printf("%10d, %10d, %10d, %10d\n", n, dt1, dt2, dt3); 
    free(data); 
    } 

    int main() { 
    srand(time(0)); 
    for(int i = 32; i < 5000000; i*=2) dotest(i); 
    return 0; 
    } 

我邀請任何人誰聲稱，排序是一樣好地指出，這樣的排序出來頂上我如何修改這個基準要更公平/正確。不完全是;請隨時嘗試一下。

Answer 4

如果數組非常大，排序需要很長時間和很多空間。

你需要什麼：

• 複製數組A的第20個元素到新數組B.

• 排序乙

• 走過去數組A對於每個元素檢查它是否小於 B [19]

• 如果是=>將它添加到B，排序B，刪除最後一個ele B