Java 中冒泡、二分、快速算法详解

冒泡排序

冒泡排序是一种简单的排序算法，通过不断交换相邻元素的值，把最大或最小的元素逐步“浮”到数列的顶端或底端。具体流程如下：

1. 比较相邻的两个元素，如果前一个元素大于后一个元素，则交换这两个元素的位置。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾最后一对。这样一轮排序过后，排在数列末尾的元素就是最大或最小的元素。
3. 再针对除去已排序的元素外的数列中的所有元素进行同样的操作，直到整个数列有序。

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

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

示例：

int[] arr = {3, 9, 4, 5, 2, 1, 6};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
// 输出结果为："[1, 2, 3, 4, 5, 6, 9]"

二分查找

二分查找也叫折半查找，是一种高效的查找算法，适用于有序数列。它查找过程从数列的中间元素开始，如果该元素等于查找值，则查找成功，否则根据中间元素和查找值的大小关系，决定去上半段还是下半段继续查找，直到查找值被找到或数列被查找完仍未找到。具体流程如下：

1. 找到数列的中间值。
2. 如果中间值等于查找值，则查找成功，返回索引值。
3. 如果中间值大于查找值，则在中间值的左半部分继续查找。
4. 如果中间值小于查找值，则在中间值的右半部分继续查找。
5. 如果未找到，则返回-1。

二分查找的代码实现如下：

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

示例：

int[] arr = {1, 2, 3, 4, 5, 6, 9};
int target = 5;
System.out.println(binarySearch(arr, target));
// 输出结果为："4"

快速排序

快速排序是一种比较常用的排序算法，通过递归将数列不断分解为更小的子数列，然后再将它们合并成一个有序的数列。具体流程如下：

1. 选择一个基准元素（一般选择数列的第一个元素），把数列分成两部分。
2. 将比基准元素小的元素放在左边的子序列中，大于基准元素的元素放在右边的子序列中，越过基准元素。
3. 对左右两个子序列分别进行快速排序，直到各个子序列中只有一个元素或空序列。
4. 合并所有子序列，得到最终有序序列。

快速排序的代码实现如下：

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int i = left, j = right, pivot = arr[left];
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        if (i < j) {
            arr[i++] = arr[j];
        }
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        if (i < j) {
            arr[j--] = arr[i];
        }
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

示例：

int[] arr = {3, 9, 4, 5, 2, 1, 6};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
// 输出结果为："[1, 2, 3, 4, 5, 6, 9]"