- 希爾排序是插入排序的升級(jí),它的元素交換次數(shù)更少,效率更高
- 希爾排序的思路
1.希爾排序?qū)⒁粋€(gè)數(shù)組按步長(zhǎng)拆分成n個(gè)數(shù)組
2.對(duì)每個(gè)數(shù)組進(jìn)行插入排序
3.將排好序的數(shù)組按照原來(lái)的索引合并,將步長(zhǎng)減半,重復(fù)上述操作
4.反復(fù)操作直到步長(zhǎng)為0,此時(shí)插入排序結(jié)束以后數(shù)組就按照有序的方式排列
代碼如下:
#include <stdio.h>
int main()
{
int num[9] = {1,6,3,4,7,3,7,9,2};
int len = sizeof(num) / sizeof(num[0]);
//先計(jì)算步長(zhǎng),步長(zhǎng)為數(shù)組長(zhǎng)度的一半
int gap = len / 2;
//取出步長(zhǎng)的元素進(jìn)行插入排序
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;
}
