算法——列表排序和常用排序算法

王野yvvrnyam9s 2021-01-24

展开全文

一、列表排序
二、常见排序算法　　
三、排序总结

正文

回到顶部

一、列表排序

　　排序就是将一组“无序”的记录序列调整为“有序”的记录序列。

　　列表排序：将无序列表变为有序列表。

　　　　输入：列表

　　　　输出：有序列表

　　两种基本的排序方式：升序和降序。

　　python内置的排序函数：sort()。

回到顶部

二、常见排序算法　　

名称	复杂度	说明	备注
冒泡排序 Bubble Sort	O(N*N)	将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮
插入排序 Insertion sort	O(N*N)	逐一取出元素，在已经排序的元素序列中从后向前扫描，放到适当的位置	起初，已经排序的元素序列为空
选择排序	O(N*N)	首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此递归。
快速排序 Quick Sort	O(n *log₂(n))	先选择中间值，然后把比它小的放在左边，大的放在右边（具体的实现是从两边找，找到一对后交换）。然后对两边分别使用这个过程（递归）。
堆排序HeapSort	O(n *log₂(n))	利用堆（heaps）这种数据结构来构造的一种排序算法。堆是一个近似完全二叉树结构，并同时满足堆属性：即子节点的键值或索引总是小于（或者大于）它的父节点。	近似完全二叉树
希尔排序 SHELL	O(n¹⁺^￡) 0<￡<1	选择一个步长(Step) ,然后按间隔为步长的单元进行排序.递归,步长逐渐变小,直至为1.
箱排序 Bin Sort	O(n)	设置若干个箱子，把关键字等于 k 的记录全都装入到第k 个箱子里 ( 分配 ) ，然后按序号依次将各非空的箱子首尾连接起来 ( 收集 ) 。	分配排序的一种：通过' 分配 ' 和 ' 收集 ' 过程来实现排序。

1、冒泡排序（Bubble Sort）

　　列表每两个相邻的数，如果前面比后面大，则交换这两个数。

　　一趟排序完成后，则无序区减少一个数，有序区增加一个数。

　　代码关键点：趟、无序区范围。

（1）图示说明

　　这样排序一趟后，最大的数9，就到了列表最顶成为了有序区，下面的部分则还是无序区。然后在无序区不断重复这个过程，每完成一趟排序，无序区减少一个数，有序区增加一个数。图示最后一张图要开始第六趟排序，排序从第0趟开始计数。剩一个数的时候不需要排序了，因此整个排序排了n-1趟。

（2）代码示例

import random

def 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]

'''

　　如果要打印出每次排序结果：

import random

def 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]

'''

（3）算法时间复杂度

　　n是列表的长度，算法中也没有发生循环折半的过程，具备两层关于n的循环，因此它的时间复杂度是O(n²)。

（4）冒泡排序优化

　　如果在一趟排序过程中没有发生交换就可以认定已经排好序了。因此可做如下优化：

import random

def 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]

'''

　　对比前面排序的次数少了很多，算法得到了优化~

2、选择排序（Selection Sort）

　　一趟遍历完记录最小的数，放到第一个位置；再一趟遍历记录剩余列表中的最小的数，继续放置。

　　算法关键点：有序区和无序区、无序区最小数的位置。

（1）简单的选择排序

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_new

li = [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(n²)。

　　而且前面冒泡排序是原地排序不需要开启一个新的列表，二这个版本的选择排序不是原地排序，多占了一份内存。

（2）优化后的选择排序

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(n²)。

3、插入排序（Insertion Sort）

　　元素被分为有序区和无序区两部分。初始时手里（有序区）只有一张牌，每次（从无序区）摸一张牌，插入到手里已有牌的正确位置，直到无序区变空。

（1）图示说明

　　一开始手里的牌只有5

　　第一张摸到的牌是7，比5大插到5的右边：

　　第二张摸到的牌是4，需要将5和7的位置向右挪，将4插到最前面：

　　后面的情况依次类推。

（2）代码示例

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(n²)。

（3）查看排序算法执行时间和效率

　　准备好cal_time.py:

import time

def 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个随机数字排序：

import random

from cal_time import *

@cal_time

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: # 循环条件

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）归位代码实现

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, 5, 6, 7, 9, 8]

'''

　　注意无论从左边找还是从右边找，都需要添加left<right条件，在箭头相遇时跳出循环。还可以注意到每次写入空位，并不是真正的空位，仍由原元素占位在空位出，直到tmp归位，整个列表才没有了重复的元素。

（4）快速排序代码实现

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 left

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)

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添加装饰器查看排序运行效率，但是递归函数不能添加装饰器，因此需要做如下改写：

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_time

def quick_sort(li):

_quick_sort(li, 0, len(li)-1)

（7）测试验证快排和冒泡排序执行效率

# -*- coding:utf-8 -*-__author__ = 'Qiushi Huang'import randomfrom cal_time import *import copy # 复制模块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)@cal_timedef quick_sort(li): _quick_sort(li, 0, len(li)-1)@cal_timedef 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，说明没有发生交换，结束代码 returnli = list(range(10000))random.shuffle(li)li1 = copy.deepcopy(li) # 深拷贝li2 = copy.deepcopy(li)quick_sort(li1)bubble_sort(li2)'''quick_sort running time: 0.03162503242492676 secs.bubble_sort running time: 10.773478269577026 secs.'''print(li1) # [0, 1, 2, 3, 4,..., 9997, 9998, 9999]print(li2)

冒泡排序和快速排序效率对比

　　对比运行时间，可以发现针对10000个元素的数组排序，快速排序的效率比冒泡排序高了几百倍。

　　时间复杂度O(nlogn)和O(n²)在数量越大的情况下，效率相差将越来越大。

　　快速排序的最好情况时间复杂度是O(n)，一般情况时间复杂度是O(nlogn)，最坏情况时间复杂度是O(n²)。