1. 前言
排序算法是计算机科学中最基本的算法之一，其作用在于将一组无序数据按照某个规则进行排序，以便于后续的处理和分析。排序算法在实际应用中非常常见，比如搜索引擎、数据库、图像处理、音视频处理、金融数据分析等领域都需要进行排序操作。
排序算法的性能直接影响到程序的执行效率和用户的体验，因此研究和优化排序算法是计算机科学中的一个重要研究领域。不同的排序算法有不同的时间复杂度和空间复杂度，选择合适的排序算法可以大大提高程序的效率。
此外，排序算法也是计算机科学中训练编程能力和算法设计能力的基石，通过研究和实现排序算法可以帮助开发者提高编程技能和挖掘算法的内在特点。
排序算法稳定性： 在满足排序规则的前提下，大小相等的元素保持原有顺序即具备稳定性，不保持原有顺序即不具稳定性。
比如数组[a1, a2, a3]中a1＞a2=a3，由小到大排序完如果是[a2, a3, a1]即为具备稳定性，如果可能出现[a3, a2, a1]即为不具备稳定性。
2.各种排序算法及源代码
各种算法的时间复杂度及稳定性如下图：
2.1冒泡排序
冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。重复地进行这个过程直到整个数列都是有序的。
具备稳定性，最坏时间复杂度=O(n^2)
源代码
def bubble_list(list): for i in range(len(list)): for k in range(len(list)-1-i): if list[k] > list[k+1]: list[k],list[k+1] = list[k+1],list[k] print(list,end="\n\n") #看下每个泡泡的上升情况 return list print(bubble_list([232,1,54,3463,22,121232,-8,99]))
2.2选择排序
选择排序是一种简单直观的排序算法，其基本思想是每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
不具备稳定性
源代码
def select (list): select_list =[] for j in range(len(list)): min = list[j] #如果min用作下标，不用重新构建一个select_list素组，这样可以少一次迭代 for i in range(j+1,len(list)): if list[i] < min: min,list[i] = list[i],min select_list.append(min) print(select_list) #还是看看过程 return select_list select([-101,232,1,22,54,3463,22,121232,-8,99])
2.3插入排序
插入排序是一种简单直观的排序算法，其基本思想是将待排序的元素插入到已经排好序的序列中，从而得到一个新的、个数加一的有序序列。具体来说，插入排序的过程如下：
- 将第一个元素看作已经排好序的序列。
- 依次将后面的元素插入到已经排好序的序列中，直到所有元素都插入完毕。
- 在插入一个元素时，从已经排好序的序列的末尾开始比较，如果该元素比已经排好序的序列中的某个元素小，则将该元素插入到该元素的后面，否则将该元素插入到已经排好序的序列的末尾。
重复步骤2和步骤3，直到所有元素都插入完毕。
源代码包含在下面希尔排序中
具备稳定性，最坏时间复杂度=O(n^2)
2.4希尔排序
希尔排序是一种排序算法，可以说是插入排序的一种变种。它通过分组的方式，直接让前端跟末端的元素进行比较，解决了插入排序的低效问题。
在希尔排序中一个数组在进行了n-排序之后，再进行更细化的k-排序，这个数组仍然是满足n-排序的，所以这个数组是越来越有序。当一开始增量n很大的时候，每一个子数组的元素很少，所以对每个子数组用插入排序进行内部排序是很高效的；而后随着增量n不断减小，这个数组是越来越有序的，此时使用插入排序也是很有利的。
因此，希尔排序会比插入排序更快，而且数组的大小越大，提升越明显。
不具备稳定性，最坏时间复杂度=O(n^2)。它的好处就是平均时间复杂度较小（它的最好情况甚至也不如插入排序）
源代码
def insert(list): for i in range(len(list)-1): for j in range(i,-1,-1): if list[j+1] < list[j]: list[j+1],list[j] = list[j],list[j+1] else: break print(list) #仍然看过程 return list def shell(list): #在插入排序基础上建立希尔排序 gap = len(list) while gap//2 != 1 : gap = gap//2 gap_list = [list[k] for k in range(0,len(list),gap) ] #构建基于每个gap的小列表 insert(gap_list) return list print(insert([-101, 232, 1, 22, 54, 3463, 22, 121232, -8, 99,-1234])) print(shell([-101, 232, 1, 22, 54, 3463, 22, 121232, -8, 99,344543,-2123,12]))
2.5快速排序
基本思路：使用两个游标（low和high），从列表的两端进行逼近（或者叫遍历）。从列表第一个元素开始查找正确位置，游标low（high）遇到比当前要确认位置的元素小（大）的元素，则继续遍历，否则停止，并交换low和high两个游标所指元素。这个过程一直进行，进行到low和high指向的元素一样的时候，则这个位置就是当前要确认位置的元素的正确位置，原有列表也被这个元素分割成两个列表，后面再按这个思路一直进行下去。
思路改进：先用high（或者low）进行遍历，遇到小于待确认位置元素的元素的时候，把这个元素赋值给low，然后low游标开始遍历，直到找到比待确认位置元素大的元素，把这个值赋值给high，循此往复
不具备稳定性，最好时间复杂度O(n*log n) (log以2为底)，最坏时间复杂度O(n^2)
难点：理解函数嵌套的递归思路；注意列表中下标+1，-1的情况
源代码
def fast(list, first, last): #为了后面递归能继续操作list中的元素，引入first和last if first-1 == last: #这个判断只能写在前面，因为后面的嵌套内部要用, 思考：这里为什么first要-1？当分割到列表仅剩一个元素的时候，low= first , last = low-1,所以last比low还小1 return list mid_value = list[first] #mid_value就是待确认位置的元素, high与low游标都和它进行对比 low = first high = last while high > low: while list[high] >= mid_value: high -= 1 if high == low: #防止中间有过多一样的元素，导致high一直减少，导致high与low游标错过 break list[low] = list[high] #刚开始的时候list[low]=mid_value=list[0]，所以第一个list[low]的值不会丢 while list[low] < mid_value: #这里和上面while list[high] >= mid_value只有一个地方能加=，否则有可能在上面break后下面再操作一遍（这里比较抽象） low += 1 if high == low: #防止中间有过多一样的元素，导致low一直增多，导致high与low游标错过 break list[high] = list[low] list[low] = mid_value print(list,end="\n\n") #仍然要看过程 fast(list,first,low-1) # print("---------------------------------------") fast(list,low+1,last) li = [-8,1,23,5,5,43,-9,100,4,6,7,2,4,-100] li2 = [121,434,23,2,0,3,0,444,0] fast(li, 0, len(li) - 1) fast(li2,0,len(li2)-1) print(li) print(li2)
输出（注意看过程）
"C:\Users\Lenovo\Desktop\Python coding\venv\Scripts\python.exe" "C:/Users/Lenovo/Desktop/Python coding/05_fast.py" [-100, -9, -8, 5, 5, 43, 23, 100, 4, 6, 7, 2, 4, 1] [-100, -9, -8, 5, 5, 43, 23, 100, 4, 6, 7, 2, 4, 1] [-100, -9, -8, 5, 5, 43, 23, 100, 4, 6, 7, 2, 4, 1] [-100, -9, -8, 1, 4, 2, 4, 5, 100, 6, 7, 23, 43, 5] [-100, -9, -8, 1, 4, 2, 4, 5, 100, 6, 7, 23, 43, 5] [-100, -9, -8, 1, 2, 4, 4, 5, 100, 6, 7, 23, 43, 5] [-100, -9, -8, 1, 2, 4, 4, 5, 100, 6, 7, 23, 43, 5] [-100, -9, -8, 1, 2, 4, 4, 5, 100, 6, 7, 23, 43, 5] [-100, -9, -8, 1, 2, 4, 4, 5, 5, 6, 7, 23, 43, 100] [-100, -9, -8, 1, 2, 4, 4, 5, 5, 6, 7, 23, 43, 100] [-100, -9, -8, 1, 2, 4, 4, 5, 5, 6, 7, 23, 43, 100] [-100, -9, -8, 1, 2, 4, 4, 5, 5, 6, 7, 23, 43, 100] [-100, -9, -8, 1, 2, 4, 4, 5, 5, 6, 7, 23, 43, 100] [-100, -9, -8, 1, 2, 4, 4, 5, 5, 6, 7, 23, 43, 100] [0, 0, 23, 2, 0, 3, 121, 444, 434] [0, 0, 23, 2, 0, 3, 121, 444, 434] [0, 0, 23, 2, 0, 3, 121, 444, 434] [0, 0, 3, 2, 0, 23, 121, 444, 434] [0, 0, 0, 2, 3, 23, 121, 444, 434] [0, 0, 0, 2, 3, 23, 121, 444, 434] [0, 0, 0, 2, 3, 23, 121, 444, 434] [0, 0, 0, 2, 3, 23, 121, 434, 444] [0, 0, 0, 2, 3, 23, 121, 434, 444] [-100, -9, -8, 1, 2, 4, 4, 5, 5, 6, 7, 23, 43, 100] [0, 0, 0, 2, 3, 23, 121, 434, 444] Process finished with exit code 0
2.6归并排序
归并排序是一种基于分治思想的排序算法，它将待排序的序列分成若干个子序列，每个子序列都是有序的，然后再将这些有序的子序列合并成一个有序的序列。具体来说，归并排序的过程可以分为两个步骤：分解和合并。
- 分解：将待排序的序列分成若干个子序列，每个子序列包含相邻的元素，然后对每个子序列进行排序。
- 合并：将排序后的子序列合并成一个有序的序列。
在这个排序中，嵌套的理解仍是难点
最有时间复杂度和最坏时间复杂度都是O(n*log n),具备稳定性
源代码
def merge(list): if len(list) == 1: return list mid = len(list) //2 left_list = merge(list[:mid]) #难点：理解这个嵌套 right_list = merge(list[mid:]) left_point = 0 right_point = 0 result_list = [] print(left_list)#这里仍然用于看过程 print(right_list) print(result_list,end="\n\n") while left_point < mid and right_point < mid: if left_list[left_point] <= right_list[right_point]: result_list.append(left_list[left_point]) left_point +=1 else: result_list.append(right_list[right_point]) right_point +=1 result_list= result_list +left_list[left_point:] #把剩余元素补上，注意，这里不能用append result_list= result_list +right_list[right_point:] return result_list li = [12,53,1] merge(li)
2.7二分法查找
只能作用于排序后的顺序表
最坏时间复杂度O(log n)
难点仍在于对嵌套递归的理解
源代码
def binary_search(in_list, target): #in_list是有序列表 n = len(in_list) if n == 0: return "Nogo" # print(n,end="****") else: n = n // 2 print(n) if target == in_list[n]: return "bingo" else: if target > in_list[n]: in_list = in_list[n+1:] print(in_list, end= "\n") return binary_search(in_list, target) #层层return最终结果 else: in_list = in_list[:n] print(in_list,end= "\n") return binary_search(in_list, target) print(binary_search([5,6,7,66,77,88,99,100,1000,10000],5))
