1. 排序
1.1 冒泡排序
1.2 选择排序
1.3 插入排序
1.4 希尔排序
1.5 快速排序
2. 搜索
1. 排序
排序算法 (英语: Sorting algorithm) 是一种能将一串数据依照特定顺序进行排列的一种算法.
排序算法的稳定性
稳定性: 稳定排序算法会让原本有相等键值的纪录维持相对次序. 也就是如果一个排序算法是稳定的, 当有两个相等键值的纪录 R 和 S, 且在原本的列表中 R 出现在 S 之前, 在排序过的列表中 R 也将会是在 S 之前.
当相等的元素是无法分辨的, 比如像是整数, 稳定性并不是一个问题. 然而, 假设以下的数对将要以他们的第一个数字来排序.
(4, 1) (3, 1) (3, 7) (5, 6)
在这个状况下, 有可能产生两种不同的结果, 一个是让相等键值的纪录维持相对的次序, 而另外一个则没有:
- (3, 1) (3, 7) (4, 1) (5, 6) (维持次序)
- (3, 7) (3, 1) (4, 1) (5, 6) (次序被改变)
不稳定排序算法可能会在相等的键值中改变纪录的相对次序, 但是稳定排序算法从来不会如此. 不稳定排序算法可以被特别地实现为稳定. 作这件事情的一个方式是人工扩充键值的比较, 如此在其他方面相同键值的两个对象间之比较,(比如上面的比较中加入第二个标准: 第二个键值的大小)就会被决定使用在原先数据次序中的条目, 当作一个同分决赛. 然而, 要记住这种次序通常牵涉到额外的空间负担.
常见算法效率比较
性能从优到劣:
1.1 冒泡排序
介绍
冒泡排序 (英语: Bubble Sort) 是一种简单的排序算法. 它重复地遍历要排序的数列, 一次比较两个元素, 如果他们的大小顺序有误则把它们交换过来. 遍历数列的工作是重复地进行直到没有元素再需要交换, 也就是说该数列已经排序完成. 这个算法的名字由来是因为越小的元素会经由交换慢慢 "浮" 到数列的顶端.
冒泡排序算法的运作如下:
比较相邻的元素. 如果第一个比第二个大(升序), 就交换他们两个.
对每一对相邻元素作同样的工作, 从开始第一对到结尾的最后一对. 这步做完后, 最后的元素会是最大的数.
针对所有的元素重复以上的步骤, 除了最后一个.
持续每次对越来越少的元素重复上面的步骤, 直到没有任何一对元素需要比较.
交换过程图示(第一次遍历)
那么我们需要进行 n-1 次冒泡过程, 每次对应的比较次数如下图所示:
演示效果
代码实现
- def bubble_sort(alist):
- "冒泡排序"
- n = len(alist)
- for j in range(n-1): # 控制遍历的次数(图示中的 Pass)
- count = 0
- for i in range(n-1-j): # 每次遍历需要比较的次数, 逐渐减少(图示中的 Comparisons)
- if alist[i]> alist[i+1]:
- alist[i], alist[i+1] = alist[i+1], alist[i]
- count += 1
- # 优化算法复杂度, 若第一遍遍历时没有交换元素, 即代表元素本身已排好序. 例如[1, 2, 3]
- # 无需再进行第二次遍历, 即可直接退出
- if count == 0:
- return
- # j: 0 i: range(n-1-0) = n-1
- # j: 1 i: range(n-1-1) = n-2
- # j: 2 i: range(n-1-2) = n-3
- # ...
- # j: n-2 i: range(n-1-(n-2)) = 1
- if __name__ == "__main__":
- li = [1, 21, 4, 2, 56, 2, 34, 67]
- bubble_sort(li)
- print(li) # [1, 2, 2, 4, 21, 34, 56, 67]
时间复杂度
最优时间复杂度: O(n)(表示第一次遍历发现没有任何可以交换的元素, 则排序结束)
最坏时间复杂度: O(n^2)
稳定性: 稳定
1.2 选择排序
选择排序 (Selection sort) 是一种简单直观的排序算法. 它的工作原理如下:
在未排序序列中找到最小 (大) 元素, 存放到排序序列的起始位置.
从剩余未排序元素中继续寻找最小 (大) 元素, 然后放到已排序序列的末尾.
以此类推, 直到所有元素均排序完毕.
选择排序的主要优点与数据移动有关. 如果某个元素位于正确的最终位置上, 则它不会被移动. 选择排序每次交换一对元素, 它们当中至少有一个将被移到其最终位置上, 因此对 n 个元素的表进行排序总共进行至多 n-1 次交换. 在所有的完全依靠交换去移动元素的排序方法中, 选择排序属于非常好的一种.
排序过程图示
红色表示当前最小值, 黄色表示已排序序列, 蓝色表示当前位置.
演示效果
代码实现
- def selected_sort(alist):
- n = len(alist)
- # 需要进行 n-1 次选择操作
- for i in range(n-1):
- # 记录最小位置
- min_index = i
- # 从 i+1 位置到末尾, 选择出最小的元素
- for j in range(i+1, n):
- if alist[j] <alist[min_index]:
- min_index = j
- # 如果选择出的元素不在正确位置, 进行交换
- if min_index != i:
- alist[i], alist[min_index] = alist[min_index], alist[i]
- alist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
- selected_sort(alist)
- print(alist)
时间复杂度
最优时间复杂度: O(n^2)
最坏时间复杂度: O(n^2)
稳定性: 不稳定(考虑升序每次选择最大的情况)
1.3 插入排序
插入排序 (英语: Insertion Sort) 是一种简单直观的排序算法. 它的工作原理是通过构建有序序列, 对于未排序数据, 在已排序序列中从后向前扫描, 找到相应位置并插入. 插入排序在实现上, 在从后向前扫描过程中, 需要反复把已排序元素逐步向后挪位, 为最新元素提供插入空间.
排序过程图示
演示效果
代码实现
- def insert_sort(alist):
- n = len(alist)
- # 从第二个位置开始(未排序数据), 即把下标为 1 的元素开始向前插入(有序数据)
- for i in range(1, n):
- # 从第 i 个元素开始向前比较, 如果小于前一个元素, 则交换
- for j in range(i, 0, -1):
- if alist[j] < alist[j-1]:
- alist[j], alist[j-1] = alist[j-1], alist[j]
- alist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
- insert_sort(alist)
- print(alist)
时间复杂度
最优时间复杂度: O(n)(升序排列, 序列已经处于升序状态)
最坏时间复杂度: O(n^2)
稳定性: 稳定
1.4 希尔排序
希尔排序 (Shell Sort) 是插入排序的一种. 也称缩小增量排序, 是直接插入排序算法的一种更高效的改进版本. 希尔排序是非稳定排序算法. 该方法因 DL.Shell 于 1959 年提出而得名. 希尔排序是把记录按下标的一定增量分组, 对每组使用直接插入排序算法排序; 随着增量逐渐减少, 每组包含的关键词越来越多, 当增量减至 1 时, 整个文件恰被分成一组, 算法便终止.
希尔排序过程
希尔排序的基本思想是: 将数组列在一个表中并对列分别进行插入排序, 重复这过程, 不过每次用更长的列 (步长更长了, 列数更少了) 来进行. 最后整个表就只有一列了. 将数组转换至表是为了更好地理解这算法, 算法本身还是使用数组进行排序.
例如, 假设有这样一组数 [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ], 如果我们以步长为 5 开始进行排序, 我们可以通过将这列表放在有 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 步长进行排序(此时就是简单的插入排序了).
示例分析
演示效果
代码实现
- def shell_sort(alist):
- n = len(alist)
- # 初始步长
- gap = n / 2
- while gap> 0:
- # 按步长进行插入排序
- for i in range(gap, n):
- j = i
- # 插入排序
- while j>=gap and alist[j-gap]> alist[j]:
- alist[j-gap], alist[j] = alist[j], alist[j-gap]
- j -= gap
- # 得到新的步长
- gap = gap / 2
- alist = [54,26,93,17,77,31,44,55,20]
- shell_sort(alist)
- print(alist)
时间复杂度
最优时间复杂度: 根据步长序列的不同而不同
最坏时间复杂度: O(n2)
稳定想: 不稳定
1.5 快速排序
快速排序(英语: Quicksort), 又称划分交换排序(partition-exchange sort), 通过一趟排序将要排序的数据分割成独立的两部分, 其中一部分的所有数据都比另外一部分的所有数据都要小, 然后再按此方法对这两部分数据分别进行快速排序, 整个排序过程可以递归进行, 以此达到整个数据变成有序序列.
步骤为:
从数列中挑出一个元素, 称为 "基准"(pivot).
重新排序数列, 所有元素比基准值小的摆放在基准前面, 所有元素比基准值大的摆在基准的后面 (相同的数可以到任一边). 在这个分区结束之后, 该基准就处于数列的中间位置. 这个称为分区(partition) 操作.
递归地 (recursive) 把小于基准值元素的子数列和大于基准值元素的子数列排序.
递归的最底部情形, 是数列的大小是零或一, 也就是永远都已经被排序好了. 虽然一直递归下去, 但是这个算法总会结束, 因为在每次的迭代 (iteration) 中, 它至少会把一个元素摆到它最后的位置去.
排序过程图示
演示效果
代码实现
方式一: 改变原列表
- def quick_sort(alist, start, end):
- # 递归的退出条件
- if start>= end:
- return
- # 设定起始元素为要寻找位置的基准元素
- mid = alist[start]
- # low 为从左往右的游标
- low = start
- # high 为从右往左的游标
- high = end
- # 当 low 与 high 未重合
- while low <high:
- # 当 low 与 high 未重合时, 若 high 指向的元素不比基准元素小, 则 high 向左移动一位
- while low < high and alist[high]>= mid:
- high -= 1
- # 若 high 指向的元素比基准元素小, 则推出循环, 交换元素位置
- alist[low] = alist[high]
- # 当 low 与 high 未重合时, 若 low 指向的元素比基准元素小, 则 low 向右移动一位
- while low <high and alist[low] < mid:
- low += 1
- # 若 low 指向的元素比基准元素大, 则推出循环, 交换元素位置
- alist[high] = alist[low]
- # 当 low 与 high 重合, 推出循环, 此时所指位置为基准元素的正确位置
- # 将基准元素放到该位置
- alist[low] = mid
- # 对基准元素左边的子序列进行快速排序
- quick_sort(alist, start, low-1)
- # 对基准元素右边的子序列进行快速排序
- quick_sort(alist, low+1, end)
- alist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
- quick_sort(alist, 0, len(alist)-1)
- print(alist)
方式二: 不改变原列表
- def quick_sort(alist):
- if len(alist) <= 1:
- return alist
- pivot = alist[0]
- left = [x for x in alist if x < pivot]
- middle = [x for x in alist if x == pivot]
- right = [x for x in alist if x> pivot]
- return quick_sort(left) + middle + quick_sort(right)
- alist = [54, 226, 93, 17, 77, 31, 44, 55, 20]
- print(quick_sort(alist))
时间复杂度
最优时间复杂度: O(nlogn)
最坏时间复杂度: O(n^2)
稳定性: 不稳定
从一开始快速排序平均需要花费 O(n log n)时间的描述并不明显. 但是不难观察到的是分区运算, 数组的元素都会在每次循环中走访过一次, 使用 O(n)的时间. 在使用结合 (concatenation) 的版本中, 这项运算也是 O(n).
在最好的情况, 每次我们运行一次分区, 我们会把一个数列分为两个几近相等的片段. 这个意思就是每次递归调用处理一半大小的数列. 因此, 在到达大小为一的数列前, 我们只要作 log n 次嵌套的调用. 这个意思就是调用树的深度是 O(log n). 但是在同一层次结构的两个程序调用中, 不会处理到原来数列的相同部分; 因此, 程序调用的每一层次结构总共全部仅需要 O(n)的时间 (每个调用有某些共同的额外耗费, 但是因为在每一层次结构仅仅只有 O(n) 个调用, 这些被归纳在 O(n)系数中). 结果是这个算法仅需使用 O(nlogn)时间.
- def merge_sort(alist):
- """归并排序"""
- n = len(alist)
- if n <= 1:
- return alist
- mid = n // 2
- # left 采用归并排序后形成的有序的新的列表
- left_li = merge_sort(alist[:mid])
- # right 采用归并排序后形成的有序的新的列表
- right_li = merge_sort(alist[mid:])
- # 将两个有序的子序列合并为一个新的整体
- # merge(left, right)
- left_pointer, right_pointer = 0, 0
- result = []
- while left_pointer <len(left_li) and right_pointer < len(right_li):
- 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
- if __name__ == "__main__":
- li = [54, 26, 93, 17, 77, 31, 44, 55, 20]
- print(li)
- sorted_li = merge_sort(li)
- print(li)
- print(sorted_li)
- def binary_search(alist, item):
- """二分查找法: 递归实现"""
- n = len(alist)
- if n> 0:
- mid = n // 2
- if item == alist[mid]:
- return True
- elif item < alist[mid]:
- return binary_search(alist[:mid], item)
- else:
- return binary_search(alist[mid+1:], item)
- # n=0, 即未找到该元素
- return False
- if __name__ == '__main__':
- li = [1, 2, 34, 45, 65, 78]
- print(binary_search(li, 2)) # True
- print(binary_search(li, 44)) # False
- def binary_search(alist, item):
- """二分查找法: 非递归实现"""
- n = len(alist)
- first = 0 # 第一个下标
- last = n - 1 # 最后一个下标
- while first <= last:
- mid = (first + last) // 2 # 中间下标
- if item == alist[mid]:
- return True
- elif item < alist[mid]:
- last = mid - 1
- else:
- first = mid + 1
- return False
- if __name__ == '__main__':
- li = [1, 2, 34, 45, 65, 78]
- print(binary_search(li, 2)) # True
- print(binary_search(li, 44)) # False
来源: http://www.bubuko.com/infodetail-3498756.html