【注】参考自教材「算法导论」。

1. 插入排序

1.1 简介

插入排序是稳定的、原址的排序算法，其时间复杂度为 O(n2)O(n^2) 。

1.2 伪代码

1
2
3
4
5
6
7
8
9
10
11
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(n2)O(n^2) 。选择排序不稳定的原因在于其在将找到的最小元素交换到有序序列尾部时改变了原来尾部元素与其他元素的相对位置。

2.2 伪代码

1
2
3
4
5
6
7
8
9
10
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(n2)O(n^2) 。

3.2 伪代码

1
2
3
4
5
6
7
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(n2)O(n^2)，可以通过增加一个是否排好序的标识，来判断是否还有需要对序列继续进行冒泡排序。

1
2
3
4
5
6
7
8
9
10
11
12
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)O(n) 。