大型网站的技术架构问题网页即时聊天
问题
排序 [30, 24, 5, 58, 18, 36, 12, 42, 39]
归并排序
归并排序采用分治法，将序列分成若干子序列，每个子序列有序后再合并成有序的完整序列。
在数组排序中，如果只有一个数，那么它本身就是有序的。如果有两个数，只需要进行一次比较就可以完成排序。也就是说，数越少，排序越容易。那么，如果有一个由大量数据组成的序列，可以考虑将其不断分解，直到只剩一个数时，本身已经有序，再将这些有序的数组合并在一起，从而完成排序。
图解
- 将待排序元素分成大小大致相同的两个序列
- 对两个序列分别进行归并排序
- 将排好序的有序子序列进行合并，得到最终的有序序列
代码
# 合并, 将两个有序的子序列合并成一个序列
def merge(nums, low, mid, high):i, j = low, mid + 1k = 0temp = [0] * (high - low + 1)while i <= mid and j <= high:if nums[i] <= nums[j]:temp[k] = nums[i]i += 1else:temp[k] = nums[j]j += 1k += 1if i <= mid:temp[k:] = nums[i:mid+1]if j <= high:temp[k:] = nums[j:high+1]nums[low:high+1] = tempreturn numsdef merge_sort(nums, low = 0, high = len(nums)-1):if low < high: # low = high时分解到只剩一个数，不用合并直接返回mid = low + (high - low) // 2merge_sort(nums, low, mid) # 对左半部分进行归并排序merge_sort(nums, mid+1, high) # 对右半部分进行归并排序return merge(nums, low, mid, high) # 合并为有序子序列else:return nums
时间复杂度
归并算法的时间复杂度为 O(nlogn)
- 分解：这一步仅仅是计算出子序列的中间位置，需要常数时间 O(1)
- 解决子问题：递归求解两个规模为 n/2 的子问题，所需时间为 2T(n/2)
- 合并：合并算法可以在 O(n) 时间内完成
所以总运行时间为：
当 n>1 时，可以递推求解：
递推最终的规模为 1， 令 2x = n，则 x = log n，那么
