Python数据结构与算法(3)排序
学习目标
什么是排序？
排序定义：将一组“无序”的记录序列调整为“有序”的记录序列。
排序的输入是列表，输出是有序的列表。排序一般有两种方式，升序和降序，python内置的排序函数为sort()。
常见的排序算法介绍
-
第一梯队：冒泡排序、选择排序、插入排序
-
第二梯队：快速排序、堆排序、归并排序
-
第三梯队：希尔排序、计数排序、基数排序……
第一梯队
冒泡排序
定义：列表每两个相邻的数，如果前面的比后面的要大，则交换两个数。一趟排序完成后，则无序区减少一个元素（最大的数排上最大的位置了），有序区增加一个数。
1
2
3
4
5
6
7
8
9
|
def bubble_sort(li):
for i in range(len(li)-1): # 一共n-1趟
for j in range(len(li)-i-1): # 每一趟的趟数为n-i-1
if li[j] > li[j+1]:
li[j],li[j+1] = li[j+1], li[j]
return li
list = [1,5,2,1,4,5,6,7]
print(bubble_sort(list))
|
时间复杂度为：O($n^2$)，上述代码可以改进，在每趟排序中放置一个检测数，若其中一趟没有发生任何交换，则默认为无序列表区域已默认排好，不需要再去遍历排序。
优化过的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
def bubble_sort(li):
for i in range(len(li)-1): # 一共n-1趟
exchange = False # 在每一趟排序之前是默认没发生交换的
for j in range(len(li)-i-1): # 每一趟的趟数为n-i-1
if li[j] > li[j+1]:
li[j],li[j+1] = li[j+1], li[j]
exchange = True # 如果发生交换就重置为交换过
if not exchange:
break
return li
list = [1,5,2,1,4,5]
print(bubble_sort(list))
|
选择排序
定义：从无序区中遍历选择最小的数，将其依次放到一个新列表中，直到无法遍历原数据。
1
2
3
4
5
6
7
|
def select_sort(li):
li_new = []
for i in range(len(li)):
min_val = min(li)
li_new.append(min_val)
li.remove(min_val)
return li_new
|
此代码不是原地排序，而且包含min()、remove()函数，都需要遍历原数据，即一个O($n$)复杂度包含两个O($n$)复杂度，需要原地操作和不要包含其他时间复杂度，则排序思想可以优化为：
思路：将列表遍历，查找到小的数来与无序区第一个数字交换，之后无序区的的数字依次不停发生交换。
1
2
3
4
5
6
7
8
|
def select_sort_plus(li):
for i in range(len(li)-1): # i为第几趟，放到有序区，把最小的数字丢前面总共需要n-1趟，最后一个数字默认为有序区
min_loc = i # 最小值位置默认为无序区最开始的位置
for j in range(i, len(li)): # 从第i趟到最后，最后用列表长度是因为range默认不包含最后一个数
if li[j] < li[min_loc]: # 如果从无序区遍历的数字比默认最小值数字还要小
min_loc = j # 此时最小值位置找到
li[i],li[min_loc] = li[min_loc],li[i] # 最小值与无序区第一个值进行交换，扩大有序区
return li
|
插入排序
定义：将第一个数字作为有序区的第一个数字，从无序区抽一个数字，比较有序区的数字，判断放在有序区数字的左边还是右边，（升序）如果大放在有序区数字的右边，反之放在左边，直到无序区没有数字。
1
2
3
4
5
6
7
8
9
10
|
def inser_sort(li):
for i in range(1,len(li)): # i为要拿的无序区的下标
j = i-1 # j为需要排序区的下标（手里的最后一张牌）
tmp = li[i] # 将要拿的无序区的保存（缓冲区的牌）
while li[j] > tmp and j >=0 : # 要拿的无序区的数字要比需要排序区的数字要小,且j不越界
li[j+1] = li[j] #把数往后移动
j -= 1 # j往前遍历
li[j+1] = tmp #拿到的无序区的数放在前面
print(li)
inser_sort([1,4,6,2,4,1])
|
第一梯队：冒泡排序、选择排序、插入排序的时间复杂度一般均为O($n^2$)。
第二梯队
快速排序
定义：取第一个元素p，使元素p归位；列表被p分为两部分，左边都比p小，右边都比p大；左边和右边都让第一个元素归位……然后也依相同的步骤递归完成排序。代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
def partition(li, left, right):
tmp = li[left] # 将第一个值保存在临时变量
while left < right: # 两个下标重合结束循环
while left < right and li[right] >= tmp: #从右边开始循环，找到比第一个值小的值（右值大于第一个值的排除，右标左移）
right -= 1 # 右边下标后退一格
li[left] = li[right] # 让右值写到左边空位
#找到之后开始再从左边找
while left < right and li[left] <= tmp: # 从左边开始循环，找到比第一个值大的值（左值小于第一个值的排除，左标右移）
left += 1
li[right] = li[left] # 让左值写到右边空位 碰上了自己等于自己
li[left] = tmp # 把tmp写到重合后的（中间）位置
return left # 返回重合下标，left和right都行，此时已经重合
def quick_sort(data,left,right):
if left < right: # 至少两个元素才递归，也就是左归位和右归位都还没排序成功时
mid = partition(data,left,right)
quick_sort(data,left,mid-1) # 左归位
quick_sort(data,mid+1,right) # 右归位
|
快速排序的时间复杂度最好的情况一般为O($nlogn$)，每层递归有n的规模，一共$logn$层，即时间复杂度为O($nlogn$)，考虑到有最坏的情况，即每次只少一个数（不是每次都少一半），即时间复杂度为O($n^2$)， 一般最坏情况出现的概率比较少。
堆排序
-
前置知识：树，树是一种数据结构，比如目录结构就是一种树，树可以定义递归，树是由n个节点组成的集合，如果n=0，那么它是一个空树；如果n>0，那么存在一个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一颗树。根节点：一个树的根；叶子节点：叶子节点指的是不能分集合的节点，树的末梢；树的深度（高度）：从根节点到叶子节点一共最大的层数；节点的度：对于一个节点能分多少节点（分多少叉），节点中有度最大的节点，树的度即是树中节点最大的度；孩子节点/父节点是只两个节点的关系，a有b节点生成，即b为a的父节点，a为b的孩子节点。子树：由一个子节点包括子节点生成的所有节点为一个子树。
-
完全二叉树：叶子节点只能出现在下层或者次下层，且最下层的叶子节点集中在树的左边，满二叉树肯定是完全二叉树，但完全二叉树不一定是满二叉树。
-
堆：是一种特殊的完全二叉树：分为大根堆和小根堆。
- 大根堆：一颗完全二叉树，满足任一节点都比其孩子节点大。
- 小根堆：一颗完全二叉树，满足任一节点都比其孩子节点小。
- 堆有向下调整的机制，即在根节点左右子树都是堆，根节点却不满足堆的性质的情况下可以通过一次向下的调整来将其变成一个堆。
-
堆排序的过程：
- 首先建立一个堆（构造堆）：先从最后一个父节点开始调整，每次小的调整，最后调整大的；
- 然后得到堆顶元素（放到有序区），为最大元素，去掉堆顶，将一个最后的元素放到堆顶，通过每次的向下调整性质使得堆有序（即堆顶维持最大值），再通过交换让所有的序列变成从上至下升序排列。（即堆顶最大值与最后一个叶子节点进行交换，且固定大的值为叶子节点）。
- 最后重复以上操作，知道，直到堆变空。
代码如下：
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
|
def sift(li, low, high): # 函数用来堆排序向下调整
"""
堆排序的调整函数（对于整个堆）
:param li: 列表
:param low: 堆的根节点位置
:param high: 堆的最后一个元素的位置
:return:
"""
i = low # 开始位置为：根节点位置（堆顶）
j = 2 * i + 1 # 找其孩子节点位置
tmp = li[low] # 把堆顶拿出来
while j <= high: # 只要j位置有值
if j+1 <= high and li[j+1] > li[j]: # 如果右孩子节点有值 且值比左孩子大
j = j+1 # 那么j就指向右孩子
if li[j] > tmp: # 如果孩子节点值大于拿出来的堆顶值
li[i] = li[j] # 那么孩子节点值往堆顶移动
i = j # i往下移动一层
j = 2 * i + 1 #j也变为新的孩子节点
else: # 拿出来的堆顶值比孩子节点大
break # 确保堆顶为最大值后退出循环
li[i] = tmp # 拿出来的堆顶值还是放在堆顶，防止越界
def heap_sort(li):
# 第一步建堆：从最后一个父节点进行调整，每次小调整，之后大数调整
# 由孩子节点i找父节点的公式为(i-1)//2
# 此时最后一个孩子节点为n(数组长度）-1，所以从最后一个孩子节点找父节点是（n-2）//2
n = len(li) # 获取列表长度
for i in range((n-2)//2,-1,-1): # 倒序排序，从最后一个到第一个，前包后不包则第二个数为-1
# i 表示建堆时调整时的根节点
sift(li,i,n-1)
# 第一步建堆完成，第二三步下来数和上去数做每次的交换与调整
for i in range(n-1,-1,-1): # i 指向当前堆的最后一个元素,循环从最后一个节点向前遍历
li[0],li[i] = li[i],li[0] # 因为堆顶已经最大，所以先交换
sift(li,0,i-1) # i-1 指的是每次交换后i要往前移动一个，为新的high
li = [11,2,3,45,1,22,66,23,89]
heap_sort(li)
print(li)
|
由于sift函数的时间复杂度为遍历数的深度，即整个问题的规模被二分，即时间复杂度为O($logn$)，调用时的heap_sort函数用到了循环，即复杂度为O($n$)，故堆排序的时间复杂度为O($nlogn$)。
一般情况下快速排序可能比堆排序时间复杂度高一点。python内部有heapq模块来帮助直接实现堆排序，使用代码如下：
1
2
3
4
5
6
7
8
9
10
|
import heapq # q = queue队列，优先队列
import random
li = list(range(10))
random.shuffle(li)
new_li = []
heapq.heapify(li) # 建小根堆
for i in range(len(li)):
j = heapq.heappop(li) # 每次弹出小根堆中最小的数字
new_li.append(j)
print(new_li)
|
topk问题
问题描述：现在有n个数，设计算法得到前k大的数。（k<n)
思路：
- 排序后切片，时间复杂度为排序的复杂度O($nlogn$)
- 冒泡排序只用取前k躺，时间复杂度为O($n * k$) 两者看k大还是$logn$大
- 堆排序解决，时间复杂度O($nlogk$)，调整根据k的数量来变化，
堆排序解决topk问题：取列表前k个元素建立一个小根堆，堆顶就是目前第k大的数，依次向后遍历列表，对于列表中的元素，如果小于堆顶，则忽略该元素，如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整。遍历所有元素后，倒序弹出堆顶。
代码实现如下：
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
|
def sift(li, low, high): # 函数用来堆排序向下调整
"""
堆排序的调整函数（对于整个小根堆）
:param li: 列表
:param low: 堆的根节点位置
:param high: 堆的最后一个元素的位置
:return:
"""
i = low # 开始位置为：根节点位置（堆顶）
j = 2 * i + 1 # 找其孩子节点位置
tmp = li[low] # 把堆顶拿出来
while j <= high: # 只要j位置有值
if j+1 <= high and li[j+1] < li[j]: # 如果右孩子节点有值 且值比左孩子大
j = j+1 # 那么j就指向右孩子
if li[j] < tmp: # 如果孩子节点值大于拿出来的堆顶值
li[i] = li[j] # 那么孩子节点值往堆顶移动
i = j # i往下移动一层
j = 2 * i + 1 #j也变为新的孩子节点
else: # 拿出来的堆顶值比孩子节点大
break # 确保堆顶为最大值后退出循环
li[i] = tmp # 拿出来的堆顶值还是放在堆顶，防止越界
def topk(li,k):
heap = li[0:k] # 取前k个元素
for i in range((k-2)//2,-1,-1): # 开始建堆
sift(heap,i,k-1)
for i in range(k, len(li)): # 以堆外的元素个数进行换顶调整操作
if li[i] > heap[0]:
heap[0] = li[i] # 换顶操作
sift(heap,0,k-1) # 调整保持根节点最大
for i in range(k-1,-1,-1): # 从小到大开始遍历出数
heap[0],heap[i] = heap[0], heap[i] # 交换
sift(heap,0,i-1) # 调整
return heap
li = [123,4324,11,123,45,1,0,12]
print(topk(li,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
38
39
|
def merge(li, low, mid, high):
"""
归并排序的归并过程
:param li: 操作的列表
:param low: 列表开始的位置
:param mid: 列表中间的位置
:param high: 整个列表的最后一个元素位置
:return:
"""
i = low # 先保存一下开始的位置
j = mid + 1 # 保存一下第二段有序列的开头位置
ltmp = [] # 临时列表
while i <= mid and j<=high: # 只要两边都有数
if li[i] < li[j]:
ltmp.append(li[i])
i += 1 # i箭头往后移
else:
ltmp.append(li[j])
j += 1 # j箭头往后移
# 以上是序列数量相同的部分操作
while i <= mid: # 如果完成后左边还剩数字则全部添加
ltmp.append(li[i])
i += 1
while j <= high: # 如果完成后右边还有数字则全部添加
ltmp.append(li[j])
j += 1
li[low:high+1] = ltmp
def merge_sort(li,low,high):
if low < high: # 至少有两个元素则满足递归
mid = (low + high)//2
merge_sort(li,low, mid) # 递归左边先分解，再执行排序merge
merge_sort(li,mid+1,high) # 递归右边先分解，再执行排序merge
merge(li,low,mid,high) # 归并过程
li = [1,2,32,3,22,11,44,23,9]
merge_sort(li,0,len(li)-1)
print(li)
|
递归的过程时间复杂度为O($logn$)，因为有$logn$层次的归并，一次归并的时间复杂度为O($n$)，因此归并排序的时间复杂度为O($nlogn$)。由于每次归并都需要开辟新的列表，所以空间复杂度为O($n$)，不为原地排序。python里内置的sort方法使用的是归并排序和插入排序的优化。
第二梯队：快速排序、归并排序、堆排序的时间复杂度一般为O($nlogn$)。一般情况下时间复杂度快速排序<归并排序<堆排序，三种排序各有优劣，快速排序在遇到极端情况下排序效率会降低，归并排序需要额外的内存开销，堆排序在快的排序算法中相对较慢。
| 排序方法 |
时间复杂度(最坏，一般，最好) |
空间复杂度 |
稳定性 |
代码复杂度 |
| 冒泡排序 |
O($n^2$),O($n^2$),O(n) |
O($1$) |
稳定 |
简单 |
| 选择排序 |
O($n^2$),O($n^2$),O($n^2$) |
O($1$) |
不稳定 |
简单 |
| 插入排序 |
O($n^2$),O($n^2$),O($n^2$) |
O($1$) |
稳定 |
简单 |
| 快速排序 |
O($n^2$),O($nlogn$),O($nlogn$) |
平均情况O($logn$)，最坏情况O($n$) |
不稳定 |
较复杂 |
| 堆排序 |
O($nlogn$),O($nlogn$),O($nlogn$) |
O($1$) |
不稳定 |
复杂 |
| 归并排序 |
O($nlogn$),O($nlogn$),O($nlogn$) |
O($n$) |
稳定 |
较复杂 |
稳定性：当两个值相对位置没有变化时，例如：两个相同的数在不同位置上排序后的顺序是否改变，如果改变即可能为不稳定，有顺序的挨个移动位置的是一般稳定的，跳着换一般是不稳定的。
第三梯队
希尔排序
定义：是一种分组插入排序算法。首先取一个整数$d_1$ = $n//2$，将元素分为$d_1$个组，每组相邻两个元素之间的距离为$d_1$ ，在各组内进行直接插入排序；取第二个整数$d_2$ =$d_1 //2 $，重复上述分组排序过程直到$d_1 = 1$，希尔排序每趟并不使得某些元素有序，而是使得整体数据越来越接近有序，最后一趟排序使得所有数据有序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
def inser_sort_gap(li,gap):
"""
由插入排序改的希尔排序
:param li: 输入列表
:param gap: 间隔d
"""
for i in range(gap,len(li)): # i 为要拿的无序区下标,从gap开始
tmp = li[i] # 将抽出的数保存进缓冲区
j = i-gap # j为有序区遍历的下标，现在相隔gap的区域前的数为有序区的数
while li[j] > tmp and j >=0 : # j在遍历范围内，且有序区中的数大于缓冲区得数
li[j+gap] = li[j] # 数字往前移动，大数往后让位
j -= gap # 遍历下标也向前移动
li[j+gap] = tmp
def shell_sort(li):
d = len(li) // 2 # 取第一个整数
while d >= 1: # 循环直到d为1
inser_sort_gap(li,d)
d //= 2 # 每次折半
import random
li = list(range(1,17))
random.shuffle(li)
shell_sort(li)
print(li)
|
希尔排序的时间复杂度比较复杂，并且和选取的gap序列有关。故暂不讨论。
计数排序
定义：新建一个从0开始到待排序最大数值的空序列，序列上全元素全归位为初始值0；如果待排序序列的值在空序列上有位置，则该位置的初始值加一计数，如此往复直到待排序序列完全记数在空序列中，再依次根据次数来排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
def count_sort(li, max_count=100): # 待排序列表中最大的数为100
count = [0 for _ in range(max_count+1)] # 下划线表示无论我遍历多少次，我不关心当前值是多少，一律为0，长度即为100(左闭右开)
for val in li: #遍历列表依次获取值
count[val] += 1 # 计数下标为值的0列表计数加一
li.clear() # 清空原列表
for ind, val in enumerate(count): # 获取在count列表迭代器中返回的索引（值）和个数
for i in range(val):
li.append(ind) # 有多少计数次就写多少次值
import random
li = list(range(99))
random.shuffle(li)
count_sort(li)
print(li)
|
计数排序的时间复杂度为O($n$)，因为计数排序中的操作数规模是根据原列表的个数来决定的，因此规模为n。计数排序虽然很快但是要提供数据的最大范围。
桶排序
定义：将计数排序中无法确定的最大范围分为几个不同的小范围（桶），再对每个桶中的元素进行排序，保持每个桶内有序，最后将所有桶依次按顺序输出，初步代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
def bucket_sort(li,n=100,max_num=10000): # n为多少个桶，max_num为最大数范围
buckets = [[] for i in range(n)] # 所有的桶即为二维列表,创建了n个桶的每个桶为一个列表。
for var in li:
i = min(var // (max_num // n), n-1) # i是放到几号桶，如果数字是10000 因为没有100号桶只有99号桶，因此取小
buckets[i].append(var) # 根据元素放入到相应的桶内
#保持每个单桶的升序
for j in range(len(buckets[i])-1,0,-1): # 对每个桶放进去的过程中进行反方向冒泡排序
if buckets[i][j] < buckets[i][j-1]: # 如果后面的数比前面的数小，则后面的数与前面的数交换
buckets[i][j],buckets[i][j-1] = buckets[i][j-1],buckets[i][j] # 两两交换
else:
break # 如果前面的元素比后面的元素小则退出循环
sorted_li = []
for buc in buckets:
sorted_li.extend(buc) # 把桶中的列表元素作为当个元素追加到空列表
return sorted_li
import random
li = list(range(100))
random.shuffle(li)
print(bucket_sort(li))
|
桶排序的表现基于数据的分布，数据的分布就是平均分布在每个数段时桶排序效率较高，如果分布在前一个范围数据量小，后一个范围数据量极大则效率不会高。也就是需要对不同的数据排序时采取不同的分桶策略，平均情况时间复杂度为O($n+k$)，最坏情况下时间复杂度为O($n^2k$)，空间复杂度为O($nk$)，因为占用了一个桶的空间。
基数排序
如果要求员工表先按照薪资排序，在按照年龄排序，根据两个关键字进行稳定排序的叫做多关键字排序。比如在一组两位数数据中，我们可以先比较个位，装个位顺序的桶，再比较个位，装十位顺序的桶，依次循环往复。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
def radix_sort(li):
"""
基数排序算法
:param li:列表
:return:
"""
max_num = max(li) # 最大值为99 那么做两次循环，如果最大值为999，做三次循环
it = 0 # 循环计数器
while 10 ** it <= max_num: # 以10的倍数为基准确定位数，确定循环次数
buckets = [[] for _ in range(10)] # 每一位分十个桶
for var in li: #对每一个数分桶，先看个位再看十位
digit = (var//(10**it))%10 #取位
buckets[digit].append(var) # 分桶
li.clear() # 原桶清空
for buc in buckets:
li.extend(buc) # 把数据写回桶
it += 1
li = [1,21,44,22,90,8,10]
radix_sort(li)
print(li)
|
基数排序的时间复杂度为：O($kn$)，k为最大数的位数，空间复杂度为O($K+n$)，它是线性排序的一种，与快速排序O($nlogn$)相比，在最大数比较的大的平均分布序列排序中更占优势，如果遇到不均衡的分布则需另外考虑，且基数排序和桶排序都需要额外空间。
总结