``排序算法之 ____ 希尔排序

写于: 2016年06月08日

昨晚没熬夜, 但是却硬生生地失眠了(@_@). 浑浑噩噩了一整个白天, 想着睡会, 又害怕今晚失眠 <(ToT)>.我是好人, 别这样 好不 ?

希尔排序是插入排序的改进版, 是... (写不下去了,今天到此over _{_})~~

.
.
.
.
.
.

原理

插入排序的改进版, 是基于插入排序的以下两点性质而提出的改进方法:

• 插入排序对几乎已经排好序的数据操作时, 效率很高,可以达到线性排序的效率.

• 但插入排序在每次往前插入时只能将数据移动一位, 效率比较低.

所以希尔排序的思想是:

• 先是取一个合适的gap＜n作为间隔, 将全部元素分为gap个子序列, 所有距离为gap的元素放入同一个子序列, 再对每个子序列进行直接插入排序;

• 缩小间隔gap, 例如去gap=ceil(gap/2), 重复上述子序列划分和排序.

• 直到, 最后gap=1时, 将所有元素放在同一个序列中进行插入排序为止.

性能

开始时, gap取值较大, 子序列中的元素较少, 排序速度快, 克服了直接排序的缺点; 其次, gap值逐渐变小后, 虽然子序列的元素逐渐变多, 但大多元素已基本有序, 所以继承了直接插入排序的优点, 能以近线性的速度排好序.

==代码==

#include <stdio.h>
void shell_sort(int arr[], int len) {
     for(int gap = len/2; gap > 0; gap /= 2) {
   for(int i = 0; i < len; i = i+gap) {
      int temp = arr[i];
      int j;
      for(j = i; j >= gap && temp < arr[j-gap]; j -= gap) {
         arr[j] = arr[j-gap];
      }
      arr[j] = temp;
   }
 }
}
int main() {
    int arr[] = {12, 34, 64, 23, 87, 54, 89, 45, 1, 3, 7, 5, 4, 2};
    shell_sort(arr, 15);
    for (int i = 0; i < 15; i++)
    printf("%d  ", arr[i]);
}

运行结果:

希尔排序的时间复杂度为O(N(logN)2), 没有快速排序算法快O(N(logN)), 但比O(N2)复杂度的算法快.

希尔排序不稳定.

==end==