C语言插入排序 | Eternal_zttz

C语言插入排序

插入排序:插入排序算法就如同它的名字,依次在有序数组中插入待排数据,直到所有的元素都已排好序,其基本思路如下:

  1. 将第一个元素看成有序数组的首位,其余元素看成待排数据
  2. 将第二个元素与第一个元素比较,如果比第一个元素小,则第一个元素后移,然后将第二个元素放在因为后移空出的位置上,此时有序数组中有两个元素
  3. 依次重复该过程,将第i个数据与前1···i-1个有序数据比较,如果比其小,则元素后移,直到遇到一个不小于改元素的值,然后将该元素放在空出的位置上
    插入排序的时间复杂度为O(n^2),不过,在数据量很小的时候(一般不超过100),插入排序有着十分迅速的运行速率。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <stdio.h>
#define SWAP(a,b) {int t = a;a =b;b =t;}
void insertSort(int a[],int n);
int main(){
int n,i;
scanf("%d",&n);
int num[n];
for (i =0 ;i<n;i++)
scanf("%d",&num[i]);
insertSort(num,n);
for (i =0 ;i<n;i++)
printf("%d ",num[i] );
return 0;
}
void insertSort(int a[],int n){
int i,j,flag;
for (i = 0;i<n;i++){
flag = a[i];
for (j =i-1;j>=0;j--){
if(flag<a[j]){
SWAP(a[j], a[j+1]);
}
else
break;
}
}
}

程序输入:

1
2
9
1 5 6 8 4 3 2 9 15

程序输出:

1
1 2 3 4 5 6 8 9 15


-------------The End-------------