梳排序Linux下c 实现

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

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

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

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

#include "combSort.h"void combSort(int *pArr, const int length){        bool swapped=true;        int i, tmp, gap=length;        while(gap > 1 || swapped)        {                swapped=false;                if(gap>1)                {                        gap /= SHRINK_FACTOR;                 }                i=0;                while(i+gap<length)                {                        if(*(pArr+i)>*(pArr+i+gap))                        {                                tmp = *(pArr+i);                                *(pArr+i) = *(pArr+i+gap);                                *(pArr+i+gap) = tmp;                                swapped=true;                        }                        i++;                }        }}

3、main头文件：main.h

#ifndef MAIN_H#define MAIN_H#define MAX_VALUE 1000#include <stdlib.h>#include <stdio.h>#include "combSort.h"int main(void);void initRandomArr(int * pArr, const int length);void showArr(const int *pArr, const int length);#endif

4、main源文件：main.c

#include "main.h"int main(void){        printf("input array length:\n");        int len;        scanf("%d", &len);        if(len < 1)        {                printf("array length must be larger %d \n", len);                return EXIT_FAILURE;        }        int arr[len];        initRandomArr(arr, len);        printf("get random array:\n");        showArr(arr, len);        combSort(arr, len);        printf("comb sort result:\n");        showArr(arr, len);        return EXIT_SUCCESS;}void showArr(const int *pArr, const int length){        int i=0;        while(i<length)        {                printf("%d ", *(pArr+i));                i++;        }        printf("\n");}void initRandomArr(int *pArr, const int length){        int i;        srand(time(0));        for(i=0;i<length;i++)        {                *(pArr+i) = rand()%MAX_VALUE;        }}

5、编译：

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

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

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

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