Hợp nhất sắp xếp

Hợp nhất sắp xếp

Sắp xếp hợp nhất là một ứng dụng rất điển hình của phép chia và phép chia. Ý tưởng của sắp xếp hợp nhất là phân tách mảng một cách đệ quy trước, và sau đó hợp nhất mảng.

Sau khi phân tách mảng thành kích thước nhỏ nhất, và sau đó hợp nhất hai mảng có thứ tự, ý tưởng cơ bản là so sánh số đầu tiên của hai mảng và lấy ai nhỏ hơn trước, sau đó di chuyển con trỏ tương ứng lùi lại một chút sau khi lấy số. Sau đó so sánh cho đến khi một mảng trống và cuối cùng sao chép phần còn lại của mảng khác.

Phân tích sắp xếp hợp nhất

Hợp nhất-sắp xếp-ví dụ

def merge_sort(alist):
    if len(alist) <= 1:
        return alist
   
    num = len(alist)/2
    left = merge_sort(alist[:num])
    right = merge_sort(alist[num:])
    return merge(left,right)

def merge(left, right):
    
    l, r = 0, 0
    result = []
    while l<len(left) and r<len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result

alist = [54,26,93,17,77,31,44,55,20]
sorted_alist = mergeSort(alist)
print(sorted_alist)

thời gian phức tạp

• Độ phức tạp thời gian tối ưu: O (nlogn)

• Độ phức tạp về thời gian tệ nhất: O (nlogn)

• Stability: ổn định