常见的排序算法

排序算法 (3)

插入类排序法

• 插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

插入排序一般意义上有两种：直接插入排序和希尔排序，下面分别介绍

希尔排序

• 希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

基本概念：

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。 所有距离为dl的倍数的记录放在同一个组中。 先在各组内进行直接插人排序，然后，取第二个增量d2<d1重复上述的分组和排序， 直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即 所有记录放在同一组中进行直接插入排序为止。

• 该方法实质上是一种分组插入方法。

例子：

例如，假设有这样一组数 [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我们以步长为5开始进行排序，我们可以通过将这列表放在有5列的表中来更好地描述算法，这样他们就应该看起来是这样：

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序：

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字，依序接在一起时我们得到： [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. 这时10已经移至正确位置了，然后再以3为步长进行排序

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为：

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步长进行排序（此时就是简单的插入排序了）。

C 实现：

    void shellsort(int *data, size_t size)
    {
       for (int gap = size / 2; gap > 0; gap /= 2)
          for (int i = gap; i < size; ++i)
          {
             int key = data[i];
             int j = 0;
             for( j = i -gap; j >= 0 && data[j] > key; j -=gap)
             {
                data[j+gap] = data[j];
              }  
             data[j+gap] = key;
         }
    }

性能分析

希尔排序是按照不同步长对元素进行插入排序， 当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快； 当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。 所以，希尔排序的时间复杂度会比o(n^2)好一些。 由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序， 但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性 就会被打乱，所以shell排序是不稳定的。

LINK

sort - 4