在之前的课堂作业里看到的，就贴了出来，顺便复习一下。
归并与快排都是分治的思想，但是归并多了结果的归并，并且动态的来看，快排是自大而小，即一步一步递归要求子数组有序，归并是自小而大，要求子数组有序，再要求父数组有序。
来自算法4
java版本
- 通用的原地归并的方法
也可以不原地归并，而是用新的数组以避免过多的元素复制，但是需要在每次递归的时候交换原数组和新数组的角色，应为在同一时刻，只有其中一个是有意义的。
/**
* 定义一个通用的原地归并的方法
* 采用元素复制，和 双指针法i，j 分别是左右有序子数组的指针
*/
public static void merge(int[] numbers, int lo , int mid, int hi){
// 不应该新建数组，而是传入一个和原始数组一样大的数组应用，以避免创建过多的对象
int[] aux = new int[hi - lo + 1];
for(int k = lo ; k <= hi ; ++ k){
aux[k] = numbers[k];
}
int i = lo , j = mid + 1;
for(int k = lo ; k <= hi; ++k){
if( i > mid){
// 左半边用尽
numbers[k] = aux[ j ++];
}else if ( j > hi ){
// 右半边用尽
numbers[k] = aux[ i ++];
} else if ( numbers[i] < numbers[j ){
// 当前左边的元素小于右边的当前元素
numbers[k] = aux[ i ++];
}else ( j > hi ){
// 当前左边的元素大于等于右边的当前元素
a[k] = aux[ j ++];
}
}
}
- 排序
- 递归
public static void sort(int[] numbers, int lo , int hi){ if( hi < lo) return; int mid = (hi - lo )/2 + lo; sort(numbers, lo, mid); sort(numbers, mid + 1, hi); merge(numbers, lo , mid , hi); }- 非递归 自底向上
两两合并，再四四合并，等等
static int[] aux ; public static void sort(int numbers, int lo , int mid , int i){ aux = new int[numbers.length]; int N = numbers.length; for(int size = 1; size < N; size *= 2){ // size 是 lo 到 hi的一半，所以小于N, 并且，Math.min(lo + size * 2-1 ,N-1), 以避免越界。 for( int lo = 0; lo < N - size ; lo += 2 * size){ merge(numbers, lo , lo + size -1, Math.min(lo + size * 2 -1 , N -1); } }
python版
非递归实现归并排序
import sys
#定义一种通用的原地merge方法
def merge(nums , low , mid , high):
i = low
j = mid + 1
aux = [0 for x in range(high + 1)]
for k in range(low, high + 1):
aux[k] = nums[k]
for k in range(low, high + 1):
if ( i > mid):
nums[k] = aux[j]
j += 1
elif j > high:
nums[k] = aux[i]
i +=1
elif aux[j] < aux[i]:
nums[k] = aux[j]
j += 1
else:
nums[k] = aux[i]
i += 1
# return nums
# 递归实现
def merge_sort(nums, lo , hi ):
if(hi <= lo):
return
mid = lo +(hi - lo) // 2
merge_sort(nums , lo , mid)
merge_sort(nums, mid + 1, hi)
merge(nums, lo , mid , hi)
# 第一种方法 不借助于栈, 实现自底向上
def merge_sort_1(length, nums):
aux = [0 for x in range(length)]
size = 1
while size < length:
for lo in range(0, length - size, 2*size):
merge(nums, lo , lo + size - 1 , min(lo + 2 * size - 1 , length - 1))
size *= 2
if __name__=="__main__":
for x in sys.stdin:
tmp = [int(i) for i in x.strip().split(" ")]
length = tmp[0]
tmp = tmp[1:]
# merge_sort(tmp, 0 , length - 1)
merge_sort_1(length , tmp)
ans = ""
for i in tmp:
ans += str(i) + " "
print(ans.strip())
