希尔排序

转自:https://www.cnblogs.com/ronnydm/p/5905715.html

希尔排序(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…}该序列中的项或者是94^i - 92^i + 1或者是4^i - 3*2^i + 1。使用不同的增量对希尔排序的时间复杂度的改进将不一样,甚至一点小的改变都将引起算法性能剧烈的改变。

优劣:
  1. 不需要大量的辅助空间,和归并排序一样容易实现。
  2. 希尔排序的时间复杂度与增量序列的选取有关,例如希尔增量时间复杂度为O(n²),而Hibbard增量的希尔排序的时间复杂度为O(),希尔排序时间复杂度的下界是n*log2n。
  3. 希尔排序没有快速排序算法快 O(n(logn)),因此中等大小规模表现良好,对规模非常大的数据排序不是最优选择。
  4. 希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,而快速排序在最坏的情况下执行的效率会非常差。
代码 :

#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));
}
原文链接:加载失败,请重新获取