冒泡排序/鸡尾酒排序

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，它通过多次交换相邻元素的位置来实现排序。它的基本思想是从数组的第一个元素开始，比较相邻的两个元素，如果它们的顺序错误，则交换它们的位置。重复进行这个过程，直到整个数组排序完成。

以下是冒泡排序的一种常见的Java实现：

public class BubbleSort {
    public static void bubbleSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    // 交换相邻元素的位置
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(array);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这段代码演示了冒泡排序算法的实现。在bubbleSort()方法中，使用两个嵌套的循环来遍历数组并比较相邻元素的大小。如果前一个元素大于后一个元素，则进行交换。通过不断交换，较大的元素会逐渐“冒泡”到数组的末尾。外层循环控制排序的轮数，内层循环进行具体的比较和交换操作。

最后，在main()方法中，我们创建一个示例数组并调用bubbleSort()方法对其进行排序。然后打印出排序后的数组。

冒泡排序的时间复杂度为O(n^2)，其中n是数组的大小。虽然冒泡排序在性能上不如其他高效的排序算法，但是由于其实现简单，适用于小规模的数据排序。

除了上述的常见实现外，还可以对冒泡排序进行优化，例如设置一个标志位来判断某一轮是否有元素交换，如果没有交换，则说明数组已经有序，可以提前结束排序。也可以针对特定情况进行优化，比如在已经有序的部分不再进行比较。这些优化可以减少一些不必要的比较和交换操作，提高排序效率。

public class BubbleSort {
    public static void bubbleSort(int[] array) {
        int n = array.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    // 交换相邻元素的位置
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }
            // 如果某一轮没有进行元素交换，则说明数组已经有序，提前结束排序
            if (!swapped) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(array);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

在这个优化版本的冒泡排序中，我们引入了一个名为swapped的标志位。在每一轮的比较过程中，如果有元素交换，则将swapped设置为true。如果某一轮没有进行元素交换，说明数组已经有序，可以提前结束排序。

通过引入标志位，可以避免在已经有序的情况下进行不必要的比较和交换操作，从而提高了冒泡排序的效率。

请注意，在最坏情况下，即输入数组完全逆序的情况下，优化后的冒泡排序的时间复杂度仍然是O(n^2)。优化的作用是在部分有序的情况下，减少了比较和交换的次数，提高了效率。

冒泡排序的多种Java实现可以根据具体的优化策略和需求进行调整和扩展，以满足特定场景下的排序需求。

鸡尾酒排序

鸡尾酒排序（Cocktail Sort），也称为双向冒泡排序（Bidirectional Bubble Sort）或定向冒泡排序（Shaker Sort），是冒泡排序的一种变体。它在排序过程中来回地在待排序序列中进行扫描和交换，以实现排序。

鸡尾酒排序的基本思想是从序列的起始位置开始，通过比较相邻元素的大小并交换它们的位置，将较大的元素逐渐“冒泡”到序列的末尾。然后，从序列的末尾开始，反向进行相同的操作，将较小的元素逐渐“冒泡”到序列的起始位置。通过来回扫描和交换的过程，逐渐缩小待排序序列的范围，直到整个序列排序完成。

以下是鸡尾酒排序的算法描述：

1. 初始化两个指针left和right，分别指向待排序序列的起始位置和末尾位置。
2. 进行以下循环，直到left不再小于right为止：
   • 从左到右遍历序列，比较相邻元素的大小，如果前一个元素大于后一个元素，则交换它们的位置。
   • 将right指针向左移动一位，缩小待排序序列的范围。
   • 从右到左遍历序列，比较相邻元素的大小，如果前一个元素大于后一个元素，则交换它们的位置。
   • 将left指针向右移动一位，缩小待排序序列的范围。
3. 完成排序后，序列中的元素按照从小到大的顺序排列。

以下是使用Java编写的鸡尾酒排序算法实现：

public class CocktailSort {
    public static void cocktailSort(int[] array) {
        int n = array.length;
        int left = 0;
        int right = n - 1;
        boolean swapped;

        while (left < right) {
            swapped = false;

            // 从左到右遍历，将较大的元素冒泡到末尾
            for (int i = left; i < right; i++) {
                if (array[i] > array[i + 1]) {
                    swap(array, i, i + 1);
                    swapped = true;
                }
            }
            right--;

            // 从右到左遍历，将较小的元素冒泡到起始位置
            for (int i = right; i > left; i--) {
                if (array[i] < array[i - 1]) {
                    swap(array, i, i - 1);
                    swapped = true;
                }
            }
            left++;

            // 如果某一轮没有进行元素交换，则说明数组已经有序，提前结束排序
            if (!swapped) {
                break;
            }
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};
        cocktailSort(array);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

在上述代码中，我们使用left和right两个指针来分别表示待排序序列的起始位置和末尾位置。通过不断地在序列中来回进行扫描和交换操作，可以逐渐将最大和最小的元素移动到正确的位置上。在每一轮的遍历过程中，如果没有进行元素交换，说明序列已经有序，可以提前结束排序。

请注意，鸡尾酒排序的时间复杂度也是O(n^2)，其中n是数组的大小。虽然鸡尾酒排序相比于传统的冒泡排序在某些情况下能够提升效率，但它仍然是一种相对较慢的排序算法。因此，在实际应用中，如果需要排序大规模数据，通常会选择效率更高的排序算法，如快速排序或归并排序。