浙教版(2019)高中信息技术选修一 数据与数据结构 5.3常用排序算法 知识点总结

1.冒泡排序（要求：熟练掌握）
1)工作原理：每次检查相邻两个元素，如果前后元素不满足升序(降序)就将相邻两个元素交换，当没有相邻元素需要交换时，排序就完成了。经i轮排序扫描，第i大(小)的数会被冒泡到数列的前面或后面
2)稳定性：冒泡排序是一种稳定的排序算法
3)时间复杂度：O(n2)
#1.冒泡排序(升序)
def bubble_sort(a):
for i in range(1,len(a)): #比较轮数=len-1
for j in range(len(a)-i): #当前比较位置
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
return a
a = [7, 8, 0, 1, 6, 3, 9, 4, 5, 2]
print(bubble_sort(a))
初始 :[7, 8, 0, 1, 6, 3, 9, 4, 5, 2]
第1轮:[7, 0, 1, 6, 3, 8, 4, 5, 2, 9]
第2轮:[0, 1, 6, 3, 7, 4, 5, 2, 8, 9]
第3轮:[0, 1, 3, 6, 4, 5, 2, 7, 8, 9]
第4轮:[0, 1, 3, 4, 5, 2, 6, 7, 8, 9]
第5轮:[0, 1, 3, 4, 2, 5, 6, 7, 8, 9]
第6轮:[0, 1, 3, 2, 4, 5, 6, 7, 8, 9]
第7轮:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
第8轮:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
第9轮:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
我们发现最后两轮冒泡时已经有序，可以直接退出循环以提升算法效率
#1.5冒泡排序优化
def bubble_sort(a):
for i in range(1,len(a)): #比较轮数=len-1
flag = True #flag初始状态
for j in range(len(a)-i): #当前比较位置
if a[j]>a[j+1]:
a[j],a[j+1]=a[j+1],a[j]
flag = False #发生交换则标记flag
if flag:break #若一轮都未发生交换则说明已经有序
return a
a = [7, 8, 0, 1, 6, 3, 9, 4, 5, 2]
print(bubble_sort(a))
2.选择排序（要求：熟练掌握）
1)工作原理：每次找出第i小(大)的元素，然后将这个元素和第i个位置元素交换
2)稳定性：一般的认为选择排序是一种不稳定的算法
3)时间复杂度：O(n2)
#2.选择排序(升序)
def selection_sort(a):
for i in range(len(a)-1):
ith = i
for j in range(i+1,len(a)):
if a[ith]>a[j]:
ith = j #找到第i小的值位置
a[ith],a[i]=a[i],a[ith]
return a
a = [6, 7, 5, 8, 2, 1, 4, 0, 3, 9]
print(selection_sort(a))
初始 : [6, 7, 5, 8, 2, 1, 4, 0, 3, 9]
第1轮: [0, 7, 5, 8, 2, 1, 4, 6, 3, 9]
第2轮: [0, 1, 5, 8, 2, 7, 4, 6, 3, 9]
第3轮: [0, 1, 2, 8, 5, 7, 4, 6, 3, 9]
第4轮: [0, 1, 2, 3, 5, 7, 4, 6, 8, 9]
第5轮: [0, 1, 2, 3, 4, 7, 5, 6, 8, 9]
第6轮: [0, 1, 2, 3, 4, 5, 7, 6, 8, 9]
第7轮: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
第8轮: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
第9轮: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
思考：选择排序是否可以提前结束
3.插入排序（要求：熟练掌握）
1)工作原理：将待排元素分为“已排序”和“未排序”两个部分，每次从未排序部分中取出一个元素放到已排序中。
2)稳定性：插入排序是一种稳定的算法
3)时间复杂度：最优O(n)，最差O(n2)
#3.插入排序(升序)
def insertion_sort(a):
for i in range(1,len(a)): #小于i的为有序部分,i~len-1为无序部分
val = a[i] #无序部分取值
pos = i-1
while pos>=0 and a[pos]>val: #在有序部分寻找插入位置
a[pos+1] = a[pos] #逐位后移
pos -= 1
a[pos+1] = val #将值插入有序部分
return a
a = [6, 0, 9, 5, 8, 3, 4, 7, 1, 2]
print(insertion_sort(a))
初始 : [6, 0, 9, 5, 8, 3, 4, 7, 1, 2]
第1轮: [0, 6, 9, 5, 8, 3, 4, 7, 1, 2]
第2轮: [0, 6, 9, 5, 8, 3, 4, 7, 1, 2]
第3轮: [0, 5, 6, 9, 8, 3, 4, 7, 1, 2]
第4轮: [0, 5, 6, 8, 9, 3, 4, 7, 1, 2]
第5轮: [0, 3, 5, 6, 8, 9, 4, 7, 1, 2]
第6轮: [0, 3, 4, 5, 6, 8, 9, 7, 1, 2]
第7轮: [0, 3, 4, 5, 6, 7, 8, 9, 1, 2]
第8轮: [0, 1, 3, 4, 5, 6, 7, 8, 9, 2]
第9轮: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
4.归并排序（要求：理解运行过程）
1)工作原理：归并排序是一种采用“分治思想”的排序方法。归并排序分为三个步骤：1.将数列分成左右两个部分；2.对左右两个部分进行并归排序；3.合并两个子序列。不难看出，并归中含有递归思想。
2)稳定性：并归排序是一种稳定的排序算法
3)时间复杂度：O(n log n)
4)空间复杂度：O(n)
#4.归并排序(升序)
def merge(a,left,mid,right): #两个有序数组合并(含头不含尾)
i = left
j = mid
b = []
while i if a[i] b.append(a[i]);i+=1
else:
b.append(a[j]);j+=1
while i b.append(a[i]);i+=1
while j b.append(a[j]);j+=1
a[left:right]=b #整理后复制回原数组
return a
def merge_sort(a,left,right): #归并(含头不含尾)
if left mid = (left+right)//2
a=merge_sort(a,left,mid) #归并左数列
a=merge_sort(a,mid,right) #归并右数列
a=merge(a,left,mid,right) #左右数列合并
return a
a = [8, 0, 2, 5, 9, 7, 3, 4, 6, 1]
print(merge_sort(a,0,len(a)))
5.快速排序（要求：理解运行过程）
1)工作原理：快速排序和归并排序类似，都采用了分治思想。快速排序也可以分为三个步骤：1.找一个值为基值，然后将小于基值的数放到基值左边，大于基值的数放到基值；2.对基值左右两部分再次进行快速排序；3.左右数列不需要合并已经有序。显然，快速排序也基于递归思想。
2)稳定性：快速排序是一种不稳定的排序算法
3)时间复杂度：最优O(n log n) ，最次O(n2)
#5.快速排序(升序)
def partition(a,low,hight): #分段(左索引,右索引)
pivot_num = a[low] #获取基值
while low while low=pivot_num:
hight-=1
a[low]=a[hight] #比基值大的放在基值左侧
while low low+=1
a[hight]=a[low] #比基值小的放在基值右侧
pivot = low
a[pivot]=pivot_num
return a,pivot #返回更新完的数列和基值位置
def quick_sort(a,low,hight): #快速排序(左索引,右索引)
if low>=hight:
return a
a,pivot = partition(a,low,hight) #将数组分为两个部分
a = quick_sort(a,low,pivot-1) #递归排序左半部分
a = quick_sort(a,pivot+1,hight) #递归排序右半部分
return a
a = [5, 4, 8, 3, 6, 2, 9, 1, 7, 0]
print(quick_sort(a,0,len(a)-1))
6.希尔排序(缩小增量排序)（要求：在掌握插入排序基础上能够自主运用）
1)工作原理：希尔排序是插入排序的一种改进版本，以其发明者希尔命名。希尔排序主要分三步处理排序问题：1.将待排序序列分为若干子序列；2.对子序列中相同位置的数进行插入排序；3.缩小每个子序列元素间的间距，重复过程直至间距缩小为1。
2)稳定性：希尔排序是一种不稳定的排序算法。
3)时间复杂度：希尔排序的时间复杂度和缩小间距的选取有之间关系。
4)空间复杂度：O(n)
#6.希尔排序
def shell_sort(a):
delta = len(a)//2 #间距
while delta>=1:
for i in range(delta,len(a),1):
j=i
while j>=delta and a[j] #两个条件同时满足时,根据步长交换,使后面的较小数快速前移
a[j],a[j-delta]=a[j-delta],a[j]
j-=delta #跳到前一组继续比较
delta //= 2 #调整间距
return a
a = [8, 5, 3, 4, 0, 7, 9, 1, 2, 6]
print(shell_sort(a))
堆排序（要求：了解即可）
1)工作原理：堆排序使用了满二叉树结构（堆结构）尽心排序。首先将一维数列转为一个满二叉树（即父节点的索引i和子节点的索引j，满足j=i*2+1）,然后进行最大（小）堆调整。每次调整后根节点一定是最大（小）值，将根节点输出后堆剩余部分再进行最大（小）堆调整。
2)稳定性：堆排序是一种不稳定的算法
3)时间复杂度：O(n log n)
#7.堆排序
def max_heapify(a,start,end): #最大堆调整
dad = start #父节点
son = dad*2+1 #左子节点
while son <= end: #子节点索引不越界
if son+1<=end and a[son] son+=1 #若右节点更大，则交换节点更新为右节点
if a[dad] a[dad],a[son]=a[son],a[dad]
dad = son
son = dad*2+1
else:
break
return a
def heap_sort(a):
#初始化调整，从最后一个父节点开始
for i in range(len(a)//2-1,-1,-1):
a=max_heapify(a,i,len(a)-1)
#最大堆的根节点一定是最大值，将最后一个节点替换根节点后再次排序
for i in range(len(a)-1,0,-1):
a[0],a[i]=a[i],a[0]
a=max_heapify(a,0,i-1)
return a
a=[5, 1, 9, 6, 8, 7, 2, 0, 3, 4]
print(heap_sort(a))
8.计数排序（要求：理解运行过程）
1)工作原理：计数排序与常规排序不同，它使用一个额外的数组（或字典）去存储各个数据的个数，然后根据数组（或字典）中值的大小顺序重新复原数组。
2)稳定性：计数排序是一种稳定的排序算法
3)时间复杂度：计数排序的时间复杂度O(n)
#8.计数排序
def count_sort(a):
dic = {};b=[]
for i in a:
dic[i]=dic.get(i,0)+1 #注意get()方法的使用
for j in range(min(a),max(a)+1):
if dic.get(j,0)>0:
for k in range(dic[j]):
b.append(j)
#print(dic) #用于输出字典结果，实际中不需要
return b
a = [9, 8, 3, 5, 1, 4, 9, 6, 4, 4]
print(count_sort(a))
#运行结果
{9: 2, 8: 1, 3: 1, 5: 1, 1: 1, 4: 3, 6: 1}
[1, 3, 4, 4, 4, 5, 6, 8, 9, 9]
注意：
get(键,填充值)方法的使用，避免了字典查询为空的问题
min()，max()方法的使用有点取巧，最值应该在第一次循环存字典时顺带统计。
字典是一种无序结构，重新整合数组顺序由j循环控制
9.桶排序（要求：理解运行过程）
1)工作原理：桶排序也并非常规的排序算法，它实际上是一种分治思想的实践。桶排序的过程可以分为4步：1.根据数据的特征将数据分为若干的桶，给每个桶规定可以存储的值的范围；2.将原数列的数据放入各个桶中；3.对每个桶都进行排序；4.按照桶的顺序将桶内数据重新链接。注意区分桶排序，归并排序，快速排序的区别。
2)稳定性：桶排序的稳定性取决与其内层排序的排序算法
3)时间复杂度：O(n2)
#9.桶排序
def bucket_sort(a):
bucket = []
b = []
bucketnum = (max(a)-min(a))//len(a)+1 #根据数据特征确定桶数量
for i in range(bucketnum): #建桶
bucket.append([])
for x in a: #入桶
num = (x-min(a))//len(a)
bucket[num].append(x)
for i in range(bucketnum):
bucket[i].sort() #并非“脱了裤子放屁”，详见“注意”
b.extend(bucket[i]) # 与 b+=bucket[i] 等价
#print(bucket) #输出桶结构
return b
a = [77, 7, 26, 14, 11, 21, 60, 51, 30, 78]
print(bucket_sort(a))
#运行结果
[[7, 11, 14], [21, 26], [30], [], [51], [60], [], [77, 78]] #桶结构
[7, 11, 14, 21, 26, 30, 51, 60, 77, 78]
注意：
桶排序更多适用与数据值域较大但分别较均匀的情况，其本质也只是用于分段，对于桶内数据一般不会再使用桶排序递归，而是采用更高效的排序算法。故示例再桶内排序时也直接使用了sort()方法加以区分和说明。
10.基数排序（要求：理解运行过程）
1)工作原理：基数排序是一种非比较排序算法，最早用与解决卡片排序问题。基数排序的过程：将待排序元素按位拆分，然后先排个位，再排十位，再排百位。。。对最高位排序结束后序列已经有序。
2)稳定性：基数排序是一种稳定的排序算法
3)时间复杂度：O(nk log n)
4)空间复杂度：O(n)
#10.基数排序
def radix_sort(a):
max_len = len(str(max(a)))
for i in range(-1,-max_len-1,-1): #位数循环
b = []
bucket = [[] for i in range(10)] #建桶，0-9共10个数
for j in a:
try:
radix=int(str(j)[i]) #关键字，即个位，十位。。。
except:
radix = 0
bucket[radix].append(j)
#print(bucket)
for k in range(10): #出桶
if len(bucket[k])>0:
b.extend(bucket[k]) #与 b+=bucket[k]等价
a = b
#print(a)
return a
a = [100, 82, 6, 33, 84, 28, 41, 64, 89, 61]
print(radix_sort(a))
#运行结果：
[100, 82, 6, 33, 84, 28, 41, 64, 89, 61]
[[100], [41, 61], [82], [33], [84, 64], [], [6], [], [28], [89]] #第一次，个位入桶
[100, 41, 61, 82, 33, 84, 64, 6, 28, 89] #第一次结果
[[100, 6], [], [28], [33], [41], [], [61, 64], [], [82, 84, 89], []] #第二次 十位入桶
[100, 6, 28, 33, 41, 61, 64, 82, 84, 89] #第二次结果
[[6, 28, 33, 41, 61, 64, 82, 84, 89], [100], [], [], [], [], [], [], [], []] #第三次百位入桶
[6, 28, 33, 41, 61, 64, 82, 84, 89, 100] #第三次结果