基础排序算法
基础排序算法
hotarugali
发布于 2022-03-01 16:24:52
发布于 2022-03-01 16:24:52
【注】参考自教材「算法导论」。
1. 插入排序
1.1 简介
插入排序是稳定的、原址的排序算法，其时间复杂度为 O(n^2) 。
1.2 伪代码
InsertionSort(A) {
for j = 2 to A.length
key = A[j]
// 将 A[j] 插入到有序数组 A[1..j-1] 中
i = j - 1
// 将大于 A[j] 的元素后移
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key
} 2. 选择排序
2.1 简介
选择排序是不稳定的、原址的排序算法，其时间复杂度为O(n^2) 。选择排序不稳定的原因在于其在将找到的最小元素交换到有序序列尾部时改变了原来尾部元素与其他元素的相对位置。
2.2 伪代码
SelectSort(A) {
for j = 1 to A.length
loc = j
// 选择未排序序列中最小的
for i = j to A.length
if A[i] < A[j]
loc = i
if loc ≠ j
swap(A[j], A[loc])
}3. 冒泡排序
3.1 简介
冒泡排序是稳定的、原址的排序算法，其时间复杂度为O(n^2) 。
3.2 伪代码
BubbleSort(A) {
for j = 1 to A.length
// 将无序序列中的最大值交换到尾部有序序列的首部
for i = 1 to A.length - j
if A[i] > A[i+1]
swap(A[i], A[i+1])
}以上的伪代码是即使在序列有序的情况下时间复杂度仍然为O(n^2)，可以通过增加一个是否排好序的标识，来判断是否还有需要对序列继续进行冒泡排序。
BubbleSort(A) {
for j = 1 to A.length
// 将无序序列中的最大值交换到尾部有序序列的首部
ordered = true
for i = 1 to A.length - j
if A[i] > A[i+1]
swap(A[i], A[i+1])
// 有交换，说明甚于序列是无序的
ordered = false
// 无交换交换，说明剩余序列是有序的
if ordered
break这样的冒泡排序算法能够达到最好情况下（序列有序）的时间复杂度为 O(n) 。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-08-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录