首页 > 代码库 > 排序五：希尔排序
排序五：希尔排序
希尔排序（Shell Sort）也是插入排序的一种。也称为缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。
基本思想：
将待排序列划分为若干组，在每一组内进行插入排序，以使整个序列基本有序，然后再对整个序列进行插入排。
再从百度上贴个示例：
希尔增量：
希尔增量是指希尔提出了一种冲破二次时间屏障的算法。
Donald Shell 提出了一种冲破二次时间屏障的算法Shellsort（希尔排序），在希尔排序中希尔给出了一组增量序列：ht = N / 2, h[k] = h[k+1] / 2，即 {N/2, (N / 2)/2, ..., 1}，这个序列就叫做希尔增量。这个是编写希尔排序时最常用的序列，但却不是最好的。其余的增量序列还有Hibbard：{1, 3, ..., 2^k-1}，Sedgewick：{1, 5, 19, 41, 109...}该序列中的项或者是9*4^i - 9*2^i + 1或者是4^i - 3*2^i + 1。使用不同的增量对希尔排序的时间复杂度的改进将不一样，甚至一点小的改变都将引起算法性能剧烈的改变。
优劣：
1. 不需要大量的辅助空间，和归并排序一样容易实现。
2. 希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n²)，而Hibbard增量的希尔排序的时间复杂度为O(
)，希尔排序时间复杂度的下界是n*log2n。
3. 希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。
4. 希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，而快速排序在最坏的情况下执行的效率会非常差。
代码1 ：
#include <stdio.h>void println(int array[], int len){ int i = 0; for(i=0; i<len; i++) { printf("%d ", array[i]); } printf("\n");}void swap(int array[], int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp;}void ShellSort(int array[], int len) // O(n*n){ int i = 0; int j = 0; int k = -1; int temp = -1; int gap = len; do { gap = gap / 3 + 1; for (i=gap; i<len; i+=gap) { k = i; temp = array[k]; for (j=i-gap; (j>=0) && (array[j]>temp); j-=gap) { array[j+gap] = array[j]; k = j; } array[k] = temp; } } while (gap > 1);}int main(){ int array[] = {21, 25, 49, 25, 16, 8}; int len = sizeof(array) / sizeof(*array); println(array, len); ShellSort(array, len); println(array, len); return 0;}
#include<stdio.h>#include<math.h> #define MAXNUM 10 void main(){ void shellSort(int array[],int n,int t);//t为排序趟数 int array[MAXNUM], i; for (i=0; i<MAXNUM; i++) scanf("%d",&array[i]); shellSort(array, MAXNUM, int(log(MAXNUM+1)/log(2)));//排序趟数应为log2(n+1)的整数部分 for(i=0;i<MAXNUM;i++) printf("%d ",array[i]); printf("\n");} //根据当前增量进行插入排序void shellInsert(int array[],int n,int dk){ int i,j,temp; for (i=dk; i<n; i++) { //分别向每组的有序区域插入 temp = array[i]; for(j=i-dk; (j>=i%dk) && array[j]>temp ;j-=dk)//比较与记录后移同时进行 array[j+dk]=array[j]; if(j!=i-dk) array[j+dk]=temp;//插入 }} //计算Hibbard增量int dkHibbard(int t,int k){ return int(pow(2,t-k+1)-1);} //希尔排序void shellSort(int array[],int n,int t){ void shellInsert(int array[],int n,int dk); int i; for(i=1;i<=t;i++) shellInsert(array,n,dkHibbard(t,i));}
排序五：希尔排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。