C语言十大排序二-----希尔排序

• 希尔排序是插入排序的升级,它的元素交换次数更少,效率更高
• 希尔排序的思路
  1.希尔排序将一个数组按步长拆分成n个数组
  2.对每个数组进行插入排序
  3.将排好序的数组按照原来的索引合并,将步长减半,重复上述操作
  4.反复操作直到步长为0,此时插入排序结束以后数组就按照有序的方式排列

代码如下:

#include <stdio.h>

int main()
{
    int num[9] = {1,6,3,4,7,3,7,9,2};
    int len = sizeof(num) / sizeof(num[0]);
    //先计算步长,步长为数组长度的一半
    int gap = len / 2;
    //取出步长的元素进行插入排序
    do{
        for(int i = gap;i < len;i++){
            for(int j = i;j - gap >= 0;j -= gap){
                if(num[j] < num[j-gap]){
                    int temp = num[j];
                    num[j] = num[j-gap];
                    num[j-gap] = temp;
                }else{
                    break;
                }
            }
        }
        gap = gap / 2;
    }while(gap > 0);
    for(int i = 0;i < len;i++){
        printf("num[%i] = %i\n",i,num[i]);
    }
    return 0;
}