数据结构与算法之排序算法总结（python版本）

排序算法性能比较1.插入排序(Insertion Sort)2.希尔排序(Shell Sort)3.冒泡排序(Bubble Sort)4.快速排序(Quick Sort)5.选择排序(Selection Sort)6.堆排序(Heap Sort)7.归并排序(Merge Sort)8.基数排序(Radix Sort)9.拓扑排序(Topological Sort)

排序算法性能比较

参考了王卓老师的数据结构与算法课程（数据结构与算法课程-王卓老师） 其它参考：（菜鸟教程排序算法）

1.插入排序(Insertion Sort)

参考链接：（Python 插入排序）

1. 基本思想 在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

2. 平均时间复杂度：O(n^2)

3. python代码实现

def insertionSort(arr): for i in range(1, len(arr)): #外循环执行n-1次 key = arr[i] j = i-1 while j >=0 and key < arr[j] : #key为当前待进行插入排序的数 arr[j+1] = arr[j] j -= 1 arr[j+1] = key arr = [12, 11, 13, 5, 6] insertionSort(arr) print ("排序后的数组:") for i in range(len(arr)): print ("%d" %arr[i])

2.希尔排序(Shell Sort)

参考链接：（Python 希尔排序）

1. 基本思想

在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

2. 平均时间复杂度：O(n^1.5)

3. python代码实现

def shellSort(arr): n = len(arr) gap = int(n/2) #第一次间隔取为数组长度的一半 while gap > 0: for i in range(gap,n): temp = arr[i] j = i while j >= gap and arr[j-gap] > temp: arr[j] = arr[j-gap] j -= gap arr[j] = temp gap = int(gap/2) arr = [ 12, 34, 54, 2, 3] n = len(arr) print ("排序前:") for i in range(n): print(arr[i]) shellSort(arr) print ("\n排序后:") for i in range(n): print(arr[i])

3.冒泡排序(Bubble Sort)

参考链接：（Python 冒泡排序）

1. 基本思想

从前往后不断比较相邻两个数的大小，较大的数往后，较小的数往前移。

2. 平均时间复杂度：O(n^2)

3. python代码实现

# 基础版本 ''' def bubbleSort(arr): n = len(arr) # 遍历所有数组元素 for i in range(n): #外循环次数为n-1次 # Last i elements are already in place for j in range(0, n-i-1): #内循环次数为n-i-1次 if arr[j] > arr[j+1] : arr[j], arr[j+1] = arr[j+1], arr[j] #两两交换 ''' #优化版本 #针对问题： #数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。 #方案： #设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。 #这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。 def bubbleSort(arr): n = len(arr) # 遍历所有数组元素 for i in range(n): #外循环次数为n-1次 flag = False # Last i elements are already in place for j in range(0, n-i-1): #内循环次数为n-i-1次 if arr[j] > arr[j+1] : arr[j], arr[j+1] = arr[j+1], arr[j] #两两交换 flag = True if not flag: break arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print ("排序后的数组:") for i in range(len(arr)): print ("%d" %arr[i])

4.快速排序(Quick Sort)

参考链接：（Python 快速排序）

1. 基本思想（分治）

先从数列中取出一个数作为基准值（pivot）；将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；对左右两个小数列重复第二步，直至各区间只有1个数。

选取基准值有数种具体方法（例如中间数或者随机数），此选取方法对排序的时间性能有决定性影响。

2. 平均时间复杂度：O(n*logn)

3. python代码实现

def partition(arr,low,high): i = low-1 # 最小元素索引 -1 pivot = arr[high] for j in range(low , high): # 0 # 当前元素小于或等于 pivot if arr[j] <= pivot: # 1 1 i = i+1 arr[i],arr[j] = arr[j],arr[i] arr[i+1],arr[high] = arr[high],arr[i+1] return i+1 # arr[] --> 排序数组 # low --> 起始索引 # high --> 结束索引 # 快速排序函数 def quickSort(arr,low,high): if low < high: pi = partition(arr,low,high) quickSort(arr, low, pi-1) quickSort(arr, pi+1, high) # {10, 7, 8, 9, 1, 5} -> {1, 5}, {7, 8, 9, 10} -> 1,5 {7,8,9}，10 -> 1, 5, {7,8}, 9，10 arr = [10, 7, 8, 9, 1, 5] n = len(arr) quickSort(arr,0,n-1) print ("排序后的数组:") for i in range(n): print ("%d" % arr[i])

5.选择排序(Selection Sort)

参考链接：（Python 选择排序）

1. 基本思想

在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；第二次遍历n-2个数，找到最小的数值与第二个元素交换；。。。第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

2. 平均时间复杂度：O(n^2)

3. python代码实现

import sys def selectSort(arr): for i in range(len(arr)): # 外循环执行n-1次 min_idx = i for j in range(i+1, len(arr)): if arr[min_idx] > arr[j]: min_idx = j arr[i], arr[min_idx] = arr[min_idx], arr[i] A = [64, 25, 12, 22, 11] print ("排序后的数组：") selectSort(A) for i in range(len(A)): print("%d" %A[i])

6.堆排序(Heap Sort)

参考链接：（Python 堆排序） 学习教程：（堆排序1）（堆排序2–堆调整）（堆排序3–建立堆） 1. 基本思想

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

2. 平均时间复杂度：O(n*logn) 由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)。二次操作时间相加还是O(N * logN)。

3. python代码实现

def heapify(arr, n, i): largest = i l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 if l < n and arr[i] < arr[l]: largest = l if r < n and arr[largest] < arr[r]: largest = r if largest != i: arr[i],arr[largest] = arr[largest],arr[i] # 交换 heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build a maxheap. for i in range(n, -1, -1): heapify(arr, n, i) # 一个个交换元素 for i in range(n-1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # 交换 heapify(arr, i, 0) arr = [ 12, 11, 13, 5, 6, 7] heapSort(arr) n = len(arr) print ("排序后") for i in range(n): print ("%d" %arr[i])

7.归并排序(Merge Sort)

参考链接：（Python 归并排序）

1. 基本思想

分治法:

分割：递归地把当前序列平均分割成两半。集成：在保持元素顺序的同时将上一步得到的子序列集成到一起（归并）。

2. 平均时间复杂度：O(n*logn) 归并排序的效率是比较高的，设数列长为N，将数列分开成小数列一共要logN步，每步都是一个合并有序数列的过程，时间复杂度可以记为O(N)，故一共为O(N*logN)。

3. python代码实现

def merge(arr, l, m, r): n1 = m - l + 1 n2 = r- m # 创建临时数组 L = [0] * (n1) R = [0] * (n2) # 拷贝数据到临时数组 arrays L[] 和 R[] for i in range(0 , n1): L[i] = arr[l + i] for j in range(0 , n2): R[j] = arr[m + 1 + j] # 归并临时数组到 arr[l..r] i = 0 # 初始化第一个子数组的索引 j = 0 # 初始化第二个子数组的索引 k = l # 初始归并子数组的索引 while i < n1 and j < n2 : if L[i] <= R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 # 拷贝 L[] 的保留元素 while i < n1: arr[k] = L[i] i += 1 k += 1 # 拷贝 R[] 的保留元素 while j < n2: arr[k] = R[j] j += 1 k += 1 def mergeSort(arr,l,r): if l < r: m = int((l+(r-1))/2) # 递归的二分数据 mergeSort(arr, l, m) mergeSort(arr, m+1, r) merge(arr, l, m, r) arr = [12, 11, 13, 5, 6, 7] n = len(arr) print ("给定的数组") for i in range(n): print ("%d" %arr[i]), mergeSort(arr,0,n-1) print ("\n\n排序后的数组") for i in range(n): print ("%d" %arr[i])

8.基数排序(Radix Sort)

参考链接：（Python 基数排序）

1. 基本思想

分配+收集 基数排序，也叫桶排序或箱排序；设置若干个箱子，将关键字为k的数据放入第k个箱子，然后再按序号将非空的连接起来。

2. 平均时间复杂度：O(k(n+m))

3. python代码实现

def radixSort(s): """基数排序""" i = 0 # 记录当前正在排拿一位，最低位为1 max_num = max(s) # 最大值 j = len(str(max_num)) # 记录最大值的位数 while i < j: bucket_list =[[] for _ in range(10)] #初始化桶数组 for x in s: bucket_list[int(x / (10**i)) % 10].append(x) # 找到位置放入桶数组 print(bucket_list) s.clear() for x in bucket_list: # 放回原序列 for y in x: s.append(y) i += 1 if __name__ == '__main__': a = [334,5,67,345,7,345345,99,4,23,78,45,1,3453,23424] radix_sort(a) print(a)

9.拓扑排序(Topological Sort)

参考链接：（Python 拓扑排序）

1. 基本思想 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

2. 平均时间复杂度：O(n+e) 如果AOV网络有n个顶点，e条边，在拓扑排序的过程中，搜索入度为零的顶点所需的时间是O(n)。在正常情况下，每个顶点进一次栈，出一次栈，所需时间O(n)。每个顶点入度减1的运算共执行了e次。所以总的时间复杂为O(n+e)。

3. python代码实现

from collections import defaultdict class Graph: def __init__(self,vertices): self.graph = defaultdict(list) self.V = vertices def addEdge(self,u,v): self.graph[u].append(v) def topologicalSortUtil(self,v,visited,stack): visited[v] = True for i in self.graph[v]: if visited[i] == False: self.topologicalSortUtil(i,visited,stack) stack.insert(0,v) def topologicalSort(self): visited = [False]*self.V stack =[] for i in range(self.V): if visited[i] == False: self.topologicalSortUtil(i,visited,stack) print (stack) g= Graph(6) g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); print ("拓扑排序结果：") g.topologicalSort()