什么是插入排序?
在插入排序法中,将检查数组中的每个元素,将它插入排序中的元素的适当位置,当最后一个元素插入到它适当的位置时,这个数组就排好序了。例如,
假如我们要对一个有5个元素的数组进行升序排列,假设第一个元素的值被假定为已排好序了,那么我们将第2个元素插入到已排序好的数组中的适当位置上,使得数组应该是排序好的。依次类推,将第3个插入到到已排序好的数组中的适当位置,使得插入后数组仍然是排序好的,。。。。。。
下面是一个插入排序的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;
}
}
下面来介绍一下希尔排序:
希尔排序就是将要排序的数据先分成如果组,对每一组实行插入排序。
代码如下:
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;
}
}
}