冒泡、选择、插入排序算法及其时间复杂度详解

冒泡排序选择排序插入排序

冒泡排序

流程：

把0到N个元素中的最大值放在N位置把0到N-1个元素中的最大值放在N-1位置把0到N-2个元素中的最大值放在N-2位置… …

时间复杂度：严格的O(N²)的算法（即使数据已经排好序，还要全部按照程序流程比较、交换一遍，所以称为严格O(N²)）

代码：

#冒泡排序算法 def bubbling_sort(lst): if len(lst)==0 or len(lst)<2: return for i in range(1,len(lst)): j = i-1 while j>=0 and lst[j] > lst[j+1]: swap(lst,j,j+1) j = j-1 def swap(lst,a,b): c = lst[a] lst[a] = lst[b] lst[b] = c ''' 随机产生0~10000之间的100个数进行排序 算法执行两百次耗时的平均值为：0.0085s '''

选择排序

流程：

找出第0到N个元素中的最小值放在0位置找出第1到N个元素中的最小值放在1位置找出第2到N个元素中的最小值放在2位置… …

时间复杂度：严格的O(N²)

代码：

def selection_sort(lst): for i in range(len(lst)-1): min_index = i for j in range(i+1,len(lst)): if lst[j]<lst[min_index]: min_index = j swap(lst,i,min_index) def swap(lst,a,b): c = lst[a] lst[a] = lst[b] lst[b] = c ''' 随机产生0~10000之间的100个数进行排序 算法执行两百次耗时的平均值为0.01s '''

插入排序

流程：

首先比较1位置数和0位置数，若1位置数小于0位置数则交换。到此前两个数已经排好了。3位置数和2位置数比较，若小则交换，若交换到2位置则和1位置数比较，小则交换。到此前三个数已经排好。4位置数和3位置数比较，小则交换，若交换到3位置则和2位置比较，小则交换，若交换到2位置则和1位置数比较，小则交换，到此前4个数已经排好。依次类推，像扑克牌一样，把新的牌插入到前面已经排好序的牌当中，使得前面的全比它小，后面的全比它大。按照此方式，直到最后一个数。

时间复杂度：O(N)~O(N²) 之间，若是一个已经排好序的数据列表，那么只需要两个相邻的数据进行比较，并不需要交换，所以复杂度为O(N)，若是一个完全逆序的数据列表，那么每个位置的数据都需要和前面的全部数逐个进行交换，因此复杂度为O(N²)。所以复杂度在O(N)~O(N²) 之间，受数据排序情况的影响。

代码：

def insertion_sort(lst): if len(lst)==0 or len(lst)<2: return for i in range(1,len(lst)): j = i-1 while j>=0 and lst[j] > lst[j+1]: swap(lst,j,j+1) j = j-1 def swap(lst,a,b): c = lst[a] lst[a] = lst[b] lst[b] = c ''' 随机产生0~10000之间的100个数进行排序 算法执行两百次耗时的平均值为0.0003s '''

以上内容为作者在学习过程中的经验总结，如有错误及不妥之处，欢迎大家留言或私信指出！