鸡尾酒排序

十大经典排序算法

鸡尾酒排序（Cocktail sort）又称双向冒泡排序，是冒泡排序的一种变形，该算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。冒泡排序每次都是从前往后把大的数字放到后面，鸡尾酒排序是先从左往右把大的放到后面，然后再从右往左把小的放到左边……。

private void cocktailSort(int[] nums) {
    int length = nums.length;
    for (int i = 0; i < length / 2; i++) {
        // 从前往后比较，和后面的值进行比较。
        for (int j = i; j < length - 1 - i; j++) {
            if (nums[j] > nums[j + 1])// 如果前面的比后面的大就交换。
                swap(nums, j, j + 1);
        }
        // 从后往前比较，和前面的值进行比较。
        for (int j = length - 1 - (i + 1); j > i; j--) {
            if (nums[j - 1] > nums[j])// 如果前面的比后面的大就交换。
                swap(nums, j, j - 1);
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

或者还可以像下面这样写，可能会更容易理解。

private void cocktailSort(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        // 从前往后比较，和后面的值进行比较。
        for (int i = left; i < right; i++)
            if (nums[i] > nums[i + 1])// 如果前面的比后面的大就交换。
                swap(nums, i, i + 1);
        right--;// 放到right位置，下次他就不在参与比较。
        // 从后往前比较，和前面的值进行比较。
        for (int i = right; i > left; i--)
            if (nums[i - 1] > nums[i])// 如果前面的比后面的大就交换。
                swap(nums, i, i - 1);
        left++;// 放到left位置，下次他就不在参与比较。
    }
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

相关链接