算法——列表排序和常用排序算法
目录
- 一、列表排序
- 二、常见排序算法
- 1、冒泡排序（Bubble Sort）
- 2、选择排序（Selection Sort）
- 3、插入排序（Insertion Sort）
- 4、快速排序（Quick Sort）
- 5、堆排序（Heap-Sort）
- 6、归并排序（Merge-Sort）
- 三、排序总结
- 1、冒泡排序、选择排序、插入排序
- 2、快速排序、堆排序、归并排序
- 3、六种排序算法对比总结
正文
一、列表排序
排序就是将一组“无序”的记录序列调整为“有序”的记录序列。
列表排序：将无序列表变为有序列表。
输入：列表
输出：有序列表
两种基本的排序方式：升序和降序。
python内置的排序函数：sort()。
二、常见排序算法
|
名称 |
复杂度 |
说明 |
备注 |
|
冒泡排序 |
O(N*N) |
将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮 |
|
|
插入排序 Insertion sort |
O(N*N) |
逐一取出元素，在已经排序的元素序列中从后向前扫描，放到适当的位置 |
起初，已经排序的元素序列为空 |
|
选择排序 |
O(N*N) |
首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此递归。 |
|
|
快速排序 Quick Sort |
O(n *log2(n)) |
先选择中间值，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使用这个过程（递归）。 |
|
|
堆排序HeapSort |
O(n *log2(n)) |
利用堆（heaps）这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是小于（或者大于）它的父节点。 |
近似完全二叉树 |
|
希尔排序 SHELL |
O(n1+￡) 0<￡<1 |
选择一个步长(Step) ,然后按间隔为步长的单元进行排序.递归,步长逐渐变小,直至为1. |
|
|
箱排序 |
O(n) |
设置若干个箱子，把关键字等于 k 的记录全都装入到第k 个箱子里 ( 分配 ) ，然后按序号依次将各非空的箱子首尾连接起来 ( 收集 ) 。 |
分配排序的一种：通过' 分配 ' 和 ' 收集 ' 过程来实现排序。 |
1、冒泡排序（Bubble Sort）
列表每两个相邻的数，如果前面比后面大，则交换这两个数。
一趟排序完成后，则无序区减少一个数，有序区增加一个数。
代码关键点：趟、无序区范围。
（1）图示说明
这样排序一趟后，最大的数9，就到了列表最顶成为了有序区，下面的部分则还是无序区。然后在无序区不断重复这个过程，每完成一趟排序，无序区减少一个数，有序区增加一个数。图示最后一张图要开始第六趟排序，排序从第0趟开始计数。剩一个数的时候不需要排序了，因此整个排序排了n-1趟。
（2）代码示例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
import randomdef bubble_sort(li): for i in range(len(li)-1): # 总共是n-1趟 for j in range(len(li)-i-1): # 每一趟都有箭头，从0开始到n-i-1 if li[j] > li[j+1]: # 比对箭头指向和箭头后面的那个数的值 # 当箭头所指数大于后面的数时交换位置, 升序排列；条件相反则为降序排列 li[j], li[j+1] = li[j+1], li[j]li = [random.randint(0, 10000) for i in range(30)]print(li)bubble_sort(li)print(li)'''[5931, 5978, 6379, 4217, 9597, 4757, 4160, 3310, 6916, 2463, 9330, 8043, 8275, 5614, 8908, 7799, 9256, 3097, 9447, 9327, 7604, 9464, 417, 927, 1720, 145, 6451, 7050, 6762, 6608][145, 417, 927, 1720, 2463, 3097, 3310, 4160, 4217, 4757, 5614, 5931, 5978, 6379, 6451, 6608, 6762, 6916, 7050, 7604, 7799, 8043, 8275, 8908, 9256, 9327, 9330, 9447, 9464, 9597]''' |
如果要打印出每次排序结果：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
import randomdef bubble_sort(li): for i in range(len(li)-1): # 总共是n-1趟 for j in range(len(li)-i-1): # 每一趟都有箭头，从0开始到n-i-1 if li[j] > li[j+1]: # 比对箭头指向和箭头后面的那个数的值 # 当箭头所指数大于后面的数时交换位置, 升序排列；条件相反则为降序排列 li[j], li[j+1] = li[j+1], li[j] print(li)li = [random.randint(0, 10000) for i in range(5)]print(li)bubble_sort(li)print(li)'''[1806, 212, 4314, 1611, 8355][212, 1806, 1611, 4314, 8355][212, 1611, 1806, 4314, 8355][212, 1611, 1806, 4314, 8355][212, 1611, 1806, 4314, 8355][212, 1611, 1806, 4314, 8355]''' |
（3）算法时间复杂度
n是列表的长度，算法中也没有发生循环折半的过程，具备两层关于n的循环，因此它的时间复杂度是O(n2)。
（4）冒泡排序优化
如果在一趟排序过程中没有发生交换就可以认定已经排好序了。因此可做如下优化：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
|
import randomdef bubble_sort(li): for i in range(len(li)-1): # 总共是n-1趟 exchange = False for j in range(len(li)-i-1): # 每一趟都有箭头，从0开始到n-i-1 if li[j] > li[j+1]: # 比对箭头指向和箭头后面的那个数的值 # 当箭头所指数大于后面的数时交换位置, 升序排列；条件相反则为降序排列 li[j], li[j+1] = li[j+1], li[j] exchange = True # 如果发生了交换就置为true print(li) if not exchange: # 如果exchange还是False，说明没有发生交换，结束代码 return# li = [random.randint(0, 10000) for i in range(5)]li = [1806, 212, 4314, 1611, 8355]bubble_sort(li)'''[212, 1806, 1611, 4314, 8355][212, 1611, 1806, 4314, 8355][212, 1611, 1806, 4314, 8355]''' |
对比前面排序的次数少了很多，算法得到了优化~
2、选择排序（Selection Sort）
一趟遍历完记录最小的数，放到第一个位置；再一趟遍历记录剩余列表中的最小的数，继续放置。
算法关键点：有序区和无序区、无序区最小数的位置。
（1）简单的选择排序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14
|
def select_sort_simple(li): li_new = [] for i in range(len(li)): min_val = min(li) # 找到最小的数，也需要遍历一边O(n) li_new.append(min_val) li.remove(min_val) # 按值删除，如果有重复的先删除最左边的,删除之后，后面元素需要向前移动补位，因此也是O(n) return li_newli = [3, 2, 4, 1, 5, 6, 8, 7, 9]print(select_sort_simple(li))'''[1, 2, 3, 4, 5, 6, 7, 8, 9]''' |
注意这里的remove操作和min操作都不是O(1)的操作，都需要进行遍历，因此它的时间复杂度是O(n2)。
而且前面冒泡排序是原地排序不需要开启一个新的列表，二这个版本的选择排序不是原地排序，多占了一份内存。
（2）优化后的选择排序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14
|
def select_sort(li): # 和冒泡排序类似，在n-1趟完成后，无序区只剩一个数，这个数一定是最大的 for i in range(len(li)-1): # i是第几趟 min_loc = i # 最小值的位置 for j in range(i+1, len(li)): # 遍历无序区，从i开始是自己跟自己比，因此从i+1开始 if li[j] < li[min_loc]: # 如果遍历的这个数小于现在min_loc位置上的数 min_loc = j # 修改min_loc的index，循环完后，min_loc一定是无序区最小数的下标 li[i], li[min_loc] = li[min_loc], li[i] # 将i和min_loc对应的值进行位置交换 print(li) # 打印每趟执行完的排序，分析过程li = [3, 2, 4, 1, 5, 6, 8, 7, 9]select_sort(li)# print(li) # [1, 2, 3, 4, 5, 6, 7, 8, 9] |
这里只有两层循环，时间复杂度是O(n2)。
3、插入排序（Insertion Sort）
元素被分为有序区和无序区两部分。初始时手里（有序区）只有一张牌，每次（从无序区）摸一张牌，插入到手里已有牌的正确位置，直到无序区变空。
（1）图示说明
一开始手里的牌只有5
第一张摸到的牌是7，比5大插到5的右边：
第二张摸到的牌是4，需要将5和7的位置向右挪，将4插到最前面：
后面的情况依次类推。
（2）代码示例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
def insert_sort(li): for i in range(1, len(li)): # i表示摸到牌的下标 tmp = li[i] # 摸到的牌 j = i - 1 # j指得是手里牌的下标 while li[j] > tmp and j >= 0: # 循环条件 ''' 循环终止条件：如果手里最后一张牌 <= 摸到的牌 or j == -1 比如手里有牌457，新摸到一张6(index=3)，当比对5与6时，5<6,满足了循环终止条件，插到列表j+1处，即index=2处. 比如手里的牌是4567,新摸到一张3(index=4)，一个个比对均比3大，到4与3比较时，由于比4小，再次循环j=-1，满足终止条件插到列表j+1处，即最前面 ''' li[j + 1] = li[j] # 通过循环条件，将手里的牌左移 j -= 1 # 手里的牌对比箭头左移 li[j + 1] = tmp # 将摸到的牌插入有序区 print(li) # 打印每一趟排序过程li = [3, 2, 4, 1, 5, 6, 9, 6, 8]print('原列表', li)insert_sort(li)print('排序结果', li) |
这个循环主要是在找插入的位置。
时间复杂度：O(n2)。
（3）查看排序算法执行时间和效率
准备好cal_time.py:
|
1 2 3 4 5 6 7 8 9 10 11
|
import timedef cal_time(func): def wrapper(*args, **kwargs): t1 = time.time() result = func(*args, **kwargs) t2 = time.time() print('%s running time: %s secs.' % (func.__name__, t2 - t1)) return result return wrapper |
检查10000个随机数字排序：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
|
import randomfrom cal_time import *@cal_timedef insert_sort(li): for i in range(1, len(li)): # i表示摸到牌的下标 tmp = li[i] # 摸到的牌 j = i - 1 # j指得是手里牌的下标 while li[j] > tmp and j >= 0: # 循环条件 li[j + 1] = li[j] # 通过循环条件，将手里的牌左移 j -= 1 # 手里的牌对比箭头左移 li[j + 1] = tmp # 将摸到的牌插入有序区 # print(li) # 打印每一趟排序过程li = list(range(10000))random.shuffle(li)insert_sort(li)'''insert_sort running time: 4.496495723724365 secs.''' |
4、快速排序（Quick Sort）
快速排序思路：取一个元素p（第一个元素），使元素p归位；列表被p分为两部分，左边都比p小，右边都比p大；递归完成排序。
算法关键点：归位、递归。
（1）图示说明
（2）元素归位过程分析
5要归位，先用一个变量将5存起来，两个箭头表示当前列表的left和right:
列表左边有了一个空位，从右边开始找一个比5小的数填入：
此时右边有了一个空位，右边是给比5大的数准备的，从左边开始找比5大的数填入：
同理，此时左边又有了空位继续从右边开始找比5小的数填过去，以此类推
最后要找比5大的数放到右边去，但是3<5，这时left和right重合了，此时说明位置已经在中间了，将5放回。
（3）归位代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
|
def partition(li, left, right): ''' 归位函数 :param li: 列表 :param left: 左箭头 :param right: 右箭头 :return: ''' tmp = li[left] while left < right: while left < right and li[right] >= tmp: # 从右边找一个比tmp小的数放过来 # 注意由于循环条件是li[right] >= tep，在两个箭头相遇时不会退出循环，因此添加left<right条件 right -= 1 # 如果比tmp大则right往左走一步 li[left] = li[right] # 将右边找的数插入到左边空位处 print(li) # 打印排序过程 while left<right and li[left] <= tmp: # 从左边找一个比tmp大的数放入右边的空位 left += 1 # 如果比tmp小则left往右走一步 li[right] = li[left] # 将左边的值写入到右边空位处 print(li) # 打印排序过程 # 循环终止条件：left>=right li[left] = tmp # 将tmp归位li = [5,7,4,6,3,1,2,9,8]print('原列表', li)partition(li, 0, len(li)-1)print('排序结果', li)'''原列表 [5, 7, 4, 6, 3, 1, 2, 9, 8][2, 7, 4, 6, 3, 1, 2, 9, 8][2, 7, 4, 6, 3, 1, 7, 9, 8][2, 1, 4, 6, 3, 1, 7, 9, 8][2, 1, 4, 6, 3, 6, 7, 9, 8][2, 1, 4, 3, 3, 6, 7, 9, 8][2, 1, 4, 3, 3, 6, 7, 9, 8]排序结果 [2, 1, 4, 3, 5, 6, 7, 9, 8]''' |
注意无论从左边找还是从右边找，都需要添加left<right条件，在箭头相遇时跳出循环。还可以注意到每次写入空位，并不是真正的空位，仍由原元素占位在空位出，直到tmp归位，整个列表才没有了重复的元素。
（4）快速排序代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
|
def partition(li, left, right): ''' 归位函数 :param li: 列表 :param left: 左箭头 :param right: 右箭头 :return: ''' tmp = li[left] while left < right: while left < right and li[right] >= tmp: # 从右边找一个比tmp小的数放过来 # 注意由于循环条件是li[right] >= tep，在两个箭头相遇时不会退出循环，因此添加left<right条件 right -= 1 # 如果比tmp大则right往左走一步 li[left] = li[right] # 将右边找的数插入到左边空位处 print(li) # 打印排序过程 while left<right and li[left] <= tmp: # 从左边找一个比tmp大的数放入右边的空位 left += 1 # 如果比tmp小则left往右走一步 li[right] = li[left] # 将左边的值写入到右边空位处 print(li) # 打印排序过程 # 循环终止条件：left>=right li[left] = tmp # 将tmp归位 return leftdef quick_sort(li, left, right): '''快速排序两个关键：归位、递归''' if left < right: # 至少有两个元素 mid = partition(li, left, right) quick_sort(li, left, mid-1) quick_sort(li, mid+1, right)li = [5,7,4,6,3,1,2,9,8]quick_sort(li, 0, len(li)-1)print(li) |
注意这里使用了partition归位函数和快速排序递归框架完成了快速排序设计。
（5）快速排序的效率
快速排序的时间复杂度：O(nlogn)，每一层排序的复杂度是O(n)，总共有logn层。
（6）快速排序改写
想给quick_sort添加装饰器查看排序运行效率，但是递归函数不能添加装饰器，因此需要做如下改写：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14
|
from cal_time import *def partition(li, left, right):......def _quick_sort(li, left, right): '''快速排序两个关键：归位、递归''' if left < right: # 至少有两个元素 mid = partition(li, left, right) _quick_sort(li, left, mid-1) _quick_sort(li, mid+1, right)@cal_timedef quick_sort(li): _quick_sort(li, 0, len(li)-1) |
（7）测试验证快排和冒泡排序执行效率
冒泡排序和快速排序效率对比
对比运行时间，可以发现针对10000个元素的数组排序，快速排序的效率比冒泡排序高了几百倍。
时间复杂度O(nlogn)和O(n2)在数量越大的情况下，效率相差将越来越大。
快速排序的最好情况时间复杂度是O(n)，一般情况时间复杂度是O(nlogn)，最坏情况时间复杂度是O(n2)。
（8）快速排序存在的问题
首先python有一个递归最大深度的问题，默认是999，修改递归最大深度方法：
|
1 2 3
|
import syssys.setrecursionlimit(100000) # 修改递归最大深度 |
虽然可以修改；而且递归会相当消耗一部分的系统资源。
其次快速排序有一个最坏情况出现：倒序排列的数组，在这种情况下，快速排序无法两边同时排序，每次只能排序一个数字。因此在这种情况下快速排序的时间复杂度是：O(n2)。
加入随机化解决该问题：即不再找第一个元素归位，而是随机找一个值与第一个元素交换，然后继续执行快速排序，就可以解决倒序例子时间复杂度特别高的情况。但是这个方法不能完全避免最坏情况，比如每次随机都恰好选中了最大的一个数，但是这种修改可以让最坏情况无法被设计出来，发生最坏情况的概率也会非常非常小。
5、堆排序（Heap-Sort）
6、归并排序（Merge-Sort）
三、排序总结
1、冒泡排序、选择排序、插入排序
冒泡排序、选择排序、插入排序的时间复杂度都是O(n2)，且都是原地排序。
2、快速排序、堆排序、归并排序
快速排序、堆排序、归并排序这三种排序算法的时间复杂度都是O(nlogn)。 但有常数差异。
（1）一般情况下，就运行时间来比较：
快速排序（速度最快）< 归并排序 < 堆排序
（2）三种排序算法的缺点：
快速排序：极端情况下排序效率低。
归并排序：需要额外的内存开销。
堆排序：在快的排序算法中相对较慢。
3、六种排序算法对比总结
（1）递归占用空间
递归需要用系统占的空间，快速排序在平均情况下需要递归logn层，所以平均情况下需要消耗O(logn)的空间复杂度；最坏情况下需要递归n层，因此需要消耗O(n)的时间复杂度。
归并虽然也有递归，但他已经开了一个列表了占用O(n)，归并递归需要的空间复杂度是O(logn)小于O(n)，因此统计空间复杂度是O(n)。
（2）排序算法稳定性
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
判断是否算法是否稳定：挨着换的稳定，不挨着换的不稳定。
（3）代码复杂度
算法是否好写，是否容易理解。