雞尾酒排序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);
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. }
22. printf("orig array:");
23. outputArr(arr, length);
24. cocktailSort(arr,length);
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