排序一個數組，並把它放在一個鏈表

-2

我有一個僞代碼算法，它採用未排序的數組作爲輸入，並將其排序在鏈表中。我不太清楚它是如何工作的。也許它有一個錯誤。我一直在嘗試了一個多小時，以瞭解它是如何工作的，但我在某個時刻被卡住了。我會盡我所能解釋。任何知道它如何工作的人都樂意提供幫助。排序一個數組，並把它放在一個鏈表

ORDER(A) 
head [L1] = create(); //Null List is created. 
key[head[L1]] = A[1]; //First element of the array is put as the first in list. 

for i=2 to length(A); 
    x = create();  // create a node for every element of the array 
    key[x] = A[i];  // put A[i] as key in the node. 
    p1 = head[L1];  // make p1 head of the list. 
    if key[p1] > A[i];  //compare A[i] with the head 
     insert_head(x);  // if smaller put it in the beggining and make it head 
    while key[next[p1]] < A[i] AND next[p1] =/= nil // This part I don't understand 
     if next[p1] == nil        //very well. 
      next[p1] = x 
      next[x] = nil 
     else 
      next[x] = next[p1] 
      next[p1] = x;

來源

2013-10-22 Marcus Aurelius

'對一個數組進行排序並將其放入一個鏈表中或'將一個未排序的數組放入一個已排序的鏈表中？ – sircodesalot

取一個未排序的數組，並將其放入已排序的鏈接列表中。 –

這與insertion sort非常相似。

對鏈表進行排序並從空開始，然後將數組中的每個元素插入到正確位置的鏈表中，以便在每次插入後排序。

對於插入，它會遍歷鏈表，直到我們要插入的元素小於鏈表中的當前元素，或者我們已經到達鏈表的末尾，並且然後插入。

我認爲有可能是一個錯誤，我認爲while循環應該是：

// here we advance the position in the linked-list 
// until we reach the end or the current element is smaller 
while key[next[p1]] < A[i] AND next[p1] =/= nil 
    p1 = next[p1] 

// if we reached the end, next[x] won't point to anything 
if next[p1] == nil       
    next[p1] = x 
    next[x] = nil 
// if we didn't reach the end, 
// next[x] needs to point to anything what next[p1] was pointing to 
else 
    next[x] = next[p1] 
    next[p1] = x;

來源

2013-10-22 13:24:49 Dukeling

這個算法具有O（n^2）它可以在O（n log-n）中進行形式化，使用更好的算法對數組進行排序，然後將它傳遞給列表 – Qsebas

@Qsebas確實，或者直接將它傳遞給鏈表並在O（n log n）中排序。 – Dukeling

你有僞代碼的insertion sort實現，誰擁有的O最壞情況的複雜性（N^2）。

基本上，while塊正在循環整個保留數據排序子集的列表，當while找到要插入的位置時，它會將其插入排序列表中。如果該時段沒有找到要插入的位置，則將其插入列表的末尾。

也許你應該考慮使用Merge sort的（複雜度爲O（N日誌-N）），然後將它傳遞給一個列表（O（n））的

提出這項建議的總複雜度爲O（N日誌N ）

來源

2013-10-22 13:58:39 Qsebas

從學習的角度來看，所有O（n^2）算法（bubblesort，選擇排序，插入排序）的優點是它們很簡單並且易於實現。此外，對於小型陣列（少於100個元素），選擇和插入排序通常比分治算法更高效，因爲其較低的頭部成本。解決新學習者關於排序問題的錯誤方法是隻關注時間複雜性。 – scottb

排序一個數組，並把它放在一個鏈表

回答

相關問題