直接插入排序Linux下C 實現

直接插入排序把待排序序列分為兩個序列：一個有序序列和一個無序序列。每次排序時，取無序序列的第一個元素，從有序序列尾部向前掃描，比較有序序列的元素，並把該元素插入到有序序列的合適位置，使有序序列繼續保持有序並增長。下面給出關鍵代碼：

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

1. #ifndef INSERTSORT_H  
2. #define INSERTSORT_H  
3. extern void InsertSort(int *pArr, int length);  
4. #endif  

2、插入排序源文件：InsertSort.c

1. #include "InsertSort.h"  
2.   
3. void InsertSort(int *pArr, int length)  
4. {  
5.         int i,j,tmp;  
6.         for(i=1; i<length; i++)  
7.         {  
8.                 j=i-1;  
9.                 tmp=*(pArr+i);  
10.                 while(j>=0 && tmp < *(pArr+j))  
11.                 {  
12.                         *(pArr+j+1)=*(pArr+j);  
13.                         j--;  
14.                 }  
15.                 if(j!=i-1)  
16.                 {  
17.                         *(pArr+j+1)=tmp;  
18.                 }  
19.         }  
20. }  

3、main頭文件：main.h

1. #ifndef MAIN_H   
2. #define MAIN_H   
3. #include "InsertSort.h"   
4. #include <stdio.h>   
5. void outputArr(const int *pArr, const int length);  
6. #endif  

4、main 源文件：main.c

1. #include "main.h"   
2.   
3. int main(void)  
4. {  
5.         printf("input array length:\n");  
6.         int length;  
7.         scanf("%d", &length);  
8.         if(length<=0)  
9.         {  
10.                 printf("length must be larger 0\n");  
11.                 return 1;  
12.         }  
13.         int i;  
14.         int arr[length];  
15.         for(i=0; i< length; i++)  
16.         {  
17.                 printf("input arr[%d] value:\n", i);  
18.                 scanf("%d", &arr[i]);  
19.         }  
20.         printf("arr orig:");  
21.         outputArr(arr, length);  
22.         InsertSort(arr, length);  
23.         printf("arr insert sort completed:");  
24.         outputArr(arr, length);  
25.   
26. }  
27.   
28. void outputArr(const int *pArr, const int length)  
29. {  
30.         int i;  
31.         for(i=0; i<length; i++)  
32.         {  
33.                 printf(" %d", *(pArr+i));  
34.         }  
35.         printf("\n");  
36. }  

4、編譯：

1. [root@localhost insertSort]$ gcc -c InsertSort.c  
2. [root@localhost insertSort]$ gcc -c main.c  
3. [root@localhost insertSort]$ gcc -o main InsertSort.o main.o  

如果運氣不是非常壞，你將看到可執行文件main，執行main，大致如下：

1. [root@localhost insertSort]$ ./main   
2. input array length:  
3. 5  
4. input arr[0] value:  
5. 43  
6. input arr[1] value:  
7. 65  
8. input arr[2] value:  
9. 76  
10. input arr[3] value:  
11. 1  
12. input arr[4] value:  
13. 43  
14. arr orig: 43 65 76 1 43  
15. arr insert sort completed: 1 43 43 65 76  

插入排序最佳效率o(n)，最糟效率O(n²)，適用於排序小列表。若列表基本有序，則插入排序比冒泡、選擇排序更有效率。