排序算法 - 鸡尾酒排序

基本思想

鸡尾酒排序基于冒泡排序,双向循环。

举个例子：给定待排数组[2 3 4 5 1]

第一趟过去时的每一步。

第一步迭代,2 < 3不换

[2 3 4 5 1]

第二步迭代,3 < 4不换

[2 3 4 5 1]

第三步迭代,4 < 5不换

[2 3 4 5 1]

第四步迭代,5 > 1交换

[2 3 4 1 5]

第一趟回来时的第一步,鸡尾酒一次到头后就回返回来,再到头后再过去,来回比,一个来回能排两个数字。

第五步迭代,1 < 5不交换

[2 3 4 1 5]

第六步迭代,1 < 4交换

[2 3 1 4 5]

第七步迭代,1 < 3交换

[2 1 3 4 5]

第八步迭代,2 > 1交换

[1 2 3 4 5]

排序完毕,顺序输出结果即可得[ 1 2 3 4 5]。

如何判断排序结束了?

假如一趟来回没有交换任何数字,则表示该数组已经有序了,可以设置了个变量表示有没有交换过。

代码

package main.java.com.study.sortingAalgorithm;

import main.java.com.study.utils.CommonUtils;

/**
 * @author: whb
 * @description: 鸡尾酒排序 基于冒泡排序,双向循环
 */
public class CocktailSort {

    public static void cocktailSort(int[] unsorted) {
        boolean swapped = false;
        do {
            for (int i = 0; i < unsorted.length - 1; i++) {
                if (unsorted[i] > unsorted[i + 1]) {
                    int temp = unsorted[i];
                    unsorted[i] = unsorted[i + 1];
                    unsorted[i + 1] = temp;
                    swapped = true;
                }
            }
            swapped = false;
            for (int j = unsorted.length - 1; j > 0; j--) {
                if (unsorted[j] < unsorted[j - 1]) {
                    int temp = unsorted[j];
                    unsorted[j] = unsorted[j - 1];
                    unsorted[j - 1] = temp;
                    swapped = true;
                }
            }
        } while (swapped);
    }

    public static void main(String[] args) {
        int[] unsorted = {6, 2, 4, 1, 5, 9};
        System.out.println("**************鸡尾酒排序******************");
        System.out.println("排序前：");
        CommonUtils.display(unsorted);
        System.out.println("排序后：");
        cocktailSort(unsorted);
        CommonUtils.display(unsorted);
    }
}

测试结果