鸡尾酒排序Linux下C 实现

鸡尾酒排序Linux下C 实现

很久很久以前，曾经写了篇文章：冒泡排序 Linux下C 实现 ，这次再show个冒泡排序的变种：鸡尾酒排序。 鸡尾酒排序在排序时，从两个方向在序列中排序。先找到最大的数字放到最后一位，然后找到最小的数字，放到第一位；然后再找到第二大的数字放到倒数第二位，再找到第二小的数字放到第二位。以此类推，直到完成排序。详细实现，请参阅下面的关键代码：

1、排序头文件：cocktailSort.h

1. #ifndef COCKTAILSORT_H   
2. #define COCKTAILSORT_H   
3. #include<stdbool.h>   
4. extern void cocktailSort(int * pArr, int length);  
5. #endif  

2、排序源文件：cocktailSort.c

1. #include "cocktailSort.h"  
2. void cocktailSort(int * pArr, int length)  
3. {  
4.         int bottom = 0;  
5.         int top = length-1;  
6.         bool swapped = true;  
7.         int tmp,i;  
8.         while(swapped)  
9.         {  
10.                 swapped = false;  
11.                 for(i=bottom; i<top; i++)  
12.                 {  
13.                         if(*(pArr+i)>*(pArr+i+1))  
14.                         {  
15.                                 swapped =true;  
16.                                 tmp = *(pArr+i);  
17.                                 *(pArr+i)=*(pArr+i+1);  
18.                                 *(pArr+i+1)=tmp;  
19.                         }  
20.                 }  
21.                 top--;  
22.                 for(i=top; i>bottom; i--)  
23.                 {  
24.                         if(*(pArr+i)<*(pArr+i-1))  
25.                         {  
26.                                 swapped = true;  
27.                                 tmp = *(pArr+i);  
28.                                 *(pArr+i)=*(pArr+i-1);  
29.                                 *(pArr+i-1)=tmp;  
30.                         }  
31.                 }  
32.                 bottom++;  
33.         }  
34. }  

3、main函数头文件：main.h

1. #ifndef MAIN_H   
2. #define MAIN_H   
3. #include<stdio.h>   
4. #include "cocktailSort.h"   
5. extern void outputArr(const int *pArr, int lenght);  
6. extern int main(void);  
7. #endif  

3、main函数源文件：main.c

1. #include "main.h"   
2. int main(void)  
3. {  
4.         printf("input array length:\n");  
5.         int length;  
6.         scanf("%d", &length);  
7.         if(length<0)  
8.         {  
9.                 printf("array length must be larger 0\n");  
10.                 return 1;  
11.         }  
12.         printf("array lenght is %d \n", length);  
13.   
14.         int arr[length];// ={1, 3, 6,5, 4};   
15.         int i=0;  
16.         for(i=0;i<length;i++)  
17.         {  
18.                 printf("input arr[%d] value\n",i);  
19.                 scanf("%d", &arr[i]);  
20.         }  
21.   
22.         printf("orig array:");  
23.         outputArr(arr, length);  
24.         cocktailSort(arr,length);  
25.   
26.         printf("cocktail sort array:");  
27.         outputArr(arr, length);  
28.         return 0;  
29. }  
30. void outputArr(const int *pArr, int length)  
31. {  
32.         int i;  
33.         for(i=0;i<length;i++)  
34.         {  
35.                 printf(" %d",*(pArr+i));  
36.         }  
37.         printf("\n");  
38. }  

4、Makefile文件：Makefile

1. all: main  
2. main: main.o cocktailSort.o   
3.         gcc -o main main.o cocktailSort.o  
4. main.o: main.c cocktailSort.c cocktailSort.h   
5.         gcc -c main.c  
6. cocktailSort.o: cocktailSort.c cocktailSort.h  
7.         gcc -c cocktailSort.c  
8. clean:  
9.         @echo "start cleaning"  
10.         -rm main *.o  
11.         @echo "clean completed"   
12. .PHONY: clean  

5、编译

1. make  

如果不出意外，可以看到可执行文件main。然后执行可执行文件，如下所示：

1. [root@localhost sort]$ ./main   
2. input array length:  
3. 5  
4. array lenght is 5   
5. input arr[0] value  
6. 34  
7. input arr[1] value  
8. 67  
9. input arr[2] value  
10. 89  
11. input arr[3] value  
12. 4  
13. input arr[4] value  
14. 3  
15. orig array: 34 67 89 4 3  
16. cocktail sort array: 3 4 34 67 89