初级排序算法

发表于 更新于 分类于

《算法（第4版）》笔记

选择排序

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

选择排序的缺点：一个已经有序的数组或是主键全部相等的数组和一个元素随机排列的数组所用的排序时间竟然一样长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// c++
// 将容器a按升序排列
template<class T>
void selection_sort(T& a)
{
    int n = a.size();
    for (int i=0; i<n; ++i)
    {
        int min = i;
        for (int j=i+1; j<n; ++j)
        {
            if (a[j] < a[min])
                min = j;
        }

        std::swap(a[i], a[min]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
# python
# 将列表a按升序排列
def selection_sort(a):
    n = len(a)
    for i in range(n):
        min = i
        for j in range(i+1, n):
            if a[j] < a[min]:
                min = j

        a[i], a[min] = a[min], a[i]

插入排序

通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当的位置。在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移动一位。这种算法叫做插入排序。

和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大的其中的元素已经有序（或接近有序）的数组进行排序将会比对随机顺序的数组或是逆序数组进行排序要快得多。

插入排序对于部分有序的数组十分高效，也很适合小规模数组。

在1980年本书第1版完成之时插入排序就比选择排序快一倍，现在仍然是这样。

1
2
3
4
5
6
7
8
9
10
11
12
// c++
// 将容器a按升序排列
template<class T>
void insertion_sort(T& a)
{
    int n = a.size();
    for (int i=1; i<n; ++i)
    {
        for (int j=i; j>0 && a[j]<a[j-1]; --j)
            std::swap(a[j], a[j-1]);
    }
}
1
2
3
4
5
6
7
8
9
10
# python
# 将列表a按升序排列
def insertion_sort(a):
    n = len(a)
    for i in range(1, n):
        for j in range(i, 0, -1):
            if a[j] < a[j-1]:
                a[j], a[j-1] = a[j-1], a[j]
            else:
                break

希尔排序

希尔排序是一种基于插入排序的快速的排序算法。

对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组（见图2.1.2）。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的h序列，我们都能够将数组排序。这就是希尔排序。使用的h序列被称为递增序列。

图2.1.2

（如上图所示，当h=4时，即间隔为4，整个数组分为4个子数组，分别对4个子数组使用插入排序进行排序。h的取值不断减小，当为1时，排序后整个数组变为有序，排序结束。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// c++
// 将容器a按升序排列
template<class T>
void shell_sort(T& a)
{
    int n = a.size();

    // 递增序列 1, 4, 13, 40, 121, ...
    // 确定h初始值
    int h = 1;
    while (h < n/3)
        h = 3 * h + 1;

    while (h >= 1)
    {
        // 将数组变为h有序
        for (int i=h; i<n; ++i)
        {
            for (int j=i; j>=h && a[j] < a[j-h]; j-=h)
                std::swap(a[j], a[j-h]);
        }

        h = h / 3;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# python
# 将列表a按升序排列
def shell_sort(a):
    n = len(a)

    # 递增序列 1, 4, 13, 40, 121, ...
    # 确定h初始值
    h = 1
    while h < n / 3:
        h = 3 * h + 1

    while h >= 1:
        # 将数组变为h有序
        for i in range(h, n):
            for j in range(i, h-1, -h):
                if a[j] < a[j-h]:
                    a[j], a[j-h] = a[j-h], a[j]
                else:
                    break

        h = h // 3

如何选择递增序列呢？要回答这个问题并不简单。算法的性能不仅取决于h，还取决于h之间的数学性质，比如它们的公因子等。有很多论文研究了各种不同的递增序列，但都无法证明某个序列是“最好的”。

和选择排序以及插入排序形成对比的是，希尔排序也可以用于大型数组。它对任意排序（不一定是随机的）的数组表现也很好。

希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大。

目前最重要的结论是它的运行时间达不到平方级别。