前言
插入排序(insertion sort)的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的序列中，直到全部记录插入完成为止.
直接插入排序
基本思想
假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n].从i = 2起直到i = n 为止，依次将R[i]插入当前的有序区R[1..i - 1]中，生成含n个记录的有序区.
排序方法
将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i - 1, i - 2, ....,1)的关键字比较：
- 若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置
- 若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j + 1即为R[i]插入位置
关键字比R[i]的关键字大的记录均已后移，所以j + 1的位置已经腾空，只要将R[i]直接插入到此位置即可完成一趟直接插入排序
c语言实现代码
- #include <stdio.h>
- #include <stdlib.h>
- void insertSort(int *, int);
- int main()
- {
- int i, n;
- int num[10];
- while(scanf("%d", &n) != EOF)
- {
- //接收无序数据
- for(i = 0; i < n; i ++)
- {
- scanf("%d",num + i);
- }
- //快速排序
- insertSort(num, n);
- //打印输出
- for(i = 0; i < n; i ++)
- {
- printf("%d ",num[i]);
- }
- printf("\n");
- }
- return 0;
- }
- void insertSort(int *array, int len)
- {
- int i, j, temp;
- for(i = 1; i < len; i ++)
- {
- temp = array[i];
- for(j = i - 1; j >= 0; j --)
- {
- if(array[j] > temp)
- {
- array[j + 1] = array[j];
- }else
- {
- break;
- }
- }
- array[j + 1] = temp;
- }
- }
时间复杂度
当数组和要求排序的顺序相同时，为o(n)
当数组和要求排序的顺序相反时，为o(n * n)
平均时间复杂度为o(n * n)
**********************************************上面转载的好像不能正常运行，xima
#include "stdio.h"
#include "conio.h"
main()
{
int a[10],r[11];
int *p;
int i,j;
for(i=0;i<10;i++)
{
p=&a[i];
printf("please scan the NO: %d\n",i);
scanf("%d",p);
r[i+1]=a[i];
}
r[0]=1;
for(i=2;i<=10;i++)
{
r[0]=r[i];
j=i-1;
while(r[j]>r[0])
{
r[j+1]=r[j];
j--;
}
r[j+1]=r[0];
}
for(i=1;i<=10;i++) {p=&r[i];printf("form min to max the NO: %d value=%d\n",i,*p);}
getch();
}
#include "conio.h"
main()
{
int a[10],r[11];
int *p;
int i,j;
for(i=0;i<10;i++)
{
p=&a[i];
printf("please scan the NO: %d\n",i);
scanf("%d",p);
r[i+1]=a[i];
}
r[0]=1;
for(i=2;i<=10;i++)
{
r[0]=r[i];
j=i-1;
while(r[j]>r[0])
{
r[j+1]=r[j];
j--;
}
r[j+1]=r[0];
}
for(i=1;i<=10;i++) {p=&r[i];printf("form min to max the NO: %d value=%d\n",i,*p);}
getch();
}