插入排序算法(4)
目录
-
插入排序算法原理
在插入排序中,需要将取出的数据与其左边的数字进行比较。就跟前面讲的步骤一样,如果左边的数字更小,就不需要继续比较,本轮操作到此结束,自然也不需要交换数字的位置。然而,如果取出的数字比左边已归位的数字都要小,就必须不停地比较大小,交换数字,直到它到达整个序列的最左边为止。具体来说,就是第k轮需要比较k-1次。因此,在最糟糕的情况下,第2轮需要操作1次,第3轮操作2次……第n轮操作n-1次,所以时间复杂度和冒泡排序的一样,都为O(n2)。和前面讲的排序算法一样,输入数据按从大到小的顺序排列时就是最糟糕的情况。
-
插入排序算法的使用场景
-
插入排序算法的实现
//描述:插入排序算法
//参数:@piArray 待排序的数组数据
// @iNum 数组个数
//返回:无
void InsertSort(int *piArray, int iNum)
{
int i, j, tmp;
char info[128];
Printf("Sort before:", piArray, iNum);
printf("\n\n");
for (i=1; i<iNum; i++)
{
for (j=0; j<i; j++)
{
if (piArray[i] > piArray[j]) //寻找最小值
{
tmp = piArray[i];
piArray[i] = piArray[j];
piArray[j] = tmp;
}
}
memset(info, 0, sizeof(info));
sprintf(info, "\nOrder number %02d:", i);
Printf(info, piArray, iNum);
}
printf("\n\n");
Printf("Sort after:", piArray, iNum);
}
int main(int argc, char *argv[])
{
int iArray[] ={10, 23, 65, -101, 999, 10000};
InsertSort(iArray, sizeof(iArray)/sizeof(iArray[0]));
system("pause");
return 0;
}
-
插入排序算法的运行结果