計數排序的穩定性

我已經在python中實現了一個計數排序算法。我看到計數排序是穩定的，因爲它保留了原始數組中元素的順序。你認爲下面的實現是穩定的嗎？計數排序的穩定性

def countingsort(A,n): 
     C = [0]*n 
     B = [0]*n 
     # the value of A[i] becomes the index for counting 
     # C now stores the no. of occurences of element A[i] in A 
     for i in A: 
      C[i] = C[i] + 1 
     print i,C 
     # prepare the indexes for reinsertion 
     # Each position in C now holds the range of array position where a value will be placed 
     i = 0 
     while i < n: 
      #print i 
      C[i] = C[i] + C[i-1] 
      i += 1 
     print "Array position for each element",C 
. 
# the stability part of sort ??? 
     for j in xrange(n-1,0,-1): 
      print "j",j,"A[j]:",A[j] 
      B[C[A[j]]-1] = A[j] 
      print B 
      C[A[j]] = C[A[j]] - 1 
      print C 
     print B 
     return B 


    if __name__ == '__main__': 
     A =[0,2,0,1,3,4,6,1,3,2] 
     countingsort(A,len(A))

計數排序在真實世界中的真正用處是什麼？

來源

2015-10-22 Tammy

*「你認爲下面的實現是穩定的嗎？」* - 你測試過了嗎？發生了什麼？ – jonrsharpe

讓我測試字典項目。我嘗試使用整數不能給出正確的圖片，因爲它們都是一樣的。 – Tammy

計數排序是對整數數組進行排序的一種快速方法，它可以從最低有效字節到最高有效字節進行排序，對於32位整數需要4遍，對於64位整數需要8遍。如果數組包含負數有符號整數，則需要修改該算法。 – rcgldr

真實世界中計數排序的真正用途是什麼？

C++ 32位無符號整數的計數/基數排序示例。它使數組遍歷一遍，根據數組中每個整數的字節在矩陣mIndex [] []中創建4組直方圖。接下來它將直方圖轉換爲索引。然後它執行4次基數排序，最低有效字節到最高有效字節。在我的系統上，英特爾2600K 3.4ghz，使用此示例基數排序，排序1,600萬個32位無符號整數大約需要1.5秒，自下而上合併排序大約需要0.5秒。

// a is input array, b is working array 
uint32_t * RadixSort(uint32_t * a, uint32_t *b, size_t count) 
{ 
size_t mIndex[4][256] = {0};   // count/index matrix 
size_t i,j,m,n; 
uint32_t u; 
    for(i = 0; i < count; i++){   // generate histograms 
     u = a[i]; 
     for(j = 0; j < 4; j++){ 
      mIndex[j][(size_t)(u & 0xff)]++; 
      u >>= 8; 
     }  
    } 
    for(j = 0; j < 4; j++){    // convert to indices 
     m = 0; 
     for(i = 0; i < 256; i++){ 
      n = mIndex[j][i]; 
      mIndex[j][i] = m; 
      m += n; 
     }  
    } 
    for(j = 0; j < 4; j++){    // radix sort 
     for(i = 0; i < count; i++){  // sort by current lsb 
      u = a[i]; 
      m = (size_t)(u>>(j<<3))&0xff; 
      b[mIndex[j][m]++] = u; 
     } 
     std::swap(a, b);    // swap ptrs 
    } 
    return(a); 
}

來源

2015-10-23 02:43:19 rcgldr

計數排序的穩定性

回答

相關問題