鸡尾酒排序算法

影-死神

一. 鸡尾酒排序与冒泡排序
        鸡尾酒排序是冒泡排序的优化。
        鸡尾酒排序与冒泡排序不同之处在于，冒泡排序是单向的，鸡尾酒排序是双向的。
        鸡尾酒排序是第一轮从左到右，第二轮从右到左，第三轮从左到右......

       算法的时间复杂度：
                同冒泡排序一样，是O(n**2)，如果排序前，数列中大部分都已经是有序的了，那么时间复杂度接近O(n)
        Java代码实现：

1. public class CockTailSort {
   
2.         public static void sort1(int[] array) {
   
3.                 int temp;
   
4.                
   
5.                 for (int i=0;i<array.length/2;i++) {
   
6.                         //有序标记
   
7.                         boolean isSorted = true;
   
8.                        
   
9.                         //奇数轮，从左往右
   
10.                         for (int j=i;j<array.length - i - 1;j++) {
    
11.                                 if (array[j] > array[j+1]) {
    
12.                                         temp = array[j];
    
13.                                         array[j] = array[j+1];
    
14.                                         array[j+1] = temp;
    
15.                                        
    
16.                                         //有交换，标记为无序
    
17.                                         isSorted = false;
    
18.                                 }
    
19.                         }
    
20.                         if (isSorted) {
    
21.                                 break;
    
22.                         }
    
23.                        
    
24.                         //偶数轮，从右往左
    
25.                         //排序前重新标记
    
26.                         isSorted = true;
    
27.                        
    
28.                         for (int j=array.length - i - 1;j>i;j--) {
    
29.                                 if (array[j] < array[j-1]) {
    
30.                                         temp = array[j];
    
31.                                         array[j] = array[j-1];
    
32.                                         array[j-1] = temp;
    
33.                                        
    
34.                                         isSorted = false;
    
35.                                 }
    
36.                         }
    
37.                         if (isSorted) {
    
38.                                 break;
    
39.                         }
    
40.                 }
    
41.         }
    
42.       
    
43.         public static void main(String[] args) {
    
44.                 int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
    
45.                
    
46.                 sort1(list);
    
47.                
    
48.                 for (int i=0;i<list.length;i++) {
    
49.                         System.out.print(list + " ");
    
50.                 }
    
51.         }
    
52. }
    

复制代码

        
二. 鸡尾酒排序算法的优化
        优化思路：同冒泡排序一样，某轮排序后，实际有序区可能大于理论有序区
        优化方法：增加有序区边界标识，具体与冒牌排序及其优化基本相同
        Java代码实现：

1. public class CockTailSort {
   
2.         public static void sort2(int[] array) {
   
3.                 int temp;
   
4.                 //左右最后交换元素的位置
   
5.                 int leftIndex = 0, rightIndex = 0;
   
6.                 //左边界
   
7.                 int leftSortBorder = 0;
   
8.                 //有边界
   
9.                 int rightSortBorder = array.length - 1;
   
10.                
    
11.                 for (int i=0;i<array.length/2;i++) {
    
12.                         //有序标记
    
13.                         boolean isSorted = true;
    
14.                        
    
15.                         //奇数轮，从左往右
    
16.                         for (int j=leftSortBorder;j<rightSortBorder;j++) {
    
17.                                 if (array[j] > array[j+1]) {
    
18.                                         temp = array[j];
    
19.                                         array[j] = array[j+1];
    
20.                                         array[j+1] = temp;
    
21.                                        
    
22.                                         //有交换，标记为无序
    
23.                                         isSorted = false;
    
24.                                         //记录交换元素的位置
    
25.                                         rightIndex = j;
    
26.                                 }
    
27.                         }
    
28.                         if (isSorted) {
    
29.                                 break;
    
30.                         }
    
31.                         rightSortBorder = rightIndex;
    
32.                        
    
33.                         //偶数轮，从右往左
    
34.                         //排序前重新标记
    
35.                         isSorted = true;
    
36.                        
    
37.                         for (int j=rightSortBorder;j>leftSortBorder;j--) {
    
38.                                 if (array[j] < array[j-1]) {
    
39.                                         temp = array[j];
    
40.                                         array[j] = array[j-1];
    
41.                                         array[j-1] = temp;
    
42.                                        
    
43.                                         isSorted = false;
    
44.                                         leftIndex = j;
    
45.                                 }
    
46.                         }
    
47.                         if (isSorted) {
    
48.                                 break;
    
49.                         }
    
50.                         leftSortBorder = leftIndex;
    
51.                 }
    
52.         }
    
53.       
    
54.         public static void main(String[] args) {
    
55.                 int[] list = {5, 8, 6, 3, 9, 2, 1, 7};
    
56.                
    
57.                 sort2(list);
    
58.                
    
59.                 for (int i=0;i<list.length;i++) {
    
60.                         System.out.print(list + " ");
    
61.                 }
    
62.         }
    
63. }
    
64. 
    

复制代码

三.应用场景
在大部分元素已经有序的情况下，能够发挥出优势