归并排序（MergeSort）
归并排序（英语：Merge sort，或mergesort），是创建在归并操作上的一种有效的排序算法，效率为 O(nlog n)（大O符号）。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行
递归法（Top-down）
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
Python实现
def mergeSort(nums):
if len(nums) < 2:
return nums
mid=len(nums)//2
left=mergeSort(nums[:mid])
right=mergeSort(nums[mid:])
return megre(left,right)
def megre(left,right):
result=[]
i=j=0
while j<len(left) and i <len(right):
if left[j] < right[i]:
result.append(left[j])
j+=1
else:
result.append(right[i])
i+=1
if j==len(left):
for temp in right[i:]:
result.append(temp)
else:
for temp in left[j:]:
result.append(temp)
return result
if __name__ == "__main__":
nums = [1, 4, 2, 3.6, -1, 0, 25, -34, 8, 9, 1, 0]
print("original:", nums)
print("Sorted:", mergeSort(nums))
输出内容：
C:Python27python.exe D:/code-program/lianxi-test/二叉搜索树.py
('original:', [1, 4, 2, 3.6, -1, 0, 25, -34, 8, 9, 1, 0])
('Sorted:', [-34, -1, 0, 0, 1, 1, 2, 3.6, 4, 8, 9, 25])
Process finished with exit code 0
c语言版本
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
int reg[len];
merge_sort_recursive(arr, reg, 0, len - 1);
}