python实现排序算法二：归并排序

##归并排序

##基本思想：对于两个排好序的数组A和B，逐一比较A和B的元素，将较小值放入数组C中，当A或者B数组元素查询完后，将A或者B剩余的元素直接添加到C数组中，此时C数组即为有序数组，这就是归并排序原理

##step1：对于一个无序数组A，可以取A元素中间索引，将A数组分为两个部分A1，A2；

##step2：递归A1，A2，分别将A1，A2分为A11，A12和A21,A22两部分直至只有一个元素；

##step3：对于只有一个元素的数组来讲，其是有序的，因此，对于两个只有一个元素的数组，可以根据基本思想所述合成一个数组C，最后得到有序数组

代码如下：

##归并排序

def merge(left, right):

	l = 0

	r = 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

def mergesort(array):

	if len(array) <= 1:

		return array

	num = int(len(array)/2)

	left = mergesort(array[:num])

	right = mergesort(array[num:])

	return merge(left, right)

if __name__ == '__main__':

	b = [1, 22, 90, 4, 65, 3, 73, 8]

	print(b)

	a = mergesort(b)

	print(a)

巴特西

python实现排序算法二：归并排序

最新文章

热门文章