- 希尔排序是插入排序的升级,它的元素交换次数更少,效率更高
- 希尔排序的思路
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;
}
