您当前的位置： 首页 > 慢生活 > 程序人生 网站首页程序人生

c语言实现希尔排序算法

发布时间：2021-04-22 21:18:40编辑：雪饮阅读（）

 希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位
过程演示：

排序算法稳定性是什么？
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变.
即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
实例：
#include <stdio.h>
void main(){
    int arr[]={3,7,2,6,9,5,4,8};
    int gap, i, j;
    int len=8;
    int temp;
    //>>:二进制右移,一个二进制右移1位相当于将这个数除以2
    for (gap = len >> 1; gap > 0; gap = gap >> 1){
        //在当前区间内进行直接插入排序（插入排序也称直接插入排序）
        for (i = gap; i < len; i++) {
            temp = arr[i];
            /*
            j -= gap：不像直接插入排序那样一次只向左走一步进行对比交换，这里每次走gap步
            随着外部循环导致分组越来越多，每个gap越来越小（开始走碎步）
            */
            for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap){
                //大数向右边推，与插入排序中arr[j] = arr[j-1];是同样的道理
                 arr[j + gap] = arr[j];
            }
            //上面循环结束后最后一个不大于temp的地方j的右边就是temp应该放置的地方，所以temp最后要放置的地方就是j+gap(当前组步长为gap)
            arr[j + gap] = temp;
        }
    }
    //输出
    for(int x=0;x<len;x++){
        printf("%d\n",arr[x]);
    }
}
其实这个希尔排序算法是建立于插入排序算法之上的，其核心原理只不过是不断的分组，刚开始分的每个组都是很大的，比如只分两个组，那么每个组内就是走大步（j-=gap），等后面不断的向下细分，则每个组就会越来越小，慢慢的就趋向走碎步了。
有时候只看图，反而看不懂，这个时候看下代码以及相关概念原理之类的资料反而能懂了。