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

首页 » 数据结构 » 正文

排序与搜索(sorting algorithm)

希尔排序(shell sorting)

  • 希尔排序(shell sorting)/缩小增量排序:是插入排序算法的更高效的优化版本。
  • 希尔排序算法的思路:
    • 选取步长(gap),可以为序列长度/2。
    • 根据步长,把序列分成序列长度/2个sub-series,然后再每个sub-series中应用插入排序。
    • 缩减步长至上个步长/2,并重复以上步骤。

希尔排序的分析

  • 如果步长选择的好的话,时间复杂度不会比选择排序大太多。

加入有一组序列[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],以步长为5开始进行希尔排序,则会得到(竖着的元素是步长组成)
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行插入排序:
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]。这时10已经移至正确位置了,然后再以3为步长进行排序:
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为:
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序(此时就是简单的插入排序了)

希尔排序的实现

# coding=utf-8
def shell_sort(alist):
	"""希尔排序"""
	n = len(alist)
	gap = n // 2
	
	# gap变化到0之前,插入算法执行的次数 
	while gap > 0:
		# 插入算法,与普通插入算法的区别就是gap步长
		for j in range(gap, n):
			# j = [gap, gap+1, gap+2, ..., n-1]
			i = j
			while i > 0:
				if alist[i] < alist[i-gap]:
					alist[i], alist[i-gap] = alist[i-gap], alist[i]
					i -= gap
				else:
					break
		# 缩短gap步长
		gap //= 2

时间复杂度

  • 最优时间复杂度:根据步长序列的不同而不同
  • 最坏时间复杂度:O(n2)
  • 稳定性:不稳定

快速排序 / 划分交换排序(Quicksort / partition-exchange sort)

  • 从数列中挑出一个元素,称为"基准"(pivot)。
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。如果左边大右边小,则交换两个元素的位置。
  • 在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  • 前面的区都比pivot小,后面的区都比pivot大。
  • 递归地(recursive)在两个区内分别再次重复以上步骤。

快速排序的分析

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

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

快速排序的实现

# coding:utf-8
def quick_sort(alist, first, last):
	"""快速排序"""
	# 递归的终止条件:传进来的是长度为1个元素的子序列
	if first >= last:
		return
	
	mid_value = alist[first]
	low = first
	high = last

	while low < high:
		# 让high游标左移
		while low < high and alist[high] >= mid_value:
				high -= 1
		alist[low] = alist[high]

		# 与high游标交替,让low游标右移
		while low < high and alist[low] < mid_value:
			low += 1
		alist[high] = alist[low]
	# 从循环退出时,low与high重合,此时所指位置为基准元素的正确位置
	 # 将基准元素放到该位置
	alist[low] = mid_value
	
	# 对mid左边的子序列进行快速排序
	quick_sort(alist, first, low-1)
	# 对mid右边的子序列进行快速排序
	quick_sort(alist, low+1, last)

时间复杂度`

  • 最优时间复杂度:

    O

    (

    n

    log

    n

    )

    O(n*/log{n})

    O(nlogn)

  • 最坏时间复杂度:

    O

    (

    n

    2

    )

    O(n^2)

    O(n2)

  • 稳定性:不稳定

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

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录