算法-排序算法精炼 Mar 24, 2021 · 算法 · 分享到: 排序算法精炼 TIPS 本文讨论的都是升序排序（从小到大）。冒泡，选择，插入是基础算法。 稳定排序：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。 不稳定排序：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。 冒泡算法 分类：比较排序大类，交换排序 核心思想：两层循环（显然复杂度$n^2$），内循环的作用是让最大值“浮”到末尾，每次内循环浮动一个值。“浮”这个过程就是通过比较相邻元素然后交换。 细节：内循环可以用一个是否存在交换的swapFlag来优化，查看是否提前完成。还有就是内循环的中止项需要考虑。 性能：时间复杂度$O(n^2)$，空间复杂度$O(1)$；稳定排序。 1def bubble(l:list)->list: 2 index_1 = 0 3 while index_1 < len(l): 4 index_2 = 0 5 swapFlag = 0 6 while index_2 < len(l)-index_1-1: # 将index_2作为最大值转移到最后,由于后面有index_2+1，所以这里只需要到len(l)-index_1-1 7 if l[index_2]>l[index_2+1]: 8 swapFlag = 1 9 l[index_2],l[index_2+1]=l[index_2+1],l[index_2] 10 index_2+=1 11 if swapFlag == 0: 12 return l 13 index_1+=1 14 return l 选择排序 分类：比较排序大类，选择排序 核心思想：最简单直观，两层循环$O(n^2)$。内循环遍历未排序数组找到最大小，与未排序的第一位元素交换。每次内循环搞定一个值。 性能：时间复杂度$O(n^2)$，空间复杂度$O(1)$；不稳定排序。表现最稳定的排序算法之一，因为无论什么数据进去都是$O(n^2)$的时间复杂度 1def sel(l:list)->list: 2 index1 = 0 3 while index1 < len(l)-1:# 最后一个必然排好，不需要 4 minEle = l[index1] 5 minIndex = index1 6 index2 = index1 + 1 7 while index2 < len(l): 8 if l[index2]<minEle: 9 minEle = l[index2] 10 minIndex = index2 11 index2+=1 12 l[index1],l[minIndex]=l[minIndex],l[index1] 13 index1+= 1 14 return l 插入排序 分类：比较排序大类，插入排序 核心思想：两层循环$O(n^2)$。内循环从未排序的数组中随便哪一个，然后根据大小插入到已排序数组中。插入排序都采用in-place在数组上实现，不用额外内存，保证空间复杂度为$O(1)$ 细节：注意在while内循环终止时temp大于l[index2]，因此应该是l[index2+1] = temp 性能：时间复杂度$O(n^2)$，空间复杂度$O(1)$；稳定排序。 1def insert(l:list)->list: 2 index1 = 0 3 while index1<len(l)-1: 4 temp = l[index1 + 1] 5 index2 = index1 6 while index2 >= 0 and temp < l[index2]: 7 l[index2+1] = l[index2] 8 index2 -= 1 9 l[index2+1] = temp # 注意在while内循环中temp大于l[index2] 10 index1 += 1 11 return l 以上是三种基本算法 希尔排序（Shell Sort） 1959年Shell发明，第一个突破O(n2)的排序算法。 分类：比较排序大类，插入排序。 核心思想：简单插入排序的改进版。它与插入排序的不同之处在于，先按照间隔对子序列排序，逐渐缩小间隔直至1，完成最终排序。 性能：最坏情况为$O(n^2)$，平均情况好于最坏情况，空间复杂度为$O(1)$，不稳定排序。 用的少，略。 归并排序 分类：归并排序大类 核心思想：分治(Divide and Conquer)，递归。分成子序列至单个元素再合并。和选择排序一样，归并排序的性能不受输入数据的影响，但时间表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度，代价是额外的空间。 细节：关键是理解递归。 性能：时间复杂度$O(n\log n)$，空间复杂度$O(n)$，稳定排序 1def sortRecursion(l:list)->list: 2 if len(l)<=1: 3 return l 4 mid = int((0+(len(l)-1)/2)) 5 l1 = sortRecursion(l[:mid+1]) 6 l2 = sortRecursion(l[mid+1:]) 7 return merge(l1,l2) 8 9def merge(l1:list,l2:list)->list: 10 index1 = 0 11 index2 = 0 12 l3=list() 13 while index1<len(l1) and index2 < len(l2): 14 if l1[index1] <= l2[index2]: 15 l3.append(l1[index1]) 16 index1+=1 17 else: 18 l3.append(l2[index2]) 19 index2+=1 20 if index1 < len(l1): 21 l3.extend(l1[index1:]) 22 if index2 < len(l2): 23 l3.extend(l2[index2:]) 24 return l3 快速排序 分类：比较排序大类，交换排序。 核心思想：快速排序首先选择一个中枢变量（一般选第一个元素），将比中枢变量小的放到左边，大的放到右边，形成分区。再将左右分区依照选中枢变量-->分区的方式递归分区，直到只有一个元素，那么整个数组就排序完成了。我觉得是分治和冒泡排序的结合。 细节：算法实现时，都用的是in-place操作，其实另开空间更能体现算法思想。in-place将第一个元素后的空间作为存放左边分区的空间，最后再将第一位的pivot元素与左边分区的最后一个元素交换，实现最终分区。 性能：平均来说，快速排序的平均复杂度为$O(c_q n\log n)$，最坏情况为$c_q O(n^2)$。但是需要指出这个常用系数$c_q$在几种排序算法中较小，因此在不太大的数组排序中，快排优势与归并和堆排序。空间复杂度取决于递归的次数最好为$O(\log n)$，最坏为$O(n)$，此外快排也是不稳定排序。 1def quickSort(l:list,start:int,end:int)->list: 2 if start < end: 3 pivot = l[start] 4 p_current = start # 选择第一个元素为pivot变量 5 for key in range(start+1,end+1): # 分区 6 if l[key] < pivot: # pivot元素在第一个，把小于pivot的元素从第二位开始逐个往后放 7 p_current+= 1 8 l[p_current],l[key]=l[key],l[p_current] 9 l[p_current],l[start] = l[start],l[p_current]# 把pivot与小于pivot的最后一个元素交换，让pivot元素成为分界线 10 quickSort(l,start,p_current-1) 11 quickSort(l,p_current+1,end) 12 return l 堆排序 分类：比较排序大类，选择排序小类，没想到把堆排序和选择排序是亲戚。 TIPS：堆是一种完全二叉树。大顶堆就是每个父节点都比其子节点大，小顶堆就是每个父节点都比子节点小。 核心思想：用给定数组建立大顶堆，我们每次都选择大顶堆的树根节点（顶部节点），相当于选择排序中选取最大点。然后将其于未排序的最后节点交换，排在最后的就是有序区域。由于交换后可能破坏了堆的结构，因此堆无序区域进行调整。因此得到最大元素，直至完成排序。 细节：每次调整堆的过程叫做“Heapify”，是一个递归调整的过程。在第一次建立堆时，从最后一个非叶子节点从后往前以此调整。 性能：每次调整堆的最好、平均、最坏复杂度都是$O(\log n)$，一共需要调整$n$次，所以总体复杂度为$O(n\log n)$，其性能稳定性继承了选择排序的风格，空间复杂度为$O(1)$，这个排序和选择排序一样也是不稳定的。 1""" 2堆中父子节点关系 3parentIndex = int((childIndex-1)/2) 4leftChildIndex = 2 * parentIndex + 1 5rightChildIndex = 2 * parentIndex + 2 6""" 7def heapify(l:list, n:int): # 修改顶部元素后重新堆化 8 if n >= len(l): 9 return l 10 maxIndex = n 11 leftChildIndex = 2 *n + 1 if 2*n+1 < len(l) else None 12 if leftChildIndex != None and l[leftChildIndex]>l[maxIndex]: 13 maxIndex = leftChildIndex 14 rightChildIndex = 2 *n + 2 if 2*n+2 < len(l) else None 15 if rightChildIndex != None and l[rightChildIndex] > l[maxIndex]: 16 maxIndex = rightChildIndex 17 if maxIndex != n: 18 l[n],l[maxIndex] = l[maxIndex],l[n] 19 heapify(l,maxIndex) 20 return l 21 22def build_heap(l:list)->list: # 将任一数列变成大顶堆 23 if len(l) <= 1: 24 return l 25 lastNodeIndex = len(l) - 1 26 lastNodeParentIndex = int((lastNodeIndex-1)/2) # 从最后一个非叶子节点，往前依次heapify 27 for i in range(lastNodeParentIndex,-1,-1): 28 heapify(l,i) 29 return l 30 31def heapSort(l:list)->list: 32 l = build_heap(l) 33 for i in range(0,len(l)): 34 l[0],l[-1-i] = l[-i-1],l[0] # 顶元素与最后一个未排序元素交换 35 l[:-1-i] = heapify(l[:-1-i],0) 36 return l 以上都是通过比较来排序，还有一些非比较的排序方法，有以下三类 计数排序 分类：非比较排序。 核心思想：其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 细节：计数排序要求输入的数据必须是有确定范围的整数。从新数组取元素应从后往前取，保证稳定性。 优化思路：由于元素最小值可能远大于0，所以可以通过 所有元素-MIN的方式来做偏置，降低所要开辟的空间。 性能：时间复杂度$O(n+k)$（未优化），其中$k$是元素最大值。空间复杂度也是$O(n+k)$，稳定排序 1def countingSort(l): 2 if len(l) < 1: # 避免max函数出错 3 return l 4 maxNum = max(l) 5 newArr = [0]*(maxNum+1) 6 for i in l: 7 newArr[i]+=1 # 将l中的元素作为newArr中的序号 8 sortedIndex = len(l)-1 9 for j in range(len(newArr)-1,-1,-1): # 从后往前取，保证稳定性 10 while newArr[j] != 0: 11 l[sortedIndex] = j 12 sortedIndex -=1 13 newArr[j]-=1 14 return l 桶排序 分类：非比较排序。 核心思想：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。进桶粗排，桶内细排。 细节：在额外空间充足的情况下，尽量增大桶的数量，可以令桶的个数等于元素的个数。 性能：平均时间复杂度$O(n+k)$，最坏时间复杂度$O(n^{2})$(所有元素放到一个桶里)。空间复杂度$O(n+k)$，其中k是桶的个数。 1def bucketSort(l): 2 if len(l) < 1: 3 return l 4 minNum = min(l) 5 maxNum = max(l) 6 if minNum == maxNum: # 数据都一样 7 return l 8 # 假设我们令桶的个数等于元素的个数 9 bucketNum = len(l) 10 # 桶的大小 11 bucketRange = (maxNum-minNum) / bucketNum 12 # 桶数组 13 bucketList = [[] for i in range(bucketNum+1)] 14 # 将元素分配到桶中 15 for i in l: 16 bucketList[int((i-minNum)//bucketRange)].append(i) # 先通过桶粗排序 17 l.clear() 18 for j in bucketList: 19 if j: # 排除空桶 20 j.sort() 21 l.extend(j) # 在桶内部使用了系统默认的排序方法 22 return l 基数排序 分类：非比较排序。 核心思想：从低位开始，先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小......（但是我没明白为什么这样排完之后就可以了）。本质是多关键字排序，也可以算是桶排序的一种。 细节：while内循环实际上是以0-9为10个桶的桶排序。但是我没明白这种排序的实际机制。 性能：时间复杂度为$O(n*k)$，其中$k$是最大数字的位数。空间复杂度为$O(n+k)$，稳定排序。 1def baseSort(l): 2 if len(l)<=1: 3 return l 4 maxNum = max(l) 5 base = 0 6 while maxNum // 10**base >0: 7 # 以0-9为10个桶,while内循实际上是桶排序 8 bucketList = [[] for x in range(10)] 9 for i in l: 10 bucketList[(i//10**base)%10].append(i) 11 temp = list() 12 for j in bucketList: 13 if j: 14 temp.extend(j) 15 l = temp 16 base+=1 17 return l 总结 排序算法分类 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 排序算法复杂度