單鏈表中的計數排序C＃

是否有任何方法可以在單鏈表中進行計數排序？我還沒有看到任何例子，如果沒有它們就很難做到。我在數組中有它的例子，並希望在單鏈表中做到這一點。有人在單鏈表中做過嗎？單鏈表中的計數排序C＃

public static int[] CountingSortArray(int[] array) 
    { 
     int[] aux = new int[array.Length]; 

     // find the smallest and the largest value 
     int min = array[0]; 
     int max = array[0]; 
     for (int i = 1; i < array.Length; i++) 
     { 
      if (array[i] < min) min = array[i]; 
      else if (array[i] > max) max = array[i]; 
     } 

     int[] counts = new int[max - min + 1]; 

     for (int i = 0; i < array.Length; i++) 
     { 
      counts[array[i] - min]++; 
     } 

     counts[0]--; 
     for (int i = 1; i < counts.Length; i++) 
     { 
      counts[i] = counts[i] + counts[i - 1]; 
     } 

     for (int i = array.Length - 1; i >= 0; i--) 
     { 
      aux[counts[array[i] - min]--] = array[i]; 
     } 

     return aux; 
    }

來源

2017-03-02 Oilka

請提供您正在尋找的示例。 – STLDeveloper

我發現一個，在一個陣列上的工作原理：http://www.geeksforgeeks.org/counting-sort/

我想以最小的努力就可以改變一個鏈表，唯一的問題是，你最終會遍歷鏈表許多次，因爲你沒有隨機訪問，例如。 []使其效率相當低。既然你似乎已經找到了同樣的事情，我可以完成打字之前，我認爲我的答案是沒有意義的。不過，對於您遇到問題的方式，我仍然有點好奇。

如果想知道從哪裏開始是問題，則需要提示：每次看到使用array[i]時，都需要首先遍歷鏈表，而不是首先獲取第i項。

編輯：您需要創建第二個鏈接頻率列表的唯一原因是，如果您需要真正對結果鏈接列表進行操作。如果你只是需要一個鏈表中的值的排序列表來顯示目的，一個數組保持頻率將工作（我想在同一時間你可以創建一個所有值的數組然後做你已經有的計數排序它）。我很抱歉，如果我一直在困惑我的c，C++，C++/cx，（我現在沒有編譯器），但是這應該給你一個關於如何去做的好主意。

public static node* FindMin(node* root){ //FindMax would be nearly identical 
    node* minValue = root; 
    while(node->Next){ 
    if(node->Value < minValue->Value) 
     minValue = node; 
    } 
    return minValue; 
} 
public static node* CountingSortArray(node* linklist){ 
    node* root = linkedlist 

    node* min = FindMin(linklist); 
    node* max = FindMax(linklist); 

    int[] counts = new int[max->Value - min->Value + 1]; 

    while(root != NULL){ 
    counts[root->Value] += 1; 
    root = root->Next; 
    } 

    int i = 0; 
    root = linkedlist; 

    while(ptr != NULL){ 
    if(counts[i] == 0) 
     ++i; 
    else{ 
     root->Value = i; 
     --count[i]; 
     root = root->Next; 
    } 
    } 
} 

void push(node** head, int new_data){ 
    node* newNode = new node(); 

    newNode->Value = new_data; 
    newNode->Next = (*head); 
    (*head) = newNode; 
} 

void printList(node* root){ 
    while(root != NULL){ 
    printf(%d ", root->Value); 
    root = root->Next; 
    } 
    printf("\n"); 
} 

int main(void){ 
    node* myLinkedList = NULL; 
    push(&head, 0); 
    push(&head, 1); 
    push(&head, 0); 
    push(&head, 2); 
    push(&head, 0); 
    push(&head, 2); 

    printList(myLinkedList); 
    CountingSortArray(myLinkedList); 
    printList(myLinkedList); 
}

來源

2017-03-02 19:23:49 user3164339

我在思考問題時應該創建一個新的LinkedList來存儲頻率列表，以及如何在LinkedList中查找最小值和最大值，因爲這是計數排序基於的數字 – Oilka

正如我確信您可能知道的那樣，每個節點在鏈表中有一個'值'和一個指向下一個節點的指針。因此，實現代碼中的'查找最小和最大'部分不會太難。使用的循環將不得不改變。我可能會創建一個min和max函數，它需要一個節點*並遍歷整個鏈表，以查找min或max。你不需要一個新的鏈表來存儲頻率，你可以在這裏實際使用一個數組，因爲你知道頻率中的第二項對應於鏈表中的第二項。我會在幾分鐘內爲你寫出一些代碼。 – user3164339

@Oilka沿途的某個地方，我只是決定對排序算法進行排序，而不是創建一個新的排序算法，或者只是返回數組中的排序值。希望這有助於（我也希望代碼工程哈哈）！ – user3164339

示例代碼更像是基數（max-min + 1）的基數排序。通常計數排序看起來像下面的代碼。通過列表來獲取最小和最大值。進行第二次生成計數。通過計數來生成基於計數的新數組（而不是複製數據）。示例代碼片段：

for (size_t i = 0; i < array.Length; i++) 
     counts[array[i]-min]++; 
    size_t i = 0; 
    for(size_t j = 0; j < counts.Length); j++){ 
     for(size_t n = counts[j]; n; n--){ 
      aux[i++] = j+min; 
     } 
    }

來源

2017-03-03 00:38:45 rcgldr

單鏈表中的計數排序C＃

回答

相關問題