計數排序 - 效率

Question

我在想如何計算排序，我們如何實現它，實際上是如何算法工程。我被困在一個部分，算法非常簡單易懂，但其中的一部分似乎並不必要。我認爲人們可能會誤會，但似乎每個人都使用相同的方法，所以我在某個地方被誤認了。你能解釋一下嗎？

這是計數從geeksforgeeks

// C Program for counting sort 
#include <stdio.h> 
#include <string.h> 
#define RANGE 255 

// The main function that sort the given string arr[] in 
// alphabatical order 
void countSort(char arr[]) 
{ 
    // The output character array that will have sorted arr 
    char output[strlen(arr)]; 

    // Create a count array to store count of inidividul 
    // characters and initialize count array as 0 
    int count[RANGE + 1], i; 
    memset(count, 0, sizeof(count)); 

    // Store count of each character 
    for(i = 0; arr[i]; ++i) 
     ++count[arr[i]]; 

    // Change count[i] so that count[i] now contains actual 
    // position of this character in output array 
    for (i = 1; i <= RANGE; ++i) 
     count[i] += count[i-1]; 

    // Build the output character array 
    for (i = 0; arr[i]; ++i) 
    { 
     output[count[arr[i]]-1] = arr[i]; 
     --count[arr[i]]; 
    } 

    // Copy the output array to arr, so that arr now 
    // contains sorted characters 
    for (i = 0; arr[i]; ++i) 
     arr[i] = output[i]; 
} 

// Driver program to test above function 
int main() 
{ 
    char arr[] = "geeksforgeeks";//"applepp"; 

    countSort(arr); 

    printf("Sorted character array is %s\n", arr); 
    return 0; 
} 

酷排序的代碼，但是這個部分：

// Build the output character array 
     for (i = 0; arr[i]; ++i) 
     { 
      output[count[arr[i]]-1] = arr[i]; 
      --count[arr[i]]; 
     } 

爲什麼我需要這個？好吧，我算我的號碼：

比方說，我有數組 - > [1，3，6，3，2，4]

  INDEXES  0 1 2 3 4 5 6 
    I created this -> [0, 1, 1, 2, 1, 0, 1] 

比這部分做到這一點：

[0, 1+0, 1+1, 2+2, 4+1, 0+5, 1+5] 
    [0, 1, 2, 4, 5, 5, 6] 

但爲什麼 ？？

不能我只是用我的數組像以前那樣的人嗎？這是我的想法和我的代碼，請解釋爲什麼它是錯誤的，或者爲什麼其他方式更有用。

void countingSort (int *arr) { 

    int countingArray[MAX_NUM] = {0}; 

    for (i = 0 ; i < ARRAY_SIZE ; i++) 
     countingArray[arr[i]]++; 

    int output_Index = 0; 

    for (i = 0 ; i < MAX_NUM ; i++) 
     while (countingArray[i]--) 
      arr[output_Index++] = i; 
} 

Answer 1

對於排序整數數組的簡單情況，您的代碼更簡單，更好。

然而，計數排序是要排序的通用排序算法，可以挑選基於從項目得到的分選鍵，用於對它們進行比較，而不是直接比較項本身。在整數數組的情況下，項目和排序鍵可以是一個也可以是相同的，您可以直接比較它們。

在我看來好像geeksforgeeks代碼已經從一個更通用的例子，允許使用排序鍵，這樣的改編：

// Store count of each item 
for(i = 0; arr[i]; ++i) 
    ++count[key(arr[i])]; 

// Change count[i] so that count[i] now contains actual 
// position of this character in output array 
for (i = 1; i <= RANGE; ++i) 
    count[i] += count[i-1]; 

// Build the output array 
for (i = 0; arr[i]; ++i) 
{ 
    output[count[key(arr[i])]-1] = arr[i]; 
    --count[key(arr[i])]; 
} 

哪裏key是計算排序鍵的功能基於一個項目（對於整數類型，你可以直接返回整數）。在這種情況下，MAX_NUM將不得不被替換爲MAX_KEY。

該方法使用額外的輸出數組，因爲最終結果是通過複製arr中的項而不是簡單地從count（僅包含每個鍵的項目數）中的信息生成的。然而，in-place counting sort是可能的。

該算法還保證stable sort（具有相同排序鍵的項目通過排序保留其相對順序） - 排序整數時這沒有意義。

但是，由於他們已經刪除了基於密鑰進行排序的能力，因此沒有理由增加額外的複雜性，並且您的方式更好。

也有可能他們已經從C++這樣的語言複製了代碼，其中int cast（在使用項目索引數組時將被調用）可能被重載以返回排序鍵，但已被錯誤地轉換到C.

Answer 2

我認爲你的版本是一個更好的方法。我懷疑是誰寫的這個代碼示例的人都可能寫類似的代碼樣本，其他排序算法 - 有很多的排序算法，你做需要單獨的「暫存空間」 - 並沒有投入足夠的思想到這一點。

另外，他（她）可能覺得該算法更容易解釋，如果我們分開「產生的結果」，從「移動的結果到位」？我不同意，如果是的話，但詳細的評論清楚表明他有教育學的想法。

儘管如此，也有一些小問題與您的版本：

• 你忘了申報i。
• 你應該採取的陣列長度作爲參數，而不是使用硬編碼ARRAY_SIZE。 （在代碼示例中，通過使用字符串避免了這個問題，所以它們可以迭代直到終止空字節。）
• 這可能是主觀的，但我認爲編寫for (int j = 0; j < countingArray[i]; ++j)會更清楚一些，但不是while (countingArray[i]--)。