合併排序所需的基礎案例Clarificaiton

我知道這是一個非常簡單的問題，但我自己學習，所以請耐心等待！合併排序所需的基礎案例Clarificaiton

在維基百科的僞代碼mergeSort（見下文）中，終端情況是如果數組/列表的長度小於或等於1。在評論中，他們說如果它的長度是0或1，那麼它就被排序。這我同意，但我很好奇這是否意味着mergeSort將不起作用，如果代碼有if (length == 1)？我只是困惑如何一個數組可能會分裂成一個0長度的數組。如果它的長度等於1，它不會停止嗎？

function merge_sort(list m) 
    // Base case. A list of zero or one elements is sorted, by definition. 
    if length of m ≤ 1 then 
     return m 

    // Recursive case. First, divide the list into equal-sized sublists 
    // consisting of the even and odd-indexed elements. 
    var left := empty list 
    var right := empty list 
    for each x with index i in m do 
     if i is odd then 
      add x to left 
     else 
      add x to right 

    // Recursively sort both sublists. 
    left := merge_sort(left) 
    right := merge_sort(right) 

    // Then merge the now-sorted sublists. 
    return merge(left, right)

來源

2016-04-03 AlanH

親愛的OP，最近你問很多問題而不接受答案，即使有可以接受的答案。請獎勵幫助過你的人並接受你的問題的答案。謝謝。 – DarkDust

@DarkDust謝謝，我已經這麼做了，但並非所有人都提供了我正在尋找的答案。有時候，他們會在評論中回答，並且我贊成這些評論（我認爲，就聲譽而言，它什麼都不做）。 – AlanH

該算法是遞歸的，這意味着該功能是拆分列表，然後調用自己與每個部分。要終止遞歸，if (length == 1)就足夠了，因爲分割後永遠不會有空列表。你有這個權利。

但是用戶可以用空列表調用此函數。所以這也需要被捕獲。因此if (length <= 1)（if length of m ≤ 1 then return m）。

來源

2016-04-03 18:03:06 DarkDust

合併排序所需的基礎案例Clarificaiton

回答

相關問題