排序算法 -鸡尾酒排序

简介


鸡尾酒排序是冒泡排序的一种,又称为来回排序。它比冒泡排序要高级点, 冒泡排序的每一个元素都可以像小气泡一样,根据自身大小,一点一点地向着数组的一侧移动。算法的每一轮都是从左到右来比较元素,进行单向的位置交换。而鸡尾酒排序元素比较和交换过程是双向的。

举例,有数组 int[] array={5,8,6,3,9,2,1,7};

在这里插入图片描述 第一趟排序:

  • 从左往右

第一次排序:5 和 8 比较,5 小于 8 ,位置不变: 5,8,6,3,9,2,1,7

第二次排序:8 和 6 比较,8 大于 6 ,交换位置: 5,6,8,3,9,2,1,7

第三次排序:8 和 3 比较,8 大于 3 ,交换位置: 5,6,3,8,9,2,1,7

第四次排序:8 和 9 比较,8 小于 9 ,位置不变: 5,6,3,8,9,2,1,7

第五次排序:9 和 2 比较,9 大于 2 ,交换位置: 5,6,3,8,2,9,1,7

第六次排序:9 和 1 比较,9 小于 1 ,交换位置: 5,6,3,8,2,1,9,7

第七次排序:9 和 7 比较,9 小于 7 ,交换位置: 5,6,3,8,2,1,7,9

  • 从右往左

第一次排序:9 和 7 比较,9 大于 7 ,位置不变: 5,6,3,8,2,1,7,9

第二次排序:7 和 1 比较,7 大于 1 ,位置不变: 5,6,3,8,2,1,7,9

第三次排序:1 和 2 比较,1 小于 2 ,交换位置: 5,6,3,8,1,2,7,9

第四次排序:1 和 8 比较,1 小于 8 ,交换位置: 5,6,3,1,8,2,7,9

第五次排序:1 和 3 比较,1 小于 3 ,交换位置: 5,6,1,3,8,2,7,9

第六次排序:1 和 6 比较,1 小于 6 ,交换位置: 5,1,6,3,8,2,7,9

第七次排序:1 和 5 比较,1 大于 5 ,交换位置: 1,5,6,3,8,2,7,9

第二趟排序:

  • 从左往右

第一次排序:1 和 5 比较,1 小于 5 ,位置不变: 1,5,6,3,8,2,7,9

第二次排序:5 和 6 比较,5 小于 6 ,位置不变: 1,5,6,3,8,2,7,9

第三次排序:6 和 3 比较,6 大于 3 ,交换位置: 1,5,3,6,8,2,7,9

第四次排序:6 和 8 比较,6 小于 8 ,位置不变: 1,5,3,6,8,2,7,9

第五次排序:8 和 2 比较,8 大于 2 ,交换位置: 1,5,3,6,2,8,7,9

第六次排序:8 和 7 比较,8 大于 7 ,交换位置: 1,5,3,6,2,7,8,9

第七次排序:8 和 9 比较,8 小于 9 ,位置不变: 1,5,3,6,2,7,8,9

  • 从右往左

第一次排序:9 和 8 比较,9 大于 8 ,位置不变: 1,5,3,6,2,7,8,9

第二次排序:8 和 7 比较,8 大于 7 ,位置不变: 1,5,3,6,2,7,8,9

第三次排序:7 和 2 比较,7 大于 2 ,位置不变: 1,5,3,6,2,7,8,9

第四次排序:2 和 6 比较,2 小于 6 ,交换位置: 1,5,3,2,6,7,8,9

第五次排序:2 和 3 比较,2 小于 3 ,交换位置: 1,5,2,3,6,7,8,9

第六次排序:2 和 5 比较,2 小于 5 ,交换位置: 1,2,5,3,6,7,8,9

第七次排序:2 和 1 比较,2 大于 1 ,位置不变: 1,2,5,3,6,7,8,9

第三趟排序:

  • 从左往右

第一次排序:1 和 2 比较,1 小于 2 ,位置不变: 1,2,5,3,6,7,8,9

第二次排序:2 和 5 比较,2 小于 5 ,位置不变: 1,2,5,3,6,7,8,9

第三次排序:5 和 3 比较,5 大于 3 ,交换位置: 1,2,3,5,6,7,8,9

第四次排序:5 和 6 比较,5 小于 6 ,位置不变: 1,2,3,5,6,7,8,9

第五次排序:6 和 7 比较,6 小于 7 ,位置不变: 1,2,3,5,6,7,8,9

第六次排序:7 和 8 比较,7 小于 8 ,位置不变: 1,2,3,5,6,7,8,9

第七次排序:8 和 9 比较,8 小于 9 ,位置不变: 1,2,3,5,6,7,8,9

  • 从右往左

第一次排序:9 和 8 比较,9 大于 8 ,位置不变: 1,2,3,5,6,7,8,9

第二次排序:8 和 7 比较,8 大于 7 ,位置不变: 1,2,3,5,6,7,8,9

第三次排序:7 和 6 比较,7 大于 6 ,位置不变: 1,2,3,5,6,7,8,9

第四次排序:6 和 5 比较,6 小于 5 ,位置不变: 1,2,3,5,6,7,8,9

第五次排序:5 和 3 比较,5 小于 3 ,位置不变: 1,2,3,5,6,7,8,9

第六次排序:3 和 2 比较,3 小于 2 ,位置不变: 1,2,3,5,6,7,8,9

第七次排序:2 和 1 比较,2 大于 1 ,位置不变: 1,2,3,5,6,7,8,9

排序结果 : 1,2,3,5,6,7,8,9

/**
 * 鸡尾酒排序
 */
public class demo2 {

    public static void main(String[] args) {
        int array[] = {5,8,6,3,9,2,1,7};

        sortBig(array);
        System.out.println("大到小排列:"+ Arrays.toString(array));

        sortSmall(array);
        System.out.println("小到大排列:"+ Arrays.toString(array));
    }

    /**
     * 从大到小排序方法
     * @param array 数组
     */
    private static void sortBig(int[] array) {
        int temp = 0;
        for (int i = 0; i < array.length/2; i++) {
            //标记
            boolean flag = true;
            for (int j = 0; j < array.length-i-1; j++) {
                if(array[j] < array[j+1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    flag = false;
                }
            }
            if (flag)
                break;

            for (int j = array.length-i-1; j > i ; j--) {
                if(array[j] > array[j-1]){
                    temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                    flag = false;
                }
            }
            if(flag)
                break;
        }
    }


    /**
     * 从小到大排序
     * @param array 数组
     */
    private static void sortSmall(int[] array) {
        int temp = 0;
        for (int i = 0; i < array.length/2; i++) {
            //标记
            boolean flag = true;
            for (int j = 0; j < array.length-i-1; j++) {
                if(array[j] > array[j+1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    flag = false;
                }
            }
            if (flag)
                break;

            for (int j = array.length-i-1; j > i ; j--) {
                if(array[j] < array[j-1]){
                    temp = array[j];
                    array[j] = array[j-1];
                    array[j-1] = temp;
                    flag = false;
                }
            }
            if(flag)
                break;
        }
    }

}

大到小排列:[9, 8, 7, 6, 5, 3, 2, 1]

小到大排列:[1, 2, 3, 5, 6, 7, 8, 9]

代码外层的大循环控制着所有排序回合,大循环内包含2个小循环,第一个循环从左向右比较并交换元素,第二个小循环从右向左比较并交换元素。


鸡尾酒排序优缺点

  • 优点:鸡尾酒排序的优点是能够在特定条件下,减小排序的回合数;

  • 缺点:代码量增加一倍,发挥性能的优势在于大部分元素已经有序;



个人博客地址:http://blog.yanxiaolong.cn 『纵有疾风起,人生不言弃』

end
  • 作者:yxl(联系作者)
  • 发表时间:2021-05-10 17:49
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 转载声明:如果是转载栈主转载的文章,请附上原文链接
  • 公众号转载:请在文末添加作者公众号二维码(公众号二维码见右边,欢迎关注)
  • 评论