直接插入排序把待排序序列分为两个序列：一个有序序列和一个无序序列。每次排序时，取无序序列的第一个元素，从有序序列尾部向前扫描，比较有序序列的元素，并把该元素插入到有序序列的合适位置，使有序序列继续保持有序并增长。下面给出关键代码：
1、插入排序头文件：InsertSort.h
#ifndef INSERTSORT_H
#define INSERTSORT_H
extern void InsertSort(int *pArr, int length);
#endif
2、插入排序源文件：InsertSort.c
#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
#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
#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、编译：
[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，大致如下：
[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
插入排序最佳效率o(n)，最糟效率O(n²)，适用于排序小列表。若列表基本有序，则插入排序比冒泡、选择排序更有效率。
当前位置：
论坛首页 »
自由讨论区 »
Android, Python及开发编程讨论区
»
发起投票
技术讨论
加好友
发消息
2012-10-10 15:23:56 |
赞(
操作
