Java冒泡排序递归实现

Java冒泡排序递归实现的代码如下：

public static void recursiveBubbleSort(int[] arr, int n) {
    if (n == 1) {
        return;
    }
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            int temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
    }
    recursiveBubbleSort(arr, n - 1);
}

相关问题

十种java冒泡排序

### 回答1：
以下是十种 Java 冒泡排序的实现方式：

1. 普通冒泡排序

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2. 优化1：如果一次交换都没有发生，则说明已经排序完成，可以退出循环

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

3. 优化2：记录最后一次交换的位置，后面的元素已经有序，不需要再比较

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    int lastSwapIndex = n - 1;
    do {
        int newLastSwapIndex = 0;
        for (int i = 1; i <= lastSwapIndex; i++) {
            if (arr[i - 1] > arr[i]) {
                int temp = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = temp;
                newLastSwapIndex = i - 1;
            }
        }
        lastSwapIndex = newLastSwapIndex;
    } while (lastSwapIndex > 0);
}

4. 优化3：同时记录第一次交换的位置和最后一次交换的位置，可以减少比较次数

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    int firstSwapIndex = 0;
    int lastSwapIndex = n - 1;
    do {
        int newLastSwapIndex = 0;
        for (int i = firstSwapIndex + 1; i <= lastSwapIndex; i++) {
            if (arr[i - 1] > arr[i]) {
                int temp = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = temp;
                newLastSwapIndex = i - 1;
            }
        }
        lastSwapIndex = newLastSwapIndex;
        for (int i = lastSwapIndex; i >= firstSwapIndex + 1; i--) {
            if (arr[i - 1] > arr[i]) {
                int temp = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = temp;
                newLastSwapIndex = i - 1;
            }
        }
        firstSwapIndex++;
        lastSwapIndex = newLastSwapIndex;
    } while (firstSwapIndex <= lastSwapIndex);
}

5. 优化4：使用鸡尾酒排序（双向冒泡排序），可以同时从前往后和从后往前排序

public static void cocktailSort(int[] arr) {
    int n = arr.length;
    int left = 0;
    int right = n - 1;
    while (left < right) {
        for (int i = left; i < right; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        right--;
        for (int i = right; i > left; i--) {
            if (arr[i] < arr[i - 1]) {
                int temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
            }
        }
        left++;
    }
}

6. 优化5：使用定向冒泡排序，可以指定排序方向（升序或降序）

public static void directionalBubbleSort(int[] arr, boolean ascending) {
    int n = arr.length;
    int sign = ascending ? 1 : -1;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (sign * arr[j] > sign * arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

7. 优化6：使用奇偶排序（奇偶交换排序），可以同时进行并行排序

public static void oddEvenSort(int[] arr) {
    int n = arr.length;
    boolean sorted = false;
    while (!sorted) {
        sorted = true;
        for (int i = 1; i < n - 1; i += 2) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                sorted = false;
            }
        }
        for (int i = 0; i < n - 1; i += 2) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                sorted = false;
            }
        }
    }
}

8. 优化7：使用组合排序（鸽巢排序），可以同时进行多个排序

public static void pigeonholeSort(int[] arr) {
    int n = arr.length;
    int min = arr[0];
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < min) {
            min = arr[i];
        } else if (arr[i] > max) {
            max = arr[i];
        }
    }
    int range = max - min + 1;
    int[] holes = new int[range];
    for (int i = 0; i < n; i++) {
        holes[arr[i] - min]++;
    }
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (holes[i] > 0) {
            arr[index++] = i + min;
            holes[i]--;
        }
    }
}

9. 优化8：使用梳排序（改进的冒泡排序），可以加快排序速度

public static void combSort(int[] arr) {
    int n = arr.length;
    int gap = n;
    double shrink = 1.3;
    boolean sorted = false;
    while (!sorted) {
        gap = (int) Math.floor(gap / shrink);
        if (gap > 1) {
            sorted = false;
        } else {
            gap = 1;
            sorted = true;
        }
        int i = 0;
        while (i + gap < n) {
            if (arr[i] > arr[i + gap]) {
                int temp = arr[i];
                arr[i] = arr[i + gap];
                arr[i + gap] = temp;
                sorted = false;
            }
            i++;
        }
    }
}

10. 优化9：使用堆排序，可以有效地处理大量数据

public static void heapSort(int[] arr) {
    int n = arr.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    for (int i = n - 1; i >= 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

private static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

### 回答2：
冒泡排序是一种简单的排序算法，可以对一个数组进行排序。它的基本思想是通过比较相邻两个元素的大小，如果它们的顺序错误，则交换它们的位置，直到整个数组有序为止。以下是十种Java实现冒泡排序的方法：

1.普通冒泡排序：
通过两层嵌套循环，外层循环控制比较的轮数，内层循环进行相邻元素的两两比较和交换。

2.优化的冒泡排序：
在普通冒泡排序的基础上，如果某轮比较没有发生任何交换操作，则表示数组已经有序，可以提前结束排序。

3.冒泡排序的递归实现：
将冒泡排序改为递归实现，每一轮递归将找到当前数组中的最大值，并将其放在正确的位置。

4.冒泡排序的并行实现：
通过多个线程同时执行冒泡排序的比较和交换操作，可以提高排序效率。

5.双向冒泡排序：
相对于单向冒泡排序从左到右比较交换，双向冒泡排序可以从左到右和从右到左同时进行比较和交换。

6.鸡尾酒排序：
鸡尾酒排序是双向冒泡排序的一种变形，在每一轮比较和交换中，先从左到右比较交换，再从右到左比较交换。

7.冒泡排序的优化算法：鸽巢排序：
鸽巢排序是对冒泡排序的优化，在每一轮的比较和交换中，根据元素的大小将其分到对应的鸽巢中，减少了比较和交换的次数。

8.冒泡排序的优化算法：鸽巢排序的并行实现：
鸽巢排序的并行实现可以通过多个线程同时执行鸽巢排序的比较和交换操作，提高排序效率。

9.冒泡排序的优化算法：鸽巢排序的递归实现：
将鸽巢排序改为递归实现，每一轮递归将找到当前数组中的最大和最小值，并将它们放在正确的位置。

10.冒泡排序的优化算法：鸽巢排序的双向实现：
鸽巢排序可以和双向冒泡排序相结合，从左到右和从右到左同时进行比较和交换，提高排序效率。

以上是十种Java实现冒泡排序的方法，它们各有优缺点，可以根据实际情况选择适合的排序算法。

java冒泡 选择 快速排序

这三种排序算法都是常见的排序算法，它们的时间复杂度分别为O(n^2)、O(n^2)和O(nlogn)。其中，冒泡排序和选择排序都是比较简单的排序算法，而快速排序则是一种比较高效的排序算法。

冒泡排序的基本思想是：每次比较相邻的两个元素，如果它们的顺序不对就交换它们，直到没有任何一对元素需要交换为止。选择排序的基本思想是：每次从未排序的元素中选择最小（或最大）的元素，放到已排序的末尾。快速排序的基本思想是：选择一个基准元素，将小于基准元素的放在左边，大于基准元素的放在右边，然后递归地对左右两个子序列进行快速排序。