Merge Sort(合併排序法)
學習資源
牛刀小試
- Leetcode 的 912
範例程式碼
python
def merge(arr, front, mid, end):
left_sub = arr[front : mid + 1]
right_sub = arr[mid + 1 : end + 1]
left_sub.append(float('inf'))
right_sub.append(float('inf'))
idx_left, idx_right = 0, 0
for i in range(front, end + 1):
if left_sub[idx_left] <= right_sub[idx_right]:
arr[i] = left_sub[idx_left]
idx_left += 1
else:
arr[i] = right_sub[idx_right]
idx_right += 1
def merge_sort(arr, front, end):
if front < end:
mid = (front + end) // 2
merge_sort(arr, front, mid)
merge_sort(arr, mid + 1, end)
merge(arr, front, mid, end)
arr = [5, 3, 8, 6, 2, 7, 1, 4]
merge_sort(arr, 0, len(arr) - 1)
print("sorted:")
print(*arr)python
def merge_sort(array):
if len(array) > 1:
mid = len(array) // 2
left = merge_sort(array[:mid])
right = merge_sort(array[mid:])
array = merge_sorted_arrays(left, right)
return array
def merge_sorted_arrays(left, right):
sorted_array = []
left_index = 0
right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
sorted_array.append(left[left_index])
left_index += 1
else:
sorted_array.append(right[right_index])
right_index += 1
sorted_array.extend(left[left_index:])
sorted_array.extend(right[right_index:])
return sorted_array
# 測試
array_to_sort = [38, 27, 43, 3, 9, 82, 10]
sorted_array = merge_sort(array_to_sort)
print("原始陣列:", array_to_sort)
print("排序後:", sorted_array)python
data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]
def merge(left, right):
result = []
while len(left) and len(right):
if (left[0] < right[0]):
result.append(left.pop(0))
else:
result.append(right.pop(0))
result = result+left if len(left) else result+right
return result
def mergeSort(array):
if len(array) < 2:
return array
mid = len(array)//2
leftArray = array[:mid]
rightArray = array[mid:]
return merge(mergeSort(leftArray),mergeSort(rightArray))
print(mergeSort(data))
#[23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]牛刀小試
Contributors
lucashsu95