排序高级之交换排序_鸡尾酒排序

2022-01-20 22:42:51

鸡尾酒排序，也就是定向冒泡排序, 鸡尾酒搅拌排序, 搅拌排序 (也可以视作选择排序的一种变形), 涟漪排序, 来回排序 or 快乐小时排序, 是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

与冒泡排序不同的地方：

鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能，原因是冒泡排序只从一个方向进行比对(由低到高)，每次循环只移动一个项目。

以序列(2,3,4,5,1)为例，鸡尾酒排序只需要访问一次序列就可以完成排序，但如果使用冒泡排序则需要四次。但是在乱数序列的状态下，鸡尾酒排序与冒泡排序的效率都很差劲。

最差时间复杂度	$排序高级之交换排序_鸡尾酒排序$
最优时间复杂度	$排序高级之交换排序_鸡尾酒排序$
平均时间复杂度	$排序高级之交换排序_鸡尾酒排序$

鸡尾酒排序动态图：

代码分析：

[html] view plain copy

 print?
package com.baobaotao.test;  
/**  
 * 排序研究  
 * @author benjamin(吴海旭)  
 * @email benjaminwhx@sina.com / 449261417@qq.com  
 *  
 */  
public class Sort {  
      
    /**  
     * 经典鸡尾酒排序  
     * @param array 传入的数组  
     */  
    public static void cocatailSort(int[] array) {  
        int length = array.length ;  
        //来回循环length/2次  
        for(int i=0;i<length/2;i++) {  
            for(int j=i;j<length-i-1;j++) {  
                if(array[j] > array[j+1]) {  
                    swap(array, j, j+1) ;  
                }  
            }  
            for(int j=length-i-1;j>i;j--) {  
                if(array[j] < array[j-1]) {  
                    swap(array, j-1, j) ;  
                }  
            }  
            printArr(array) ;  
        }  
    }  
      
    /**  
     * 鸡尾酒排序（带标志位）  
     * @param array 传入的数组  
     */  
    public static void cocatailSortFlag(int[] array) {  
        int length = array.length ;  
        boolean flag1,flag2 = true ;  
        //来回循环length/2次  
        for(int i=0;i<length/2;i++) {  
            flag1 = true ;  
            flag2 = true ;  
            for(int j=i;j<length-i-1;j++) {  
                if(array[j] > array[j+1]) {  
                    swap(array, j, j+1) ;  
                    flag1 = false ;  
                }  
            }  
            for(int j=length-i-1;j>i;j--) {  
                if(array[j] < array[j-1]) {  
                    swap(array, j-1, j) ;  
                    flag2 = false ;  
                }  
            }  
            if(flag1 && flag2) {  
                break ;  
            }  
            printArr(array) ;  
        }  
    }  
      
    /**  
     * 按从小到大的顺序交换数组  
     * @param a 传入的数组  
     * @param b 传入的要交换的数b  
     * @param c 传入的要交换的数c  
     */  
    public static void swap(int[] a, int b, int c) {  
        int temp = 0 ;  
        if(b < c) {  
            if(a[b] > a[c]) {  
                temp = a[b] ;  
                a[b] = a[c] ;  
                a[c] = temp ;   
            }  
        }  
    }  
      
    /**  
     * 打印数组  
     * @param array  
     */  
    public static void printArr(int[] array) {  
        for(int c : array) {  
            System.out.print(c + " ");  
        }  
        System.out.println();  
    }  
      
    public static void main(String[] args) {  
        int[] number={11,95,45,15,78,84,51,24,12} ;  
        int[] number2 = {11,95,45,15,78,84,51,24,12} ;  
        cocatailSort(number) ;  
        System.out.println("*****************");  
        cocatailSortFlag(number2) ;  
    }  
}  

结果分析：

[html] view plain copy

 print?
11 12 45 15 78 84 51 24 95   
11 12 15 24 45 78 51 84 95   
11 12 15 24 45 51 78 84 95   
11 12 15 24 45 51 78 84 95   
*****************  
11 12 45 15 78 84 51 24 95   
11 12 15 24 45 78 51 84 95   
11 12 15 24 45 51 78 84 95   

可见鸡尾酒排序排序的次数比普通冒泡排序要少很多。只需要4次，用了改进版的标志位鸡尾酒排序仅需要3次就可以完成排序。

转载请注明：http://blog.csdn.net/benjamin_whx/article/details/42456279

码农公寓

相关文章