什么是插入排序？
在插入排序法中，將檢查數(shù)組中的每個(gè)元素，將它插入排序中的元素的適當(dāng)位置，當(dāng)最后一個(gè)元素插入到它適當(dāng)?shù)奈恢脮r(shí)，這個(gè)數(shù)組就排好序了。例如，
假如我們要對(duì)一個(gè)有5個(gè)元素的數(shù)組進(jìn)行升序排列，假設(shè)第一個(gè)元素的值被假定為已排好序了，那么我們將第2個(gè)元素插入到已排序好的數(shù)組中的適當(dāng)位置上，使得數(shù)組應(yīng)該是排序好的。依次類推，將第3個(gè)插入到到已排序好的數(shù)組中的適當(dāng)位置，使得插入后數(shù)組仍然是排序好的，。。。。。。
下面是一個(gè)插入排序的Demo：
int tarArr[]=
{10,1,35,12,7,17,66,6,56,26};
int size = sizeof(tarArr)/sizeof(tarArr[0]);
void insertSort(void)
{
int i=0,j=0;
for(i=1;i<size;i++)
{
int nextValue = tarArr[i];
for(j=i-1;j>=0;j--)
{
if(nextValue<tarArr[j])
tarArr[j+1]=tarArr[j];
else
{
break;
}
}
tarArr[j+1]=nextValue;
}
}下面來(lái)介紹一下希爾排序：
希爾排序就是將要排序的數(shù)據(jù)先分成如果組，對(duì)每一組實(shí)行插入排序。
代碼如下：
int tarArr[]={10,1,35,12,7,17,66,6,56,26};
int size = sizeof(tarArr)/sizeof(tarArr[0]);
void shellSort(void)
{
int gap =0,i=0,j=0;
for(gap = size/2;gap>0;gap/=2)
{
for(i=gap;i<size;i+=gap)
{
int nextValue = tarArr[i];
for(j=i-gap;j>=0;j-=gap)
{
if(nextValue<tarArr[j])
tarArr[j+gap] = tarArr[j];
else
{
break;
}
}
tarArr[j+gap] = nextValue;
}
}
}