Python数据结构与算法_第6节_排序 & 搜索

首页 » 数据结构 » 正文

排序(sorting algorithm)

归并排序(merge sorting)

  • 归并排序(merge sorting):是采用分治法的一个非常典型的应用。先递归分解数组,再合并数组。
  • 归并排序算法的思路:
    • 将数组分解最小。
    • 合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁。
    • 取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。
    • 重复这个步骤直至合并出来原序列长度的新序列。

归并排序的分析

用递归分解序列至singleton。然后将每对相邻singleton中大的元素放到合并出来的序列(长度为2)第一位。设置left和right游标。
Python数据结构与算法_第6节_排序 & 搜索
把游标所指的元素中更小的那个放到新合并的序列(长度为4)的第一位。然后把更小的那个元素的游标(此处为right)往后移动一位。
Python数据结构与算法_第6节_排序 & 搜索
比较游标新指向元素的大小,然后把更小的那个放到新合并序列(长度为4)的第二位,重复这个步骤至新序列排列好。
Python数据结构与算法_第6节_排序 & 搜索
用同样的方式合成新的序列(长度为8)。

归并排序的实现

# coding:utf-8
def merge_sort(alist):
	"""归并排序"""
	# 先拆分序列
	n = len(alist)
	# 如果序列拆分至singleton则停止recursion
	if n <= 1:
		return alist
	mid = n // 2

	# left采用归并排序后形成的有序的新的序列
	left_li = merge_sort(alist[:mid])
	# right采用归并排序后形成的有序的新的序列
	right_li = merge_sort(alist[mid:])
	# 将两个有序的子序列合并为一个新的整体
	# merge(left_li, right_li)
	
	left_pointer, right_pointer = 0, 0
	result = []
	# 每次构建新合并的序列时,把上层序列跑完
	while left_pointer < len(left_li) and right_pointer < len(right_li) :
	# 小于等于,以此来使该排序算法稳定(同大小元素,原列表左边的排在sorted列表的左边)
	if left_li[left_pointer] <= right_li[right_pointer]:
		result.append(left_li[left_pointer])
		left_pointer += 1
	else:
		result.append(right_li[right_pointer])
		right_pointer += 1
	# 把上层序列中剩余的最后一个元素放到新合并序列中的最后
	result += left_li[left_pointer:]
	result += right_li[right_pointer:]
	return result

时间复杂度

  • 最优时间复杂度:

    O

    (

    n

    log

    n

    )

    O(n*/log n)

    O(nlogn)

  • 最坏时间复杂度:

    O

    (

    n

    log

    n

    )

    O(n*/log n)

    O(nlogn)

  • 稳定性:稳定

常见排序算法效率比较

Python数据结构与算法_第6节_排序 & 搜索

  • 必须掌握快速排序
  • 面试的是时候可能会问列几个熟知的排序算法,并且写出来他们。

搜索

  • 搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的,因为该项目是否存在。
  • 搜索的几种常见方法:顺序查找、二分法查找、二叉树查找、哈希查找。

二分法查找(binary searching)

  • 二分查找/折半查找(binary search):适用于不经常变动而查找频繁的有序列表。
    • 优点:优点是比较次数少,查找速度快,平均性能好
    • 缺点:要求待查表为有序顺序表(不能是链表),且插入删除困难
  • 二分法查找算法的思路:
    • 假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功.
    • 否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
    • 重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
      Python数据结构与算法_第6节_排序 & 搜索

二分查找实现

# coding:utf-8

def binary_search_recursion(alist, item):
	"""二分查找,递归版本"""
	n = len(alist)
	# 递归的终止条件
	if n > 0:
		mid = n // 2
		if alist[mid] == item:
			return True
		elif item < alist[mid]:
			binary_search_recursion(alist[:mid], item)
		else:
			binary_search_recursion(alist[mid+1:, item])
	return False

def binary_search_non_recursion(alist, item):
	"""二分查找,非递归版本"""
	n = len(alist)
	first = 0
	last = n-1
	while first <= last:
		mid = (first + last) //2
		if alist[mid] == item:
			return True
		elif item < alist[mid]:
			last = mid - 1
		else:
			first = mid + 1
	return False

时间复杂度

  • 最优时间复杂度:

    O

    (

    1

    )

    O(1)

    O(1)

  • 最坏时间复杂度:

    O

    (

    log

    n

    )

    O(/log n)

    O(logn)

未经允许不得转载:作者:1389-李同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Python数据结构与算法_第6节_排序 & 搜索》 发布于2020-12-02

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录