直接插入排序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"
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"
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);
26. }
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²)，適用於排序小列表。若列表基本有序，則插入排序比冒泡、選擇排序更有效率。