计数排序的稳定性

我已经在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

计数排序的稳定性

回答

相关问题