排列算法（冒泡排序、选择排序、插入排序（动图分析））

文章目录

排序排序算法的稳定性冒泡排序算法分析时间复杂度 选择排序算法分析时间复杂度 插入排序算法分析时间复杂度

排序

排序算法（是一种能将一串数据依照特定顺序进行排列的一种算法。

排序算法的稳定性

稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。

冒泡排序

算法分析

// An highlighted block '''冒泡排序''' def bubble_sort(alist): n=len(alist) #需要进行排列的次数 for i in range(n-1): # 需要排列的数组 for j in range(0,(n-1)-i): if alist[j] > alist[j+1]: alist[j], alist[j+1] = alist[j+1], alist[j] li = [11,13,5,7,20] a=[11,13,5,7,20,9,15,10] bubble_sort(li) print(li) bubble_sort(a) print(a)

时间复杂度

最优时间复杂度：O(n) 最坏时间复杂度：O(n^2) 稳定性：稳定

选择排序

算法分析

// An highlighted block '''选择排序''' def selection_sort(alist): n = len(alist) # 需要进行n-1次选择操作 for i in range(n-1): # 记录最小位置 min_index = i # 从i+1位置到末尾选择出最小数据 for j in range(i+1, n): if alist[j] < alist[min_index]: min_index = j alist[i], alist[min_index] = alist[min_index], alist[i] li = [11,13,5,7,20] a=[11,13,5,7,20,9,15,10] selection_sort(li) print(li) selection_sort(a) print(a)

时间复杂度

最优时间复杂度：O(n^2) 最坏时间复杂度：O(n^2) 稳定性：不稳定（考虑升序每次选择最大的情况）

插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间

算法分析

// An highlighted block '''插入排序''' def insert_sort(alist): # 从第二个位置，即下标为1的元素开始向前插入 n=len(alist) for i in range(1, n): # 从第i个元素开始向前比较，如果小于前一个元素，交换位置 for j in range(i, 0, -1): if alist[j] < alist[j-1]: alist[j], alist[j-1] = alist[j-1], alist[j] li = [11,13,5,7,20] a=[11,13,5,7,20,9,15,10] insert_sort(li) print(li) insert_sort(a) print(a)

时间复杂度

最优时间复杂度：O(n) （升序排列，序列已经处于升序状态） 最坏时间复杂度：O(n^2) 稳定性：稳定