MENU

内部排序算法详解

2019 年 08 月 01 日 • 阅读: 61 • 算法

内部排序是指待排序列完全位于内存中的排序过程,适合内存充足,能够一次性加载整个序列的情况,与此对应的还有外部排序。本文将详细介绍几种经典非线性内部排序算法的原理和实现,并分析各自的稳定性和时空性能。

排序算法的稳定性

采用何种排序算法,除了考虑数据规模和时空复杂度,特定场景下,稳定性也常常成为重要指标。我们称,满足以下特征的排序算法具有稳定性:使用某排序算法对待排序列排序,假设序列中有两个元素 e1 和 e2,e1.key = e2.key 且 e1 位于 e2 之前,使用该排序算法后,e1 仍处于 e2 之前。

既然 e1.key = e2.key,那么最终谁在前面又有什么影响呢?大多数情况下确实没有影响,但如果对复杂对象的多个属性排序,且下一次排序要保持上一次的某些局部相邻顺序,就要使用稳定的排序算法。例如要对商品对象按销量排序,如果销量相同就按价格排序。我们可以首先按价格排序,随后使用稳定的算法对销量排序。当然你也可以先按销量排序,随后遍历序列,在每个销量相同的区间里分别按价格排序,不过这样实现相对复杂,也不适合价格本身有序的情况。

快速排序

之所以首先介绍快速排序,一来因为它的平均时间复杂度为 O(nlogn),空间复杂度为 O(logn),在所有内部排序算法中综合性能最优,二来其主要思想是上一节介绍的 分治与递归,可当作递归的应用讲解。

基本思想

回顾能用递归解决的问题必须满足的三个条件:首先,原问题能够分解为几个规模较小的子问题。其次,原问题和子问题是同一问题。第三,存在终止条件。具体到排序,试想这样的操作:选定待排序列中任一元素作为分界点,将小于分界点的元素都放到其左边,大于分界点的元素都放到其右边,问题便转换为对分界点两侧的序列排序。分好类后,对于每个子序列,仍可使用上面的方法排序,即从原问题到子问题,规模变小,解决方法相同。当子序列仅有一个元素时,无需排序,这便是终止条件。可见,排序问题可以用递归解决。

现在寻找递推公式,假如要对数组下标从 p 到 r 之间的元素由小到大排序,选择在此之间的任意元素作为分界点 pivot,遍历待排序列,将小于 pivot 的元素放到其左边,大于 pivot 的元素放到其右边,下面是一个示例

                  pivot
                    ↓
[8][10][2][3][6][1][5]
 p                  r
        分 |
        区 ↓
[2][3][1][5][6][8][10]
 p        q         r

记对下标从 p 到 r 之间的序列排序的过程为 f(p, r),q 是分区结束后 pivot 的数组下标,则对下标从 p 到 q-1 之间序列排序的过程为 f(p, q-1),对下标从 q+1 到 r 之间序列排序的过程为 f(q+1, r),要使整个序列有序,只要对两个子序列分别排序即可,所以 f(p, r) = f(p, q-1) and f(q+1, r)。

当子序列仅有一个元素,即 p >= r 时,排序结束,加上 > 的原因将在后面说明。下面是递归函数的实现代码

// 分区函数
int partition(int[] a, int p, int r) {
    // 选择任意元素作为分区点 pivot,对 a 分区,
    //+ 使 pivot 左边都小于它,右边都大于它,
    //+ 最后返回分区结束后 pivot 的下标
    // ...
}

void quickSort(int[] a, int p, int r) {
    if (p >= r) return;
    int q = partition(a, p, r);
    quickSort(a, p, q-1);
    quickSort(a, q+1, r);
}

现在考虑如何高效实现 partition 函数,基本想法是开辟两个新数组 b 和 c,将小于 pivot 的元素拷贝到 b,大于 pivot 的元素拷贝到 c,最后再将 b,c 拷贝回 a。但这样实现的空间复杂度是 O(2n),能否将其降到 O(1) 呢?考虑这样的做法:选定最后一个元素 a[r] 为 pivot,用 i 将 a[p, r-1] 分成两部分,记 a[p, i-1] 为 已处理区间,a[i, r-1] 为未处理区间。起初 i=p,遍历未处理区间,每次从中取一个元素 a[j],若小于 pivot,则将其加入已处理区间末尾,即 a[i] 位置,此时已处理区间增加一个元素,i++。最终,i 前面都比 pivot 大,将 pivot 放到 i 位置,返回 i。下面是完整示例

p           r
ij         pivot
6  11 3  9  8    6<8,将 6 加入已处理序列,i 后移。继续遍历未处理序列,j 后移

   ij
6  11 3  9  8    11>8,继续遍历未处理序列,j 后移

    i j
6  11 3  9  8    3<8,将 3 加入已处理序列,i 后移。继续遍历未处理序列,j 后移

       i  j
6  3  11  9  8   9>8,未处理序列遍历完毕

      i  j
6  3  8  9  11   交换 8 和 11,将 pivot 移动到已处理序列末尾

我们知道往数组插入元素的平均复杂度是 O(n),那么整个 partition 函数的时间复杂度将是 O(n^2),显然是可不取的。在 操作数组的几个技巧 中我们提到,如果仅将数组当作数据集合使用,无需考虑元素顺序,那么将元素插入到第 k 个位置的操作可简化为:将第 k 个位置的元素插入到数组尾,将新元素放到第 k 个位置上,不做数据搬移,时间复杂度为 O(1)。

此处,因为 a[i] 和 a[j] 都处于未处理序列中,而未处理序列的顺序我们并不关心,所以要将 a[j] 插入到 a[i] 的位置上,只需将两者交换,这样,插入便成为 O(1) 操作,整个 partition 函数的时间复杂度就是 O(n)。因为没有使用额外空间,空间复杂度是 O(1)。下面是 partition 的实现代码

void swap(int[] a, int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

int partition(int[] a, int p, int r) {
    // 选取最后一个元素作为分界点
    int pivot = a[r];
    // 起初,整个序列都处于未处理区间
    int i = p;
    // 遍历未处理区间
    for( int j=i; j<r; j++) {
        // 如果元素比分界点小,则将其放到已处理序列末尾
        if (a[j] < pivot)
            // 已处理序列增加一个元素
            swap(a, i++, j);
    }
    // a[i] 之前都小于 pivot,将 pivot 放到 i 位置即可
    swap(a, i, r);
    return i;
}

考虑序列 1,2,3,4,5,第一次调用 partition 后将返回 4,所以会执行 quickSort(0,3),quickSort(5, 4),此时 5 > 4,这就是递归终止条件写成 p >= r 的原因。

稳定性

考虑序列 6,8,7,6,3,5,在 3 之前的元素都大于 5,而 3<5,所以第一个 6 要与 3 交换,这样序列中两个 6 的顺序就发生了变化,由此可见,快速排序是 不稳定 的排序算法。

性能分析

最好时间复杂度

快排所需时间等于对数组进行划分的时间加上两次递归调用的时间。假如每次 partition 都能把数组分成大小近似相等的两个子区间,那么递归的层数将到达最小,所花时间最少。记对 n 个元素进行快速排序的时间为 T(n),那么对每个子区间排序的时间就是 T(n/2),有 T(n) = n + 2 * T(n/2),其中 n 为划分所花时间。当 n = 1 时无需排序,即 T(1) = C。假如整个过程进行了 k 次递归,有

$$ \begin{equation} \begin{aligned} T(n) &= n + 2 * T(\frac{n}{2})\\ &= 2n + 4 * T(\frac{n}{4})\\ &= 3n + 8 * T(\frac{n}{8})\\ &...\\ &= kn + 2^{k} * T(\frac{n}{2^{k}}) \end{aligned} \end{equation} $$

当 n/2^k = 1,即 k = logn 时,T(n) = nlogn + Cn。所以快速排序的最好时间复杂度是 O(nlogn)。

最坏时间复杂度

如果待排序列初始状态是逆序,每次递归前半部分没有元素,后半部分元素个数为整个序列长度减 1,所以总共要进行 n 层递归,每层递归中,划分操作的时间复杂度是 O(n),所以最坏时间复杂度是 O(n^2)。

平均时间复杂度

记对 n 个数进行划分后,k-1 个数被划分到左边,k 可能是 1-n 之间的任意数字,且每种可能概率相等,都是 1/n。所以对 n 个数进行快速排序,其平均时间的递推公式如下,其中 Cn 是划分所用时间:

$$ T(n)=Cn+\frac{1}{n}\sum_{k=1}^n[T(k-1)+T(n-k)] $$

记 S(n-1) = T(0) + T(1) + ... + T(n-1),有

$$ T(n)=Cn+\frac{2}{n}S(n-1) $$

移项得

$$ S(n-1)=\frac{n}{2}[T(n)-Cn] $$

$$ S(n-2)=\frac{n-1}{2}[T(n-1)-C(n-1)] $$

因为 T(0)=T(1)=1,所以

$$ T(n-1)=S(n-1)-S(n-2)=\frac{n}{2}[T(n)-Cn)]-\frac{n-1}{2}[T(n-1)-C(n-1)] $$

等号两边同时乘 2 并移项整理得

$$ nT(n)=(n+1)T(n-1)+2Cn-C $$

为了简化计算,去除最后的非决定项 -C,两边同时除以 n(n+1) 得

$$ \frac{T(n)}{n+1}=\frac{T(n-1)}{n}+\frac{2C}{n+1} $$

现在进行叠缩

$$ \frac{T(n-1)}{n}=\frac{T(n-2)}{n-1}+\frac{2C}{n}\\ \frac{T(n-2)}{n-1}=\frac{T(n-3)}{n-2}+\frac{2C}{n-1}\\ ...\\ \frac{T(2)}{3}=\frac{T(1)}{2}+\frac{2C}{3} $$

将以上叠缩式相加并约分整理得

$$ \frac{T(n)}{n+1}=\frac{T(1)}{2}+2C\sum_{i=3}^{n+1}\frac{1}{i} $$

上式的最后一项是调和级数的部分和,两边同时乘以 n+1 得

$$ T(n)=2C(n+1)[ln(n+1)+r-3]+\frac{n+1}{2},r 为欧拉-马歇罗尼常数 $$

所以,快速排序的平均时间复杂度是 O(nlogn)。

空间复杂度

最坏情况下,快速排序要进行 n 层递归,空间复杂度 O(n),最好和平均情况下要进行 logn 层递归,空间复杂度 O(logn)。

快速排序的优化

针对快排的优化主要从四个方面入手。第一,固定位置选取 pivot 容易导致分割不均,通常采用三数取中法。第二,对于重复元素过多的序列,可将所有与 pivot 相等的元素移到 pivot 两边,下次递归时忽略这些元素。第三,元素较少时采用插入排序。第四,将第二个递归改为循环,即尾递归优化,通常编译器会自动进行。

应用:寻找第 K 大数

有很多种做法,首先是直接排序,时间复杂度为 O(nlogn)。其次是循环 K 次,每次排除当前数组的最小值,时间复杂度 O(Kn)。更好的做法是利用快排的分区思想,例如数组 a[p,r],每次选取 a[r] 作为 pivot 将数组分成三个区 a[p, pivot-1],a[pivot] 和 a[pivot+1,r]。如果 pivot+1 = K,则 a[pivot] 就是第 K 大数。如果 pivot+1 < K,则结果在 a[pivot+1,r] 中,反之结果在 a[p, pivot-1] 中。假如 pivot 每次都能将数组平分,那么整个过程要遍历的元素个数为

$$ \begin{equation} \begin{aligned} T(n)&=n+\frac{n}{2}+\frac{n}{4}+...+\frac{n}{2^{k}}+1\\ &=n(1+\frac{1}{2}+\frac{1}{4}+...+\frac{1}{2^k})+1\\ &=n\frac{1-\frac{1}{2^{k+1}}}{1-\frac{1}{2}}+1\\ &=2n-\frac{n}{2^k}+1,\ 2^{k+1}=n\\ &=2n-1 \end{aligned} \end{equation} $$

所以时间复杂度为 O(n),下面是示例代码

int kTh(int[] a, int p, int r, int k) {
    int q = partition(a, p, r);
    int cTh = 0; // 保存 q 位置是第几大数
    int left = p; // left 表示划分区间的左端点
    while ((cTh += q + 1 - left) != k) {
        if (cTh > k) {
            left = p;
            cTh = 0; // 在左区间搜索时,要清空上一次是第几大数,右区间则要加上
            q = partition(a, p, q - 1);
        } else {
            left = q + 1;
            q = partition(a, q + 1, r);
        }
    }
    return a[q];
}

递归实现更容易理解。

int kTh(int[] a, int p, int r, int k) {
    int q = partition(a, p, r);
    int cTh = q + 1 - p;

    if (cTh == k)
        return a[q];
    else if (cTh > k)
        return kTh(a, p, q - 1, k);
    else
        return kTh(a, q + 1, r, k - cTh);
}

归并排序

归并排序与快速排序一样,也利用了分治思想,并且其最好最坏和平均时间复杂度都是 O(nlogn),除此之外它还是稳定的排序算法,唯一缺点是空间复杂度为 O(n)。

基本思想

将待排序列从中间分成两部分,对它们分别排序,最后将排好序的两部分合并。下面是一个示例:

---                11 8  3  9  7  1  2  5
 ↓                ↙                      ↘
           11 8  3  9                  7  1  2  5
分         ↙         ↘                ↙         ↘
         11 8        3  9             7  1        2  5
 ↑      ↙   ↘        ↙   ↘       ↙   ↘      ↙   ↘  
---    11    8       3    9        7      1      2     5
 ↓      ↘   ↙        ↘   ↙       ↘   ↙      ↘   ↙
        8  11         3  9            1  7        2  5
合        ↘          ↙                 ↘        ↙
          3  8  9  11                    1  2  5  7
 ↑                 ↘                     ↙
---                 1  2  3  5  7  8  9  11

如上图所示,对于每个子序列我们仍然可以继续分割,直到子序列只有一个元素时,它肯定是有序的,随后将有序子序列逐层合并就能使整个序列有序。记为 p,r 间序列排序的过程为 mergeSort(p,r),以 p,r 中点 q 将序列分成前后两部分,则对两部分分别排序的过程为 mergeSort(p,q) 及 mergeSort(q+1,r),合并数组 a,b 的过程为 merge(a,b),则有以下递推公式

mergeSort(p,r) = merge(mergeSort(p,q), mergeSort(q+1,r)), q=(p+r)/2

递归终止条件为 p >= r,大于号在序列仅有 2 个元素时取到,不妨令 p=0,r=1,则 q = (p+r)/2 = 0,此时会执行 mergeSort(0, 0) 和 mergeSort(1, 0),满足 p>=r。下面是实现代码

void mergeSort(int[] a, int p, int r) {
    if (p >= r) return;
    int q = (p+r)/2;
    mergeSort(a, p, q);
    mergeSort(a, q+1, r);
    merge(a, p, r, q);
}

上述代码中 merge 函数的作用是合并原始序列 a[p,r] 的前后两部分,具体做法是开辟一个与待合并序列大小相等的新数组 tmp,随后设定两个指针 i 和 j 分别指向两个待合并序列的起始位置 p 和 q+1,比较 a[i] 和 a[j],将较小者放入 tmp 末尾,同时相应指针后移。如果某个指针走至所在部分末尾,则将另一指针所在部分剩余元素全部插入 tmp 末尾,最后将 tmp 拷贝回数组 a。下面是实现代码

void merge(int[] a, int p, int r, int q) {
    int[] tmp = new int[r-p+1];
    int i = p;
    int j = q+1;
    int k = 0;

    while (i<=q && j<=r)
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];

    while (i <= q)
        tmp[k++] = a[i++];

    while (j <= r)
        tmp[k++] = a[j++];

    for (k=0,; k<r-p+1; k++)
        a[p+k] = tmp[k];
}

稳定性

容易看出,归并排序的稳定性依赖于合并函数 merge,具体来说是函数的第 9 行 if (a[i] <= a[j])。上述代码实现的是从小到大排序,其中 a[i] 位于前半部分,a[j] 位于后半部分。根据语义,当 a[i]=a[j] 时,a[i] 会先于 a[j] 进入数组,这就决定了 a[i] 最终仍会位于 a[j] 之前,所以归并排序是 稳定 的排序算法。

性能分析

时间复杂度

记对含 n 个元素的序列排序所需时间为 T(n),由于每次都是平分序列,所以 T(n) = 2*T(n/2) + n,其中 n 为合并所需时间,有以下递推公式

$$ \begin{equation} \begin{aligned} T(n) &=2*T(\frac{n}{2})+n\\ &=2*2*T(\frac{n}{4})+2n\\ &...\\ &=2^{k}*T(\frac{n}{2^{k}})+kn\\ \end{aligned} \end{equation} $$

假设整个排序过程需要 k 层递归,由于递归的终止条件是 T(1) = 1,可令 n/2^k = 1,即 k=logn,则

$$ T(n)=n+n*log_2n $$

所以,归并排序的时间复杂度是 O(nlogn)。需要注意的是,由于每次都是平分序列,无论初始状态如何,归并的时间都是相同的,即最好、最坏和平均时间复杂度都是 O(nlogn)。

空间复杂度

归并排序中的 merge 函数需要 O(n) 的额外空间,虽然整个排序过程要进行 logn 层递归,但上层 merge 执行时,下层 merge 已经将空间释放,又 O(logn) < O(n),所以归并排序的空间复杂度是 O(n)。

插入排序

基本思想

往有序数组插入新元素,要求插入后数组仍然有序,做法是遍历数组,找到合适的位置后将后面所有元素搬移,最后将新元素插入到那个位置,插入排序便利用了该思想。

和快速排序的 partition 函数一样,插入排序也将数组分为 已排序未排序 两个区间,起初已排序区间只有一个元素,即数组首元素。每次取未排序区间的第一个元素,在已排序区间中找到合适位置并插入,重复这个过程,直到未排序区间为空,算法结束。下面是一个示例

     sorted | unsorted
          4 | 5 6 1 3 2
        4 5 | 6 1 3 2
      4 5 6 | 1 3 2
    1 4 5 6 | 3 2
  1 3 4 5 6 | 2
1 2 3 4 5 6 |

下面是实现代码

void insertionSort(int[] a) {
    if (a.length<2) return;
    
    for (int i = 1; i < a.length; i++) {
        // 当前元素比已处理序列最大值都大,直接放末尾
        if (a[i] >= a[i-1]) continue;
        
        //保持未处理序列首元素,避免覆盖
        int t = a[i];
        
        // 记录插入位置,i 是未处理序列头,i-1 是已处理序列尾
        int j = i-1;
        
        // 逆序遍历已处理序列,寻找合适插入位置,并将之后的元素后移
        for (; j>=0 && a[j]>t; j--)
                a[j+1] = a[j];
        
        // 插入到合适位置
        a[j+1] = t;
    }
}

稳定性

上述代码内部 for 循环的终止条件 a[j] > t 决定,当元素相等时,后出现的元素不会插入到前面,所以插入排序是 稳定 的排序算法。

性能分析

最好时间复杂度

当元素本身有序且为正序时,插入排序无须移动元素,时间复杂度为 O(n)。

最坏时间复杂度

当元素逆序时,每次插入都要移动已处理序列的所有元素,时间复杂度为 O(n^2)。

平均时间复杂度

当 i<j 时,若 a[i]<=a[j],则称 a[i] 与 a[j] 为一组有序元素对,有序度是数组中有序元素对的个数。逆序度的定义与有序度相反。对于完全有序的数组,称它的有序度为满有序度。对于含 n 个元素的数组,其满有序度为

$$ \begin{equation} \begin{aligned} FullOrderDegree &=(n-1) + (n-2) + ... + 1\\ &=\frac{n(n-1)}{2} \end{aligned} \end{equation} $$

满有序度=逆序度+有序度,排序就是增加有序度,减少逆序度的过程。插入排序包含两个操作,比较和移动,对于给定的初始序列,每次遍历已处理序列时,只有逆序才需要移动,每移动一个元素,逆序度都减 1,所以插入排序的移动次数等于初始序列的逆序度。

另一方面,插入排序本质是 n 次数组插入,数组插入的平均复杂度为 O(n),所以插入排序的平均时间复杂度就为 O(n^2)。

空间复杂度

算法使用了常数级的额外空间,所以最好最坏和平均空间复杂度都为 O(1)。

插入排序的优化

折半插入排序

因为已处理序列是有序的,因此可使用折半查找的方法寻找插入位置,这样可将比较次数降低到 O(nlogn)。下面是示例代码

void insertSort(int[] a) {
    if (a.length<2) return;
    // 遍历未处理序列
    for (int i=1; i<a.length; i++) {
        // 未处理序列首元素大于已处理序列尾元素,直接插入到末尾
        if (a[i] >= a[i-1]) continue;
        
        // 记录未处理序列首元素,避免移动元素覆盖
        int t = a[i];
        
        //  在已处理序列中通过二分搜索,找到最后一个大于 t 的位置
        //+ 因 low>high 才会退出循环, 所以退出前执行了 high = mid-1,
        //+ 这意味着 low=mid,a[mid]>t,所以 low 是最后一个大于 t 的位置
        int low = 0;
        int high = i-1;
        while (low <= high) {
            int mid = (low+high)/2;
            if (a[mid] > t)
                high = mid-1;
            else
                low = mid + 1;
        }
        
        // 逆序遍历已处理序列,移动元素
        for(int j=i-1; j>=low; j--)
            a[j+1] = a[j];
        
        // 插入到合适位置
        a[low] = t;
    }
}

希尔排序

直接插入排序的移动次数等于初始序列的逆序度,如果数据规模较小且初始序列基本有序,比较和移动次数就会显著降低。基于以上两点 D.L.Shell 于 1959 年发明了希尔排序,其基本思想是:把记录下标按一定增量分组,对每组使用直接插入排序;随着增量逐渐减少,每组包含的元素越来越多,当增量减至 1 时,整个文件恰被分成一组,再进行一次插入排序,整个序列便达到有序。

简单插入排序很循规蹈矩,不管数组分布是怎么样的,都一步一步地对元素进行比较,移动,插入。比如 [ 5, 4, 3, 2, 1, 0 ] 这种倒序序列,数组末端的 0 要回到首位很是费劲,比较和移动均需 n-1 次。希尔排序采用跳跃式分组策略,通过某个增量将数组元素划分为若干组,分组进行插入排序。处理完所有组后,减小增量,继续按组进行插入排序,直至增量为 1。通过这种策略使得整个数组在初始阶段达到宏观基本有序,到增量为1时,只需微调即可。

目前尚未求得一个最好的增量序列,希尔的做法是 d1=n/2, d(i+1)=⌊di/2⌋,且最后一个增量为 1。在理解希尔排序时,我们倾向于逐组处理,但在代码实现中,不用处理完一组再回去处理下一组(这样还得加个 for 循环去处理分组)。比如 [ 5, 4, 3, 2, 1, 0 ] ,首次增量设 d1=length/2=3,将序列分成 3 组 [ 5, 2 ] [ 4, 1 ] [ 3, 0 ],实现时不用循环按组处理,而是从第 d1 个元素开始逐个遍历,实现跨组处理。以下是示例代码

void shellSort(int[] a, int n) {
    if (n < 2) return;
    
    // 间距逐步减小,每组元素逐步增多,分组数逐步减少
    for (int dk=n/2; dk>=1; dk/=2) {
        //  逐个遍历,实现跨组处理
        //+ 随着 i++,dk 分别是第一组,第二组,... ,第 dk 组未处理序列的第  一  个元素,
        //+                   第一组,第二组,... ,第 dk 组未处理序列的第  二  个元素,
        //+ ...
        //+                   第一组,第二组,... ,第 dk 组未处理序列的第 n/dk 个元素。
        for (int i=dk; i<a.length; i++) {
            // 如果未处理序列开头比已处理序列最大值还大,直接放末尾
            if (a[i] >= a[i-dk]) continue;
            
            // 记录未处理组开头,避免覆盖
            int t = a[i];
            
            // 记录插入位置,i-dk 是已处理序列最后一个元素
            int j = i-dk;
            
            // 遍历已处理序列,将大元素后移
            for(; j>=0 && t<a[j]; j-=dk)
                a[j+dk] = a[j];
            
            // 插入到合适位置
            a[j+dk] = t;
        }
    }
}

此外除了一次性移动所有元素,也可采用将待插入元素逐个与大于它的元素交换的方法,以下是示例代码

void shellSort(int[] a, int n) {
    if (n < 2) return;
    
    for (int dk=n/2; dk>0; dk/=2) {
        for (int i=dk; i<a.length; i++) {
            if (a[i] >= a[i-dk]) continue;
            for (int j=i; j-dk>=0 && a[j]<a[j-dk]; j-=dk)
                swap(a, j, j-dk);
        }
    }
}

当相等元素被划分到不同组时,可能会改变它们的相对次序,所以希尔排序是 不稳定 的排序算法。下面的示例一目了然

3  2  2* 1  0  dk=5/2=2
^     ^     ^
0  1  2* 2  3
^     ^     ^

0  1  2* 2  3  dk=2/2=1

希尔排序的空间复杂度为 O(1),它的时间复杂度依赖于增量序列函数,这涉及到数学上尚未解决的难题,所以不便准确分析,当 n 在某个特定范围时,其时间复杂度约为 O(n^1.3),最坏情况下时间复杂度为 O(n^2)。希尔排序是冲破 O(n^2) 的第一批算法之一。

选择排序

基本思想

与插入排序类似,选择排序也将数组分为已排序和未排序区间,不同的是,选择排序每次从未排序区间选择最小元素后缀至已排序区间。因为并不关心未排序区间第一个元素 p 和最小元素 min 的顺序,并且 p 将在下一步进入已排序区间,所以后缀 min 的操作可以转换为交换 p 和 min,下面是一个示例

     sorted | unsorted
            | 4 5 6 3 2 1 swap 4 and 1
          1 | 5 6 3 2 4   swap 5 and 2
        1 2 | 6 3 5 4     swap 6 and 3
      1 2 3 | 6 5 4       swap 6 and 4
    1 2 3 4 | 5 6         swap 5 and 5
  1 2 3 4 5 | 6           swap 6 and 6
1 2 3 4 5 6 |

下面是实现代码

int selectionSort(int[] a) {
    for (int i=0; i<a.length; i++) {
        int min = a[i];
        int minIndex = i;
        for(int j=i+1; j<a.length; j++)
            if (a[j] < min) {
                min = a[j];
                minIndex = j;
            }
        swap(a, i, minIndex);
    }
}

稳定性

考虑序列 5,6,5,2,9,第一次找到的最小元素是 2,要将其与第一个 5 交换,这样就改变了两个 5 的顺序,所以选择排序 不具有稳定性

性能分析

时间复杂度

无论原始序列有序性如何,选择排序都要进行 n 次寻找最小值的操作,而寻找最小值的时间复杂度是 O(n),所以选择排序的最好最坏和平均时间复杂度都是 O(n^2)。

空间复杂度

算法使用了常数级空间,所以空间复杂度为 O(1)。

冒泡排序

基本思想

同样将数组分为已就绪和未就绪区间,初始状态整个数组都未就绪。遍历未就绪区间,比较相邻元素,若不满足大小关系则交换,一次遍历会至少让一个元素移动到它应该在的位置,重复 n-1 次就完成了排序工作。下面是一次冒泡过程

从小到大排序,if(a[j] > a[j+1]) 交换
4 5 6 3 2 1 , 4<5 不交换
j
4 5 6 3 2 1 , 5<6 不交换
  j
4 5 6 3 2 1 , 6>3   交换
    j
4 5 3 6 2 1 , 6>2   交换
      j
4 5 3 2 6 1 , 6>1   交换,结束
        j
首次冒泡后,整个数组的最大值到达最终位置,下次冒泡,次大值将到达最终位置
还可以看出,若某次冒泡,如果未就绪序列有 m 个元素,则要进行 m-1 次比较

某些情况下,排序操作不需要 n-1 次冒泡,因为如果某次冒泡没有发生数据交换,说明未就绪序列相邻元素全部满足大小关系,即未就绪序列实际上已经就绪,可停止后续冒泡,下面是示例代码

void bubbleSort(int[] a) {
    for (int i=0; i<a.length-1; i++) {
        boolean sorted = true;
        for (int j=0; j<a.length-i-1; j++) {
            if(a[j]>a[j+1]) {
                swap(a, j, j+1);
                sorted = false;
            }
        }
        if(sorted) break;
    }
}

稳定性

冒泡排序只交换相邻元素,对于非相邻相等元素,最终会因逐个交换而相邻,因此只要保证相等元素不交换,就可保证排序的稳定性。换句话说,冒泡排序是 稳定 的排序算法。

性能分析

最好时间复杂度

当元素和待排顺序相同时,只需一次冒泡,所以最好时间复杂度为 O(n)。

最坏时间复杂度

当元素逆序是,要进行 n-1 次冒泡,所以最坏时间复杂度为 O(n^2)。

平均时间复杂度

冒泡排序的两个基本操作是比较和交换。每进行一次交换,序列的有序度就加 1,所以冒泡排序的交换次数等于原始序列的逆序度。

对于包含 n 个元素的数组,最坏情况逆序度为 n(n-1)/2,最好情况逆序度为 0,粗略取中间值 n(n-1)/4 作为平均逆序度,则冒泡排序的平均交换次数为 n(n-1)/4,比较次数显然大于交换次数,而最坏时间复杂度为 O(n2),所以其平均时间复杂度为 O(n^2)。

空间复杂度

算法使用了常熟级额外空间,所以最好最坏和平均时间复杂度都是 O(1)。

堆排序

如果一棵二叉树的结点要么是叶子结点,要么该节点有两个子结点,那么这颗树就是满二叉树。完全二叉树是由满二叉树引申出来的。对于深度为 K 的,有 n 个结点的二叉树,当且仅当其每个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。也可以这样定义:设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大,第 h 层所有的结点都连续集中在最左边,这颗树就是完全二叉树。

堆 (Heap) 又被称为优先队列 (Priority Queue)。尽管名为优先队列,但它并不是队列。队列先进先出,而堆必须根据优先级取出元素。由完全二叉树 (Complete Binary Tree) 实现的堆称为二叉堆 (Binary Heap)。二叉堆是具有下列性质的完全二叉树:如果一颗完全二叉树每个节点的值都大于等于(小于等于)其左右孩子节点的值,则将这颗完全二叉树称为大顶堆或大根堆(小顶堆或小根堆)。堆的主要操作是添加最后一个节点和删除第一个节点,在插入或删除后,必须仍保持堆的性质: 1. 完全二叉树。2. 每个节点值都大于等于(小于等于)它的子节点。

插入新节点 new 时,将其放到最后一个节点之后,此时可能破坏堆的性质,要进行调整,具体操作为:将 new 与父节点比较,构建大根堆时,如果 new 节点比父节点大,那么交换两者。交换之后,继续与父节点比较,直到 new 节点不比父节点大,或者 new 节点成为根节点。下面是一次建立大根堆的过程

          53
      17      78
    09  45  65  87
    ↑
32

          53
      17      78
              ↑
    32  45  65  87
09

          53
      17      87
      ↑
    32  45  65  78
09

          53
          ↑
      45      87
    32  17  65  78
09

          87
      45      53
               ↑
    32  17  65  78
09

          87
      45      78
    32  17  65  53
09

堆只能删除根节点。根节点删除后,会得到两棵子树,需要基于它们重构堆:让最后一个节点 last 成为根构成新二叉树,再将 last 节点不断和子节点比较,构建大根堆时,如果 last 节点比两个子节点中大的那个小,则与该子节点交换。继续比较,直到 last 不小于任一子节点,或成为叶节点时,堆重构完成。堆排序(Heap Sort)便是利用堆设计的排序算法。

基本思想

堆排序是一种树形选择排序,其基本思想是:将待排数组构建成大根堆,不断删除堆顶(最大值)直到堆中仅含一个元素,排序完成。以下是示例代码

// 不使用 a[0],len 为无序区(堆)元素个数
void heapSort(int[] a, int len) {
    // 仅含一个元素,无需排序
    if (len < 3) return;
    
    // 建立大根堆,堆顶 a[1] 是最大值
    buildMaxHeap(a, len);
    
    // 不断处理无序区(删除堆顶),直到仅含一个元素
    while (len > 2) {
        // 将最大值移到有序区,堆元素减一
        swap(a, 1, len--);
        
        // 从根开始往下调整,使之成为新堆
        adjustDown(a, 1, len);
    }
}

void buildMaxHeap(int[] a, int len) {
    //  len/2 是最大非叶节点(对应最后一颗子树)
    //+ 建堆过程就是从最大非叶节点向上遍历,一直到根,
    //+ 在此过程中,在每个非叶节点处向下调整,使对应子树满足堆的性质
    for (int i=len/2; i>0; i--)
        adjustDown(a, i, len);
}

// 将元素 k 向下调整,使子树成为堆,len 为堆中节点数
void adjustDown(int[] a, int k, int len) {
    // 保存当前非叶节点
    a[0] = a[k];
    
    // 沿较大子节点向下筛选,从左子节点(2k)开始
    for (int i=2*k; i<=len; i<<1) {
        // 若右子节点大于左子节点,则 i 移动到右子节点
        if (i < len && a[i]<a[i+1])
            i++;
        
        //  若当前非叶节点大于左右子树,则已经
        //+ 满足堆的性质,无需继续向下调整
        if (a[0] >= a[i])
            break;
        else {
            // 否则将左右子节点的较大者上移
            a[k] = a[i];
            
            // 非叶节点下移
            k = i;
        }
    }
    
    // 将当前非叶节点放到合适位置,即第一次大于等于其子节点的位置,或最后一个叶子节点
    a[k] = a[0];
}

向下调整也可用递归实现,每次递归处理一层。

void adjustDown(int[] a, int k, int len) {
    int i = 2 * k;
    if (i + 1 <= len && a[i] < a[i + 1])
        i++;
    if (a[0] >= a[i])
        return;
    swap(a, k, i);
    adjustDown(a, i, len);
}

稳定性

在进行筛选时,有可能把后面相等的元素调整到前面,所以堆排序是 不稳定 的排序算法。下面是一个演示示例

待排序列 
1  2  2*

建立大根堆
   2
1     2*

删除堆顶,已排序列为 2
   2*
1

删除堆顶,已排序列为 2* 2
   1

堆中仅剩一个元素,排序结束,最终序列为
1  2*  2

性能分析

时间复杂度

记树高为 h,则向下调整时间为 O(h)。建堆过程中每次向下调整时,大部分节点高度都较小,可证明建堆时间为 O(n)。如下是证明方法:假设完全二叉树有 n 个节点,则

$$ \sum_{i=0}^{h-1}2^i<n<=\sum_{i=0}^{h}2^i $$

解得 h≈logn。建堆调整时,最后一层每个父节点最多需下调 1 次,共 2^(h-1) 个节点。倒数第二层每个父节点最多需下调 2 次,共 2^(h-2) 个节点。依次类推,顶点最多需下调 h 次,共 1 个节点。所以总共需下调的次数为

$$ \begin{equation} \begin{aligned} T(n) &=1*2^{h-1}+2*2^{h-2}+...+h*2^0\\ \end{aligned} \end{equation} $$

可利用错位相减法计算 T(n)

$$ \begin{equation} \begin{aligned} 2T(n) &=1*2^{h}+2*2^{h-1}+3*2^{h-2}+...+\ \ h\ \ \ *\ \ \ \ \ 2^1\\ T(n) &=\ \ \ \quad\quad\quad1*2^{h-1}+2*2^{h-2}+...+(h-1)*2^1+h*2^0\\ T(n) &=1*2^h+1*2^{h-1}+1*2^{h-2}+...+\ \ 1\ \ \ \ *\ \ \ \ \ 2^1-h*2^0\\ &=\frac{2(1-2^h)}{1-2}-h\\ &=2^{h+1}-2-h,\ h=logn\\ &=2n-2-logn \end{aligned} \end{equation} $$

所以建立大根堆的时间复杂度是 O(n)。建堆完成后还要进行 n-1 次向下调整,每次调整时间复杂度都是 O(h),所以堆排序的最好、最坏和平均时间复杂度都是 O(nlogn)。

空间复杂度

算法使用了常数级空间,所以堆排序的最好、最坏和平均空间复杂度都是 O(1)。

总结

 类别            算法               时间复杂度               空间复杂度        稳定性
                              平均    最好       最坏
               直接插入       O(n^2)   O(n)     O(n^2)         O(1)            稳定
插入排序        折半插入       O(n^2)  O(n)      O(n^2)         O(1)            稳定
               希尔排序      O(n^1.3)  O(n)     O(n^2)         O(1)          不稳定

选择排序        直接选择      O(n^2)   O(n^2)    O(n^2)         O(1)          不稳定
               树形选择      O(nlogn) O(nlogn)  O(nlogn)       O(1)          不稳定

交换排序        冒泡排序       O(n^2)    O(n)    O(n^2)        O(1)            稳定
               快速排序      O(nlogn) O(nlogn)  O(n^2)       O(logn)         不稳定

归并排序                     O(nlogn) O(nlogn)  O(nlogn)       O(n)            稳定

对于稳定性,当排序过程中有非相邻元素交换,便会导致元素相对次序颠倒。希尔排序对序列分组,存在交叉移动。直接选择将未处理序列第一个元素与最小值交换,属于非相邻交换。堆排序采用树形结构,对子树向下调整,子树元素序号不一定连续。快速排序与直接选择类似。

几种简单排序中,直接插入的移动次数及冒泡排序的交换次数等于初始序列的逆序数,但冒泡排序赋值语句多于直接插入,而直接选择的交换次数与初始序列状态无关,但少于直接插入。因此,当数据规模较小时 (n <= 50),若序列基本有序则选择直接插入,若元素对象比较复杂,且不考虑稳定性,为减少移动开销,因使用简单选择。

当数据规模较大时,不考虑稳定性,优选选择优化后的快速排序。因为快速排序和堆排序时间复杂度一致,虽然后者空间复杂度更低,但其有如下缺点:第一,堆排序访问数据的方式不如快排。快排的划分函数对数据是顺序访问的,而堆排序对数据是跳跃式访问的,这就不利于 CPU 缓存。第二,对于同一组数据,堆排序交换次数多余快排。因为快速排序数据交换的次数小于等于原始序列的逆序数。而归并排序无论是建堆还是删除堆顶都要向下调整,大多数情况下会导致逆序度增加。如果要选择稳定性算法,在内存充足的情况下,归并排序时间效率最高,内存紧张的情况下,使用希尔排序。

参考文献

最后编辑于: 2019 年 08 月 20 日