使用有限的一組操作對50000個數字的2個鏈接列表進行排序

因此，我有這個學校項目：我有一個鏈接列表，其中包含50000個數字和第二個空列表。我只有一個非常有限的說明小組。它們是：使用有限的一組操作對50000個數字的2個鏈接列表進行排序

「sa」的交換列表的前兩個元素1
「SB」交換列表的前兩個元素2
「SS」是「sa」和「SB」同時
「PA」：在列表中的1
「PB」頂推列表2的頂部元件：推列表的頂部元件1上列表的頂部2
「RA」：旋轉列表1（第一元件變成最後）
「RB」：旋轉列表2（第一變最後）
「RR」：「RA」和「RB」在一次
「RRA」：旋轉列表1（最後成爲第一）
「RRB」：旋轉列表2（最後成爲第一）
「RRR」：「宗教事務條例」和「無線電規則委員會」在一次

我要實現在C排序算法，目標是與指令的最小量做到這一點。我試着用一個非常簡單的算法，旋轉列表1，直到最大值在最上面，然後重複推入列表2中，直到所有內容都在列表2中，然後將所有內容都推回到列表1中，但我無法對列表中的列表進行排序在合理的時間內超過5k數字

來源

2015-11-14 Henry

您可以使用這些操作進行相當高效的合併排序。 –

所以我應該把列表1的一半放在列表2中，然後同時對這兩個列表進行排序併合並它們？ – Henry

我認爲某種快速排序或合併排序是最好的選擇。雖然存儲未使用的節點會有點棘手。 –

我想我已經想出瞭如何使用快速排序來做到這一點。這是一些僞代碼。

編輯：更新僞專注於它在做什麼，而不是不必要的語法

quicksort(int n) 
    if n == 1 return 
    int top_half_len = 0 
    choose a median //it's up to you to determine the best way to do this 
    for 0 to n { //filter all values above the median into list 2 
     if (value > median) { 
      push list 1 top to list 2 //list 2 stores the larger half 
      top_half_len++ 
     } 
     rotate list 1 forward 
    } 

    //reverse the list back to original position 
    rotate list 1 backward (n - top_half_len) times 

    //push larger half onto smaller half 
    push list 2 top to list 1 top_half_len times 

    //recursively call this on the larger half 
    quicksort(top_half_len) 

    //rotate smaller half to front 
    rotate list 1 forward top_half_len times 

    //recursively call this on smaller half 
    quicksort(n - top_half_len) 

    //reverse list back to original position 
    rotate list 1 backward top_half_len times

基本上，將列表分成比中位數（較小的一半）小於或等於一個部分和部分比更大（大一半）。然後它在這兩個方面都稱自己。一旦長度爲1，算法就完成了，因爲長度爲1的列表被排序。谷歌快速排序爲一個實際的解釋。

我認爲這應該可行，但我可能錯過了一些邊緣案例。不要盲目追隨此。另外，如果你在處理數組，我建議你在某個遞歸深度停止快速排序並使用堆排序（或者防止最壞情況O（n^2）複雜度），但我不確定這裏有什麼效率。 更新：根據彼得Cordes，你應該使用插入排序當你得到一個特定的數組大小（國際海事組織，你應該在一定的遞歸深度）。

顯然合併排序在鏈接列表上更快。它可能不會太難以修改此實現合併排序。合併排序與快速排序非常相似。 why is merge sort preferred over quick sort for sorting linked lists

來源

2015-11-14 04:23:29

非常感謝，非常有幫助，我絕對會試試這個 – Henry

問題語句丟失一個比較功能，所以我會限定比較（LISTA，數組listB）至LISTA的第一節點與數組listB的第一節點進行比較和用於=返回-1爲<，0,1對於更大或合併排序所需的全部數據，對於< =和0代表1。

另外還缺少一個返回值，表示在執行pa或pb時列表爲空。如果源列表不爲空，則定義pa或pb以返回1;如果源列表爲空（不需要複製節點），則返回0。

不清楚目標是否是最小的指令數量是指源代碼中的指令數量或排序過程中執行的指令數量。

最小的代碼將旋轉基於list2中的指令數目與list1的比較在適當的位置插入節點分成list2中。以pb開始，並將list2大小設置爲1.然後執行rb或rrb以將list2旋轉到下一個pb應該完成的位置。該代碼將跟蹤list2「偏移」到最小節點，以避免無限循環旋轉list2。複雜性是O（n^2）。

我在想最快的排序，也許執行的指令數最少是自下而上的合併排序。

在旋轉列表時使用它們（如循環緩衝區/列表）進行自底向上合併排序。使用序列|將list1複製到list2以生成節點計數count = 0 | while（pb）{rb | count + = 1}。

使用計數，使用{pa，rr}，n/2次將每個其他節點從list2移動到list1。始終跟蹤每個列表上的實際節點數量，以便知道何時到達列表的邏輯末尾。還要跟蹤每個列表的運行計數器，以瞭解運行的邏輯結束時間。此時，您有兩個列表，其中偶數節點位於list1上，奇數節點位於list2上。

運行大小從1開始，在每次通過時加倍。對於運行大小爲1的第一遍，將具有奇數節點的偶數節點合併，創建大小爲2的排序運行，交替地將排序的節點對附加到列表1和列表2。例如，如果追加到list1和list1節點< = list2節點，請使用{ra，run1count - = 1}，否則使用{pa，ra，run2count - = 1}。到達運行結束時，將剩餘運行的剩餘部分追加到列表的末尾。在下一個過程中，合併來自列表的2個節點的已排序運行，交替地將已排序的4個節點運行追加到每個列表。繼續運行8,16 ...，直到所有節點都在一個列表中。

因此，這是一個通過計算節點，一次通過拆分偶數和奇數節點，並且ceil（log2（n））通過進行合併排序。鏈表操作的開銷很小（rotate會移除並附加一個節點），所以整體合併應該相當快。

可以通過while（pb）{count + = 1}減少計數過程中指令的數量，這會將list1複製到list2中。然後將list2吐在list1中也會使用rrr來解決它們。

複雜性是O（n log（n））。

來源

2015-11-14 08:31:30 rcgldr

使用有限的一組操作對50000個數字的2個鏈接列表進行排序

回答

相關問題