梳排序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
- #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;
- }
- }
- [root@localhost combSort]$ gcc -c combSort.c
- [root@localhost combSort]$ gcc -c main.c
- [root@localhost combSort]$ gcc -o main main.o combSort.o
- [root@localhost combSort]$ ./main
- input array length:
- 10
- get 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
相关推荐
IT之家 2020-03-11
graseed 2020-10-28
zbkyumlei 2020-10-12
SXIAOYI 2020-09-16
jinhao 2020-09-07
impress 2020-08-26
liuqipao 2020-07-07
淡风wisdon大大 2020-06-06
yoohsummer 2020-06-01
chenjia00 2020-05-29
baike 2020-05-19
扭来不叫牛奶 2020-05-08
hxmilyy 2020-05-11
黎豆子 2020-05-07
xiongweiwei00 2020-04-29
Cypress 2020-04-25
冰蝶 2020-04-20