直接插入排序把待排序序列分為兩個序列：一個有序序列和一個無序序列。每次排序時，取無序序列的第一個元素，從有序序列尾部向前掃描，比較有序序列的元素，並把該元素插入到有序序列的合適位置，使有序序列繼續保持有序並增長。下面給出關鍵代碼：
1、插入排序頭文件：InsertSort.h
[plain]
#ifndef INSERTSORT_H
#define INSERTSORT_H
extern void InsertSort(int *pArr, int length);
#endif
#ifndef INSERTSORT_H
#define INSERTSORT_H
extern void InsertSort(int *pArr, int length);
#endif
2、插入排序源文件：InsertSort.c
[html]
#include "InsertSort.h"
void InsertSort(int *pArr, int length)
{
int i,j,tmp;
for(i=1; i<length; i++)
{
j=i-1;
tmp=*(pArr+i);
while(j>=0 && tmp < *(pArr+j))
{
*(pArr+j+1)=*(pArr+j);
j--;
}
if(j!=i-1)
{
*(pArr+j+1)=tmp;
}
}
}
#include "InsertSort.h"
void InsertSort(int *pArr, int length)
{
int i,j,tmp;
for(i=1; i<length; i++)
{
j=i-1;
tmp=*(pArr+i);
while(j>=0 && tmp < *(pArr+j))
{
*(pArr+j+1)=*(pArr+j);
j--;
}
if(j!=i-1)
{
*(pArr+j+1)=tmp;
}
}
}
3、main頭文件：main.h
[cpp]
#ifndef MAIN_H
#define MAIN_H
#include "InsertSort.h"
#include <stdio.h>
void outputArr(const int *pArr, const int length);
#endif
#ifndef MAIN_H
#define MAIN_H
#include "InsertSort.h"
#include <stdio.h>
void outputArr(const int *pArr, const int length);
#endif
4、main 源文件：main.c
[cpp]
#include "main.h"
int main(void)
{
printf("input array length:\n");
int length;
scanf("%d", &length);
if(length<=0)
{
printf("length must be larger 0\n");
return 1;
}
int i;
int arr[length];
for(i=0; i< length; i++)
{
printf("input arr[%d] value:\n", i);
scanf("%d", &arr[i]);
}
printf("arr orig:");
outputArr(arr, length);
InsertSort(arr, length);
printf("arr insert sort completed:");
outputArr(arr, length);
}
void outputArr(const int *pArr, const int length)
{
int i;
for(i=0; i<length; i++)
{
printf(" %d", *(pArr+i));
}
printf("\n");
}
#include "main.h"
int main(void)
{
printf("input array length:\n");
int length;
scanf("%d", &length);
if(length<=0)
{
printf("length must be larger 0\n");
return 1;
}
int i;
int arr[length];
for(i=0; i< length; i++)
{
printf("input arr[%d] value:\n", i);
scanf("%d", &arr[i]);
}
printf("arr orig:");
outputArr(arr, length);
InsertSort(arr, length);
printf("arr insert sort completed:");
outputArr(arr, length);
}
void outputArr(const int *pArr, const int length)
{
int i;
for(i=0; i<length; i++)
{
printf(" %d", *(pArr+i));
}
printf("\n");
}
4、編譯：
[cpp]
[root@localhost insertSort]$ gcc -c InsertSort.c
[root@localhost insertSort]$ gcc -c main.c
[root@localhost insertSort]$ gcc -o main InsertSort.o main.o
[root@localhost insertSort]$ gcc -c InsertSort.c
[root@localhost insertSort]$ gcc -c main.c
[root@localhost insertSort]$ gcc -o main InsertSort.o main.o
如果運氣不是非常壞，你將看到可執行文件main，執行main，大致如下：
[cpp]
[root@localhost insertSort]$ ./main
input array length:
5
input arr[0] value:
43
input arr[1] value:
65
input arr[2] value:
76
input arr[3] value:
1
input arr[4] value:
43
arr orig: 43 65 76 1 43
arr insert sort completed: 1 43 43 65 76
[root@localhost insertSort]$ ./main
input array length:
5
input arr[0] value:
43
input arr[1] value:
65
input arr[2] value:
76
input arr[3] value:
1
input arr[4] value:
43
arr orig: 43 65 76 1 43
arr insert sort completed: 1 43 43 65 76
