本次,我們談論下希爾排序,希爾排序也叫遞減增量排序算法。步長也是影響希爾排序的一個重要因素,我們這裡主要用Marcin Ciura設計的步長。關鍵代碼如下:
1、希爾排序頭文件:shellSort.h
-
#ifndef SHELLSORT_H
-
- #define SHELLSORT_H
- extern void shellSort(int * pArr, const int length);
- #endif
2、希爾排序源文件:shellSort.c
- #include "shellSort.h"
- void shellSort(int * pArr, const int length)
- {
- const int pInc[9]={1,4,10,23,57,132,301,701,1750};
- int len=sizeof(pInc)/sizeof(int);
- int i,k,j,tmp;
- int inc;
- k=0;
- while(*(pInc+k)<length && k<=len)
- {
- k++;
- }
- while(--k>=0)
- {
- inc=*(pInc+k);
- for(i=inc; i< length; i++)
- {
- tmp=*(pArr+i);
- j=i;
- while(j>=inc && *(pArr+j-inc)>tmp)
- {
- *(pArr+j)=*(pArr+j-inc);
- j=j-inc;
- }
- *(pArr+j)=tmp;
- }
- }
- }
3、main頭文件:main.h
- #ifndef MAIN_H
- #define MAIN_H
- #include<stdio.h>
- #include "shellSort.h"
- int main(void);
- void showArr(const int *pArr, const int length);
- void initRandomArr(int *pArr, const int length);
- #endif