計數排序 - 實施差異

我聽說過Counting Sort，並根據我的理解編寫了我的版本。計數排序 - 實施差異

public void my_counting_sort(int[] arr) 
    { 
     int range = 100; 
     int[] count = new int[range]; 
     for (int i = 0; i < arr.Length; i++) count[arr[i]]++; 
     int index = 0; 
     for (int i = 0; i < count.Length; i++) 
     { 
      while (count[i] != 0) 
      { 
       arr[index++] = i; 
       count[i]--; 
      } 
     } 
    }

上面的代碼完美的作品。

但是，在CLRS中給出的算法是不同的。下面是我的實現

public int[] counting_sort(int[] arr) 
    { 
     int k = 100; 
     int[] count = new int[k + 1]; 
     for (int i = 0; i < arr.Length; i++) 
      count[arr[i]]++; 
     for (int i = 1; i <= k; i++) 
      count[i] = count[i] + count[i - 1]; 
     int[] b = new int[arr.Length]; 
     for (int i = arr.Length - 1; i >= 0; i--) 
     { 
      b[count[arr[i]]] = arr[i]; 
      count[arr[i]]--; 
     } 
     return b; 
    }

我直接將它從僞代碼翻譯成C＃。該代碼不起作用，我得到一個IndexOutOfRange異常。

所以我的問題是：

這有什麼錯第二一段代碼？
我的幼稚實現和本書給出的算法之間有什麼區別？

來源

2010-09-20 rohit89

你用什麼來輸入'count_sort'的第二個版本？該算法有一些限制，允許輸入值。 – Jacob 2010-09-20 20:31:22

'int [] arr'包含0-100範圍內的整數。我知道如果存在重複的元素，算法將不起作用。 – rohit89 2010-09-20 21:01:56

與您的版本有關的問題是，如果元素具有衛星數據，它將不起作用。

CLRS版本將工作，它是穩定的。

編輯：

這裏是由關鍵的CLRS版本的Python，這種種對（鍵，值）的實現：

def sort(a): 
    B = 101 
    count = [0] * B 
    for (k, v) in a: 
    count[k] += 1 
    for i in range(1, B): 
    count[i] += count[i-1] 
    b = [None] * len(a) 
    for i in range(len(a) - 1, -1, -1): 
    (k, v) = a[i] 
    count[k] -= 1 
    b[count[k]] = a[i] 
    return b  


>>> print sort([(3,'b'),(2,'a'),(3,'l'),(1,'s'),(1,'t'),(3,'e')]) 
[(1, 's'), (1, 't'), (2, 'a'), (3, 'b'), (3, 'l'), (3, 'e')]

來源

2010-09-21 04:17:07

應該

b[count[arr[i]]-1] = arr[i];

我將讓你來追蹤原因;-)。

我不認爲他們執行任何不同。第二個只是推動循環中的計數的相關性，以便在最終循環內簡化一點。就我而言，這沒有必要。你的方式就像直截了當，可能更具可讀性。事實上（我不知道C＃因爲我是一個Java人）我期望你可以用一個庫數組填充替換內部的while循環;是這樣的：

 for (int i = 0; i < count.Length; i++) 
    { 
     arrayFill(arr, index, count[i], i); 
     index += count[i]; 
    }

在Java中的方法是java.util.Arrays.fill(...)。

來源

2010-09-20 20:18:14

的問題是，你有硬編碼的您正在使用的陣列的長度爲100.陣列的長度應爲m + 1，其中m是原始陣列上的最大元素。這是你認爲使用計數排序的第一個原因，如果你有關於數組元素的信息都是次要的，那麼一些常量並且它會很好。

來源

2012-11-03 14:25:16 a0viedo

計數排序 - 實施差異

回答

相關問題