------------------------------------------
本文为本人原创，欢迎转载!
雪夜流星
------------------------------------------
2.直接插入排序算法是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。实现代码和测试程序如下：
#include
#include
/*****************************************************************
*功能描述：直接插入排序算法
*传入参数：num：需要排序的数组首地址， n:数组的元素
*传出参数：num：排序后的数组首地址，传入参数和传出参数空间复用，降低空间复杂度
*返回值： 无
****************************************************************/
void insert_sort(int *num, int n)
{
int tmp, i, j;
/*判断参数的合法性，当指针为空或者数组中只有一个元素时，直接返回*/
if((num == NULL) || (n<2))
{
return;
}
/*把数组中的第一个元素当成是一个有序表，逐个将后面的元素插入到该表中；当n=1时
数组中只有一个元素，直接返回；数组索引从0开始取，为避免数组越界，i最大值只能取 n-1*/
for (i=1; i
{
/*num[0...i-1]是有序表；如果num[i]比有序表中最后一个元素（即最大的元
素）要小，则将num[i]放到临时变量
并将有序表的最后一个元素往后移一位腾出 一个空间便于后续插入；否则直接将num[i]并入有序表尾*/
if (num[i] < num[i-1])
{
tmp = num[i];
num[i] = num[i-1];
/*继续跟有序表中前面的元素比较，遍历整个有序表，直到找到插入的
位置或者到j<0(即比有序表中的任何元素
都要小，可以插到有序表表 头)为止；当满足循环中的条件时，有序表中的元素依次往后移一个位 置*/
for (j=i-2; ((tmp=0)); j--)
{
num[j+1] = num[j];
}
num[j+1] = tmp;//将待插入元素插入到合适的位置(注意：因循环中 //的第三个条件为j--，插入位置为j+1)
}
}
return;
}
int main(void)
{
int i;
int num[5] = {5, 4, 3, 2, 1};
printf("before:\n");
for(i=0; i<5; i++)
{
printf("num[%d]:%d\n", i, num[i]);
}
insert_sort(num, 5);
printf("after:\n");
for(i=0; i<5; i++)
{
printf("num[%d]:%d\n", i, num[i]);
}
return 0;
}
阅读(1098) | 评论(1) | 转发(1) |
