直接插入排序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²)，适用于排序小列表。若列表基本有序，则插入排序比冒泡、选择排序更有效率。

相关内容