直接插入排序Linux下c 实现

直接插入排序把待排序序列分为两个序列：一个有序序列和一个无序序列。每次排序时，取无序序列的第一个元素，从有序序列尾部向前扫描，比较有序序列的元素，并把该元素插入到有序序列的合适位置，使有序序列继续保持有序并增长。下面给出关键代码：

1、插入排序头文件：InsertSort.h

#ifndef INSERTSORT_H#define INSERTSORT_Hextern 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:5input arr[0] value:43input arr[1] value:65input arr[2] value:76input arr[3] value:1input arr[4] value:43arr orig: 43 65 76 1 43arr insert sort completed: 1 43 43 65 76