梳排序Linux下C 实现

梳排序Linux下C 实现

梳排序改良自冒泡排序和快速排序，是不稳定排序算法。梳排序的递减率关系着算法的效率，递减率常常使用1.3，也有人提议用1.247330950103979。下面给出关键代码：

1、梳排序头文件： combSort.h

1. #ifndef COMBSORT_H   
2. #define COMBSORT_H   
3. #define SHRINK_FACTOR 1.3   
4. #include <stdbool.h>   
5. extern void combSort(int *pArr, const int length);  
6. #endif  

2、梳排序源文件：  combSort.c

1. #include "combSort.h"   
2.   
3. void combSort(int *pArr, const int length)  
4. {  
5.         bool swapped=true;  
6.         int i, tmp, gap=length;  
7.         while(gap > 1 || swapped)  
8.         {  
9.                 swapped=false;  
10.                 if(gap>1)  
11.                 {  
12.                         gap /= SHRINK_FACTOR;   
13.                 }  
14.                 i=0;  
15.                 while(i+gap<length)  
16.                 {  
17.                         if(*(pArr+i)>*(pArr+i+gap))  
18.                         {  
19.                                 tmp = *(pArr+i);  
20.                                 *(pArr+i) = *(pArr+i+gap);  
21.                                 *(pArr+i+gap) = tmp;  
22.                                 swapped=true;  
23.                         }  
24.                         i++;  
25.                 }  
26.         }  
27. }  

3、main头文件：main.h

1. #ifndef MAIN_H   
2. #define MAIN_H   
3. #define MAX_VALUE 1000   
4. #include <stdlib.h>   
5. #include <stdio.h>   
6. #include "combSort.h"   
7. int main(void);  
8. void initRandomArr(int * pArr, const int length);  
9. void showArr(const int *pArr, const int length);  
10. #endif  

4、main源文件：main.c

1. #include "main.h"   
2.   
3. int main(void)  
4. {  
5.         printf("input array length:\n");  
6.         int len;  
7.         scanf("%d", &len);  
8.         if(len < 1)  
9.         {  
10.                 printf("array length must be larger %d \n", len);  
11.                 return EXIT_FAILURE;  
12.         }  
13.         int arr[len];  
14.         initRandomArr(arr, len);  
15.         printf("get random array:\n");  
16.         showArr(arr, len);  
17.         combSort(arr, len);  
18.         printf("comb sort result:\n");  
19.         showArr(arr, len);  
20.         return EXIT_SUCCESS;  
21. }  
22.   
23. void showArr(const int *pArr, const int length)  
24. {  
25.         int i=0;  
26.         while(i<length)  
27.         {  
28.                 printf("%d ", *(pArr+i));  
29.                 i++;  
30.         }  
31.         printf("\n");  
32. }  
33.   
34. void initRandomArr(int *pArr, const int length)  
35. {  
36.         int i;  
37.         srand(time(0));  
38.         for(i=0;i<length;i++)  
39.         {  
40.                 *(pArr+i) = rand()%MAX_VALUE;  
41.         }  
42. }  

5、编译：

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

执行可执行文件main，大致如下：

1. [root@localhost combSort]$ ./main   
2. input array length:  
3. 10  
4. get random array:  
5. 767 740 68 436 307 343 72 314 863 790   
6. comb sort result:  
7. 68 72 307 314 343 436 740 767 790 863   

梳排序时间复杂度：O(nlog n)