day20——归并排序学习qq42662568的博客-

Day_20 —— 归并排序

归并排序的基本思想是：

• 先将序列一次次分成子序列，直到子序列长度为1；
• 再将已有序的子序列合并，得到完全有序的序列。

可以看出归并排序运用了 分而治之的思想 。

归并排序是按照分层进行比较的，会分成
$log_2n$

log2​n层；
而每一层的比较次数为
$O(n)$

O(n)；
所以时间复杂度求得
$nlog_2n$

nlog2​n。

C实现：

#include <stdio.h> #define max 10 int a[11] = { -10, 14, 11, 26, 34, 31, -33, 20, 42, 11, 0 }; int b[10]; void merging(int low, int mid, int high) { int l1, l2, i; for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) { if(a[l1] <= a[l2])          b[i] = a[l1++]; else          b[i] = a[l2++]; } while(l1 <= mid)           b[i++] = a[l1++]; while(l2 <= high)          b[i++] = a[l2++]; for(i = low; i <= high; i++)       a[i] = b[i]; } void sort(int low, int high) { int mid; if(low < high) {       mid = (low + high) / 2; sort(low, mid); sort(mid+1, high); merging(low, mid, high); } else { return; } } int main() { int i; printf("List before sortingn"); for(i = 0; i <= max; i++) printf("%d ", a[i]); sort(0, max); printf("nList after sortingn"); for(i = 0; i <= max; i++) printf("%d ", a[i]); } 

python实现：

def merge_sort(collection): def merge(left, right):         result = [] while left and right:             result.append((left if left[0] <= right[0] else right).pop(0)) return result + left + right      if len(collection) <= 1: return collection     mid = len(collection) // 2 return merge(merge_sort(collection[:mid]), merge_sort(collection[mid:])) if __name__ == "__main__":     user_input = input("Enter numbers separated by a comma:n").strip()     unsorted = [int(item) for item in user_input.split(",")] print(*merge_sort(unsorted), sep=",")