梳排序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

1. #include "combSort.h"
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"
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. }
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. }
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. }

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

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