希爾排序Linux下C實現

本次，我們談論下希爾排序，希爾排序也叫遞減增量排序算法。步長也是影響希爾排序的一個重要因素，我們這裡主要用Marcin Ciura設計的步長。關鍵代碼如下：

1、希爾排序頭文件：shellSort.h

1. #ifndef SHELLSORT_H
3. #define SHELLSORT_H

• extern void shellSort(int * pArr, const int length);
• #endif

2、希爾排序源文件：shellSort.c

1. #include "shellSort.h"
2. void shellSort(int * pArr, const int length)
3. {
4. const int pInc[9]={1,4,10,23,57,132,301,701,1750};
5. int len=sizeof(pInc)/sizeof(int);
6. int i,k,j,tmp;
7. int inc;
8. k=0;
9. while(*(pInc+k)<length && k<=len)
10. {
11. k++;
12. }
13. while(--k>=0)
14. {
15. inc=*(pInc+k);
16. for(i=inc; i< length; i++)
17. {
18. tmp=*(pArr+i);
19. j=i;
20. while(j>=inc && *(pArr+j-inc)>tmp)
21. {
22. *(pArr+j)=*(pArr+j-inc);
23. j=j-inc;
24. }
25. *(pArr+j)=tmp;
26. }
27. }
28. }

3、main頭文件：main.h

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