c语言实现插入排序
1、用c语言实现一个插入算法:
基本思路类似于摸牌思想,比如:我玩扑克,摸牌后习惯整理成从小到大的顺序,我将这么做:
(1)把第一张扑克拿到手
(2)抓第二张扑克,如果比第一张小,就把第一张往后挪,把第二张插入到第一张前面;反之,保持位置不变
(3)抓第三张扑克,如果比第二张小,就把第二张往后挪,再与第一张比,如果比第一张小,再把第一张往后挪,并且把第三章扑克插入到第一张前面
(4)抓第四张扑克,如果比第三张小,就把第三章往后挪,再与第二张比,如果没有第二张大,则把第四张扑克插入到第二张扑克后面,其实就是第三张扑克挪动之前的位置
。。。。。。。。。。。
重复以上步骤,直到摸完一把牌,此时,手里的牌是从小到大排列
2、具体实现代码如下:
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>
int * getArr(int count);
void main()
{
int count=10;
int * c;
c = getArr(count);
int i;
for (i=1;i<count;i++)
{
int j = i - 1;
int temp = c[i];
while (j>=0 && temp < c[j])
{
c[j+1] = c[j];
j--;
}
c[j+1] = temp;
}
for (i=0;i<count;i++)
{
printf("%5d\n", c[i]);
}
}
int * getArr(int count)
{
srand(time(NULL));
int i;
int a[count];
for (i=0;i<count;i++)
{
time_t t = rand()%count;
a[i] = t;
printf("%5d\n", a[i]);
}
printf("%s\n", "***************************************");
int * b = (int *)malloc(count*sizeof(int));
memcpy(b, a, count*sizeof(int));
return b;
}
3、说明:(1)自己要去理解这种算法的思路
(2)getArr用来获取一个随机数组
(3)循环中,i为0对应第一张扑克;i=1,插入第2张;i=2,插入第3张 ....以此类推
(4) c[j+1] = c[j];此为往后挪动
(5) j--;再与前一张扑克的大小进行比较
(6) c[j+1] = temp;插入的位置
(7)while (j>=0 && temp < c[j]),此为循环条件,也就是每次都有可能比到第一个元素
4、运行结果如下: