写于: 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==
