选择排序 (Selection sort) 是? 种简单直观的排序算法. 它的? 作原理如 下.? 先在未排序序列中找到最?(?)元素, 存放到排序序列的起始位 置, 然后, 再从剩余未排序元素中继续寻找最?(?)元素, 然后放到已排 序序列的末尾. 以此类推, 直到所有元素均排序完毕.
选择排序的主要优点与数据移动有关. 如果某个元素位于正确的最终位置 上, 则它不会被移动. 选择排序每次交换? 对元素, 它们当中? 少有? 个将 被移到其最终位置上, 因此对 n 个元素的表进? 排序总共进?? 多 n-1 次交 换. 在所有的完全依靠交换去移动元素的排序? 法中, 选择排序属于? 常好 的? 种.
选择排序分析
排序过程:
- 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 # 如果选择出的数据不在正确位置, 进? 交换 if min_index != i: alist[i], alist[min_index] = alist[min_index], al ist[i]
- alist = [54,226,93,17,77,31,44,55,20]
- selection_sort(alist) print(alist)
时间复杂度
最优时间复杂度: O(n ) 最坏时间复杂度: O(n ) 稳定性: 不稳定(考虑升序每次选择最? 的情况)
选择排序演示
插? 排序
插? 排序 (英语: Insertion Sort) 是? 种简单直观的排序算法. 它的? 作原 理是通过构建有序序列, 对于未排序数据, 在已排序序列中从后向前扫描, 找到相应位置并插?. 插? 排序在实现上, 在从后向前扫描过程中, 需要反 复把已排序元素逐步向后挪位, 为最新元素提供插? 空间.
插? 排序分析
- def insert_sort(alist): # 从第? 个位置, 即下标为 1 的元素开始向前插? for i in range(1, len(alist)): # 从第 i 个元素开始向前? 较, 如果? 于前? 个元素, 交换位置 for j in range(i, 0, -1): if alist[j] < alist[j-1]:
- alist[j], alist[j-1] = alist[j-1], alist[j]
- alist = [54,26,93,17,77,31,44,55,20] insert_sort(alist) print(alist)
时间复杂度
最优时间复杂度: O(n) (升序排列, 序列已经处于升序状态) 最坏时间复杂度: O(n ) 稳定性: 稳定
插? 排序演示
python 数据结构与算法(13)
来源: http://www.bubuko.com/infodetail-2866005.html