對於大型表格奇怪的慢速排列

Question

我一直在做我的作業，這是比較一堆排序算法，我遇到了一個奇怪的現象。事情一直如預期的那樣：insertionsort贏得了20個int表，否則quicksort勝過heapsort和mergesort。最多500,000英鎊（存儲在內存中）。對於5,000,000個整數（仍然保存在內存中），quicksort會突然變差，然後會出現heapsort和mergesort。數字總是隨機分佈的，窗口虛擬內存關閉。任何人都有一個想法可能是什麼原因呢？

 void quicksortit(T *tab,int s) { 
        if (s==0 || s==1) return; 
        T tmp; 
        if (s==2) { 
         if (tab[0]>tab[1]) { 
             tmp=tab[0]; 
             tab[0]=tab[1]; 
             tab[1]=tmp; 
             } 
         return; 
         } 
        T pivot=tab[s-1]; 
        T *f1,*f2; 
        f1=f2=tab; 
        for(int i=0;i<s;i++) 
          if (*f2>pivot) 
           f2++; 
          else { 
           tmp=*f1; 
           *f1=*f2; 
           *f2=tmp; 
           f1++; f2++; 
           } 
        quicksortit(tab,(f1-1)-tab); 
        quicksortit(f1,f2-f1); 
    }; 

Answer 1

當算法中存在許多重複項時，算法開始失敗。你只注意到這個數值很大，因爲你一直在提供算法的隨機值，這些值有很大的跨度
（我假設你使用rand（）：0 - RAND_MAX），並且這個問題只出現在大數組中。

當您嘗試對相同數字的數組進行排序（嘗試排序100000個相同的數字時，程序將崩潰），您將首先遍歷整個數組，過多地交換元素。然後，你陣列分成兩個，但是大陣列只被降低1：

    v 
quicksortit(tab,(f1-1)-tab); 

因此你的算法變得爲O（n^2），並且還消耗非常大量的堆疊。尋找一個更好的支點，在這種情況下不會幫助你，而是選擇一個沒有表現出這個缺陷的quicksort（）版本。

例如：

function quicksort(array) 
    if length(array) > 1 
     pivot := select middle, or a median of first, last and middle 
     left := first index of array 
     right := last index of array 
     while left <= right 
      while array[left] < pivot 
       left := left + 1 
      while array[right] > pivot 
       right := right - 1 
      if left <= right 
       swap array[left] with array[right] 
       left := left + 1 
       right := right - 1 
     quicksort(array from first index to right) 
     quicksort(array from left to last index) 

這是修改後的版本：http://rosettacode.org/wiki/Sorting_algorithms/Quicksort

Answer 2

這可能是您的陣列現在比L3緩存大。

快速排序分區操作將隨機元素從數組的一端移動到另一端。典型的Intel L3緩存就像8MB一樣。使用5M 4字節元素 - 您的數組爲20MB。你從一端寫到另一端。

緩存未命中L3轉到主內存，可能是太多比較高級別的緩存未命中更慢。

到目前爲止，您的整個排序操作完全在CPU內運行。