雞尾酒排序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  

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. }  

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  

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. }  

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  

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