歸併排序實現

有歸併排序我見過的許多實現，但是，我想寫一個從合併排序的算法定義直譯：歸併排序實現

拆分陣列，直到剩下1個元素
將它們合併在一起。

但是我有點卡住了。這是我的代碼，直到現在，

class MergeSort: 
    def __init__(self): 
     bucket = [] 

    def _sort(self, arr): 
     if len(arr) == 1: 
      pass 

     mid = len(arr) //2 
     self._sort(arr[:mid]) 
     self._sort(arr[mid:]) 

    def _merge(self, arr1, arr2, arr): 
     i, j = 0, 0 
     while i < len(arr1) and j < len(arr2): 
      if arr1[i] < arr2[j]: 
       arr.append(arr1[i]) 
       i += 1 
      else: 
       arr.append(arr2[j]) 
       j += 1

代碼將以這種方式調用。

merge_sort = MergeSort() 
merge_sort._sort([1,9,3,2,5])

有人可以幫我把這兩種方法縫合在一起，以便合併排序。只是重申一下，我沒有看到新的方法。謝謝。

來源

2017-09-09 Melissa Stewart

沒有進入，爲什麼不是方法靜態的，什麼是'水桶的使用'等等。使用這個類的代碼在哪裏？ – Yigal

@Yigal桶應該保存排序後的數組。我正在使用調用代碼更新代碼。 –

如果您只是使用您的類調用'_sort（）'方法，則不需要使用'bucket'變量進行初始化。 – Daniel

我不是100％清楚爲什麼你需要將你的邏輯封裝在一個類中（這個決定導致了問題的重點：類設計的Python成語等）。

class MergeSort: 

    def _sort(self, arr): 
     arr1 = [] 
     arr2 = [] 

     n = len(arr) 

     if n <= 1: 
      return 

     for i in range(0, n): 
      if i < (n/2): 
       arr1.append(arr[i]) 
      else: 
       arr2.append(arr[i]) 

     self._sort(arr1) 
     self._sort(arr2) 
     self._merge(arr, arr1, arr2) 
     return arr 

    def _merge(self, arr, arr1, arr2): 
     end1 = len(arr1) 
     end2 = len(arr2) 
     start1 = 0 
     start2 = 0 
     k = 0 

     while (start1 < end1) and (start2 < end2): 
      if arr1[start1] < arr2[start2]: 
       arr[k] = arr1[start1] 
       start1 += 1 
      else: 
       arr[k] = arr2[start2] 
       start2 += 1 
      k += 1 

     while start1 < end1: 
      arr[k] = arr1[start1] 
      start1 += 1 
      k += 1 

     while start2 < end2: 
      arr[k] = arr2[start2] 
      start2 += 1 
      k += 1

其中產量：在下面的代碼，但是，農具排序在Python由算法定義合併

>>>lis = [4,1,6,2,3,8,9,7] 
>>>print "Sorted array: ", MergeSort()._sort(lis) 
Sorted array: [1, 2, 3, 4, 6, 7, 8, 9]

來源

2017-09-09 16:16:18 Daniel

歸併排序實現

回答

相關問題