希尔排序Linux下C实现

希尔排序Linux下C实现

本次，我们谈论下希尔排序，希尔排序也叫递减增量排序算法。步长也是影响希尔排序的一个重要因素，我们这里主要用Marcin Ciura设计的步长。关键代码如下：

1、希尔排序头文件：shellSort.h

1. #ifndef SHELLSORT_H  
2.  
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