算法HW5

1265-张同学

发表文章数:58

首页 » 数据结构 » 正文

知识点

  1. 排序算法的稳定性:稳定的排序会让原本有相等键值的记录维持相对次序。

  2. 冒泡排序:

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

时间复杂度:O(n2)。稳定。

  1. 选择排序,优点在于数据移动,若某个元素位于正确的位置上,则它不会被移动。
def select_sort(arr):
	if not arr: return 
	for i in range(len(arr)-1):
		min_ind = i
		for j in range(i+1,len(arr)):
			if arr[min_ind]>arr[j]:
				min_ind = j
			arr[i],arr[min_ind] = arr[min_ind],arr[i]
	return arr

时间复杂度O(n2)。不稳定。

  1. 插入算法,对每个元素向前交换,即向前插入。
def insert_sort(arr):
	if not arr: return 
	for i in range(1,len(arr)):
		while i>0:
			if arr[i] < arr[i-1]:
				arr[i-1],arr[i] = arr[i],arr[i-1]
				i -= 1
			else:
				break
	return arr

时间复杂度O(n2)。稳定。

  1. 希尔排序,引入间隔并且间隔变化的插入排序。
def shell_sort(arr):
	if not arr: return []
	n = len(arr)
	gap = n//2
	i = 1
	while gap:
		for j in range(gap,n):
			i = j
			while i>0:
				if arr[i] < arr[i-gap]:
					arr[i],arr[i-gap] = arr[i-gap],arr[i]
					i -= gap
				else:
					break
		gap //= 2
	return arr

时间复杂度O(n2)。不稳定。

  1. 快速排序。
def quick_sort(arr,first,last):
	if first>=last: return
	n = len(arr)
	mid = arr[first]
	low,high = first,last
	while low<high:
		while low<high and arr[high]>=mid:
			high -= 1
		arr[low] = arr[high]
		while low<high and arr[low]<mid:
			low += 1
		arr[high] = arr[low]
	arr[low] = mid
	quick_sort(arr,first,low-1)
	quick_sort(arr,low+1,last)
	return arr	

时间复杂度O(nlogn),T(n) = T(n/2)+O(n)。不稳定。

  1. 归并排序。
def merge_sort(arr):
	if len(arr)<=1: return arr
	mid = len(arr)>>1
	left = merge_sort(arr[:mid])
	right = merge_sort(arr[mid:])
	return merge(left,right)
def merge(left,right):
	l,r = 0,0
	res = []
	while l<len(left) and r<len(right):
		if left[l]<=right[r]:
			res.append(left[l])
			l += 1
		else:
			res.append(right[r])
			r += 1
	res += left[l:]
	res += right[r:]
	return res

时间复杂度O(nlogn),T(n) = T(n/2)+O(n)。稳定。

  1. 排序算法总结。
    算法HW5
  2. 二分查找。
#Method1 recursion
def binary_search(arr,item):	
	n = len(arr)
	arr = sorted(arr)
	if n:
		mid = n//2
		if arr[mid] == item:
			return True
		elif arr[mid] > item:
			return binary_search(arr[:mid],item)
		else:
			return binary_search(arr[mid+1:],item)
	return False
#iteration
def binary_search(arr,item):
	if not arr: return False
	arr = sorted(arr)
	l, r = 0, len(arr)-1
	while l<=r:
		mid = (l+r)>>1
		if arr[mid] == item:
			return True
		elif arr[mid]<item:
			l = mid+1
		else:
			r = mid-1
	return False

时间复杂度O(logn)。

拜师教育学员文章:作者:1265-张同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《算法HW5》 发布于2020-09-04

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录