22 附录：其他常见排序算法& 附录：ASCII编码表 知识点梳理- 2023届浙教版（2019）高考信息技术专题复习（选修）

附录：基本排序算法补充 1.归并排序（要求：理解运行过程） 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<mid and j<right:         if a[i]<a[j]:             b.append(a[i]);i+=1         else:             b.append(a[j]);j+=1     while i<mid:         b.append(a[i]);i+=1     while j<right:         b.append(a[j]);j+=1     a[left:right]=b          #整理后复制回原数组     return a def merge_sort(a,left,right):  #归并(含头不含尾)     if left<right-1: #子序列长度不为1         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))) 2.快速排序（要求：理解运行过程） 1)工作原理：快速排序和归并排序类似，都采用了分治思想。快速排序也可以分为三个步骤：1.找一个值为基值，然后将小于基值的数放到基值左边，大于基值的数放到基值；2.对基值左右两部分再次进行快速排序；3.左右数列不需要合并已经有序。显然，快速排序也基于递归思想。 2)稳定性：快速排序是一种不稳定的排序算法 3)时间复杂度：最优O(n log n) ，最次O(n2) #5.快速排序(升序) def partition(a,low,hight):    #分段(左索引,右索引)     pivot_num = a[low]   #获取基值     while low<hight:         while low<hight and a[hight]>=pivot_num:             hight-=1         a[low]=a[hight]     #比基值大的放在基值左侧         while low<hight and a[low]<=pivot_num:             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)) 3.希尔排序(缩小增量排序)（要求：在掌握插入排序基础上能够自主运用） 1)工作原理：希尔排序是插入排序的一种改进版本，以其发明者希尔命名。希尔排序主要分三步处理排序问题：1.将待排序序列分为若干子序列；2.对子序列中相同位置的数进行插入排序；3.缩小每个子序列元素间的间距，重复过程直至间距缩小为1。 2)稳定性：希尔排序是一种不稳定的排序算法。 3)时间复杂度：希尔排序的时间复杂