[数据结构与算法]Python经典排序方法总结

冒泡排序

def bubble_sort(nums):
	for i in range(len(nums)-1):
		for j in range(len(nums)-i-1):
			if nums[j] > nums[j+1]:
				nums[j], nums[j+1] = nums[j+1], nums[j]
	return nums

nums = [3,6,4,2,11,10,5]
bubble_sort(nums)

选择排序

思想： 每次都从未排序的序列中选择一个最小的数放在已排序列的最左边，直至排序完成。

def select_sort(nums):
	for cur in range(len(nums)-1):
		num_max = cur
		# 当前元素和剩余元素进行对比，有更小值需替换
		for i in range(cur+1, len(nums)):
			if nums[i] < nums[num_max]:
				nums[i], nums[num_max] = nums[num_max], num[i]
		# 若当前元素不是最小元素，需要和上面查到的最小值进行替换
		if num_max != cur:
			nums[cur], nums[num_max] = nums[num_max], nums[cur]
	return nums

nums = [3,6,4,2,11,10,5]
select_sort(nums)		

插入排序

基本思想：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

def insert_sort(nums):
	for i in range(1, len(nums)):
		# 从第i个位置往前比较，如果小于前一个元素，就交换位置
		for j in range(i, 0 , -1):
			if nums[j] < nums[j-1]:
				nums[j], nums[j-1] = nums[j-1], nums[j]
	return nums

nums = [3,6,4,2,11,10,5]
insert_sort(nums)

快速排序

基本思想：从序列中找出一个基准元素，大于该元素的放到一边，小于该元素的放到另一边形成分区；然后分别从大小分区中再找出基准分别分出相对大小分区，然后利用递归完成快速排序。

def quick_sort(nums):
	if len(nums) > 2:	# 递归入口及出口
		mid = nums[len(nums)//2] # 选取基准值，也可以是第一个或者最后一个
		left, right = [], [] # 定义基准值左右两侧的列表
		nums.remove(mid) # 从原始数组中移除基准值
		for num in nums:
			if num >= mid:
				right.append(num)
			else: 
				left.append(num)
		return quick_sort(left)+ [mid] + quick_sort(right)
	else:
		return nums
nums = [3,6,4,2,11,10,5]
quick_sort(nums)

希尔排序

基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

def shell_sort(nums):
	step = len(nums)//2
	while step > 0:
		for cur in range(step, len(nums)):
			i = cur 
			while i >= step and nums[i-step] > nums[i]:
				nums[i-step], nums[i] = nums[i], nums[i-step]
				i -= step
		step = step //2
	return nums

nums = [3,6,4,2,11,10,5]
shell_sort(nums)

归并排序

基本思想：速度较快速稍慢。将数组分解最小之后，合并两个有序数组。比较两个数组最前面的数，谁小取谁，取了后指针相应后移一位。一直比较，至一个数组为空，然后将另一个数组的术语部分复制到后面即可。

def merge_sort(nums):
	if len(nums) <= 1:
		return nums
	num = len(nums) // 2
	left = merge_sort(nums[:nums])
	right = merge_sort(nums[nums:])
	return merge(left, right) # 合并

def merge(left, right):
	l, r = 0,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
	
nums = [3,6,4,2,11,10,5]
merge_sort(nums)

二分查找法

前提是有序序列

def binarysearch(nums, target)L
	left, right = 0, len(nums)
	while left <= right:
		mid = left + (right - left) // 2
		if target == nums[mid]:
			return mid
		elif target < nums[mid]:
			right = mid - 1
		else:
			left = mid + 1
		return -1

nums = [2,4,7,8,10,12,13]; target = 8
binarysearch(nums, target)