直接插入排序Linux下c 实现

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

       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