2-1 Elementary Sort

发表于   |   分类于

在所有的排序算法实现中，只使用比较（Compare）和交换（exchange）两种函数操作。考虑算法的时间复杂度时，也只考虑这两种操作（如果没有交换操作，则考虑数组访问（array access）的代价）；考虑空间复杂度时，需考虑排序算法是在原处修改还是新建了一个数组来存储排序结果。

有时候，我们在比较时，只需要比较每个元素的某个特征来对他们排序（以人为元素，我们可能只比较身高，而不比较他们的其他特征）。以下为求简介，统一称为“比较元素”

选择排序（Selection Sort）

算法内容：

  • 首先，找到数组中最小的元素，将它与第一个元素交换（如果就是第一个元素，则不用交换）
  • 然后，在剩下 N-1 个元素中找出最小的，将它与第二个元素交换
  • 重复这个步骤，直到整个数组排序完成

    选择排序得名于它不断地从剩下的元素中选择出最小的一个

————————————————————————

排序一个大小为 N 的数组，选择排序使用了 ~N2/2 次比较操作和 N 次交换操作

————————————————————————

算法特点：

  • 运行时间对输入内容不敏感：

    一次查找最小元素的过程不会给下一次查找提供任何有用的信息。所以，排序一个已排序数组所需时间甚至和排序一个乱序数组所需时间是差不多的。

  • 最小化的元素移动：

    选择排序使用了 N 次的交换操作，所以对数组的访问次数与数组大小是线性关系（任何其他排序算法都没有这个特性，大多数都是随 N 类线性 ( linearithmic ) 增长或平方级 ( quadratic ) 增长）

插入排序（Insertion Sort）

插入排序类似于我们整理手中扑克牌时使用的算法

算法内容：

  • 从左到右扫描数组，对于每个元素，将它与它左边的所有元素依次进行比较：

    如果小于左边的元素，则交换两个元素，继续向左比较

    如果大于左边的元素或到达数组最左端，则停止比较，扫描下一个元素

————————————————————————

排序一个大小为 N 的数组（数组元素互异），插入排序平均使用了 ~N2/4 次比较操作和 ~N2/4 次交换操作。最差的情况是 ~N2/4 次比较操作和 ~N2/4 次交换操作 ，最好的情况是 N-1 次比较操作和 0 次交换操作

————————————————————————

Inversion 指的是数组中一对位置错误的元素。比如，在数组（1，3，5，2）中，有 2 个 Inversion ：（3，2），（5，2）。

如果一个数组中的 Inversion 数少于数组大小的常数倍，则称之为部分良序数组（Partially Sorted Array）。以下是几种常见的部分良序数组：

  • 数组中的每个元素和它的最终位置相距不远
  • 一个小数组附加在一个已经排好序的大数组后面
  • 一个数组只有很少的元素不在合适的位置

插入排序对这种部分良序数组（Inversion 数很少）具有优良的性能，甚至优于其他任何排序算法。在实际应用中，很多时候都是部分良序数组，所以插入排序表现很好。插入排序也适合适合小规模数组的排序。

————————————————————————

插入排序使用交换操作的次数与数组中Inversion的数量相等，而比较操作的次数至少等于Inversion的数量，至多等于Inversion数量加上 N-1

————————————————————————

希尔排序（Shell Sort）

希尔排序是对插入排序的一种改进

对于比较大的乱序序列，插入排序的劣势体现在它每次只能将一个元素与它旁边的元素交换，即一次只能移动一个位置。如果较小的元素恰好出现在序列尾端，则仅为这一个元素就需要移动 ~ N 次。希尔排序的思想是通过一次移动的距离大一些，来使元素尽快到达它应该在的位置附近。

首先，确定一个 h 值递减的规律和初始的 h 值。希尔排序每次从序列中每隔 h 个取一个元素，形成一个新的序列，用插入排序对其进行排序。然后，按照规律递减 h ，直到 h 减为 1 ，即进行最后一次（整个序列的）插入排序，得到有序的结果。

下面是希尔排序的 python 实现（取元素和插入排序两步糅合到一起了；下降规律为 1/2(3k-1)，h 的初始值为小于 N 的最大可能值）

def sort(Sequence a):
    N = len(a)
    h = 1
    while h < N//3:
        h = 3*h + 1      # 1, 4, 13, 40, 121, 364, ...
    while h >= 1:
        for i in range(h, N):
            j = i
            # Insert a[i] among a[i-h], a[i-2*h], ...
            while j >= h  and  less(a[j], a[j-h]):   # less function is used to compare
                exch(a, j, j-h)  # to exchange elements
                j -= h
        h = h//3

希尔排序的一个例子

_input_ s h e l l s o r t e x a m p l e
_13-sort_ p h e l l s o r t e x a m s l e
_13-sort_ p h e l l s o r t e x a m s l e
_13-sort_ p h e l l s o r t e x a m s l e
_4-sort_ l h e l p s o r t e x a m s l e
_4-sort_ l h e l p s o r t e x a m s l e
_4-sort_ l h e l p s o r t e x a m s l e
_4-sort_ l h e l p s o r t e x a m s l e
_4-sort_ l h e l p s o r t e x a m s l e
_4-sort_ l e e l p h o r t s x a m s l e
_4-sort_ l e e l p h o r t s x a m s l e
_4-sort_ l e e a p h o l t s x r m s l e
_4-sort_ l e e a m h o l p s x r t s l e
_4-sort_ l e e a m h o l p s x r t s l e
_4-sort_ l e e a m h l l p s o r t s x e
_4-sort_ l e e a m h l e p s o l t s x r
_1-sort_ e l e a m h l e p s o l t s x r
_1-sort_ e e l a m h l e p s o l t s x r
_1-sort_ a e e l m h l e p s o l t s x r
_1-sort_ a e e l m h l e p s o l t s x r
_1-sort_ a e e h l m l e p s o l t s x r
_1-sort_ a e e h l l m e p s o l t s x r
_1-sort_ a e e e h l l m p s o l t s x r
_1-sort_ a e e e h l l m p s o l t s x r
_1-sort_ a e e e h l l m p s o l t s x r
_1-sort_ a e e e h l l m o p s l t s x r
_1-sort_ a e e e h l l l m o p s t s x r
_1-sort_ a e e e h l l l m o p s t s x r
_1-sort_ a e e e h l l l m o p s s t x r
_1-sort_ a e e e h l l l m o p s s t x r
_1-sort_ a e e e h l l l m o p r s s t x
_result_ a e e e h l l l m o p r s s t x

希尔排序对处理大规模序列很有用，比插入排序有显著的性能提升，构造一个使希尔排序运行缓慢的序列是一个很大的挑战。然而，寻找一个优于其他的 h 递减函数依然是一个研究课题。在实际中，运用上面代码中或其他简单的递减函数往往已经可以得到一个不错的效率。