1、基本思想
希尔排序也称缩小增量排序,是插入排序的一种更高效的改进版本。它的基本思想是先将待排序的数组元素按照一定的间隔(称为增量)分成若干个子序列,分别对这些子序列进行插入排序,随着迭代的进行,逐渐减小这个间隔,直到最后间隔为1时,对整个数组进行一次插入排序。通过这种方式,让元素能够在相对较远的位置上快速移动到大致合适的位置,使得后续在间隔较小的插入排序时,元素的移动次数减少,从而提高排序效率。
2、算法步骤
2.1、算法步骤描述:
1.根据实际情况选择增量序列,增量序列的形式为h1,h2,h3……hn,序列满足h1>h2>h3>……>hn=1,通常h1=N/2,N为待排序数组的长度,常见的增量选取可以按照hi+1=hi/2,也可以按照实际进行其他选择。
2.根据当前增量将待排序数组分成若干个子序列,每个子序列同等位置的间隔为hi 。例:以数组a[10]={a0,a1,a2,a3,a4,a5,a6,a7,a8,a9},以h1=N/2,hi+1=hi/2进行增量选取,那么第一轮划分中,增量为5,数组arr将被分成如下两个子序列:{a[0],a[5]},{a[1],a[6]},{a[2],a[7]},{a[3],a[8]},{a[4],a[9]}。第二轮划分中,增量为2,数组arr将被分成如下序列:{a[0],a[2],a[4],a[6],a[8]},{a[1],a[3],a[5],a[7],a[9]},增量为1时进行最后一次划分……
3、对于步骤2中每一轮划分得到的子序列,每个子序列分别进行插入排序。插入排序的过程就是在子序列中,将每个元素与其前面已排好序的元素依次比较并移动到合适位置,使得子序列有序。
4、当增量减小到1时,对整个数组进行最后一次插入排序,此时数组就完成了排序。
2.2、希尔排序算法动态演示图:
3、代码实现
c语言代码实现如下:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10
void sort(int arr[])
{int gap = N;while(gap != 1){gap = gap/2; //确定本轮排序增量for(int i = 0; i < gap; i++)//增量决定这一轮进行插入排序的次数{for(int j = i; j + gap < N ;j = j + gap)//对根据增量分成的其中一组进行插入排序{int end = j;//重置本轮扫描位置int insert = arr[end+gap];//本轮要插入的数据while(insert < arr[end] && end >= i){arr[end+gap] = arr[end];//移动end = end - gap;//改变下次开始扫描位置}arr[end+gap] = insert;//插入}}}}
int main(int argc, char *argv[])
{srand(time(NULL));int a[N];int i;puts("排序前数组为:");for(i = 0; i < N; i++){a[i] = rand()%100;//为数组随机赋值printf("%d ",a[i]);//输出排序之前数组值}puts("");sort(a);//排序puts("排序后的数组为:");for(i = 0; i < N; i++){printf("%d ",a[i]);//输出排序之后的数组值}puts("");return 0;
}
4、时间复杂度和空间复杂度
希尔排序的时间复杂度与所选择的增量序列密切相关。
平均时间复杂度:O(n^1.3)到O(n^1.5)之间,具体取决于增量序列的选择。
空间复杂度:希尔排序是一种原地排序算法,空间复杂度为O(1)。
稳定性:希尔排序是不稳定的排序算法。在排序过程中,由于相同元素可能在不同的子序列中移动,并且在最后一次整体插入排序时,它们的相对顺序可能会发生改变。
5、适用情况
1、当数据规模不是特别大,且对空间复杂度有一定要求的情况下。
2、由于其实现相对简单,在一些对排序速度要求不是极高、且数据的分布情况不太明确的场景下,也可以考虑使用希尔排序。