1. 冒泡排序（Bubble Sort）

• 思想：通过相邻元素比较和交换，将最大（或最小）元素逐步“冒泡”到数组末尾。

• 时间复杂度：

  • 最好情况（已有序）：O(n)。

  • 最坏情况（逆序）：O(n²)。

• 空间复杂度：O(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 - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 交换相邻元素
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

2. 快速排序（Quick Sort）

• 思想：分治法，选择一个基准元素，将数组分为两部分（小于基准和大于基准），递归排序。

• 时间复杂度：

  • 平均情况：O(n log n)。

  • 最坏情况（已有序）：O(n²)。

• 空间复杂度：O(log n)（递归栈空间）。

• 稳定性：不稳定。

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high); // 分区
        quickSort(arr, low, pivotIndex - 1);  // 递归排序左半部分
        quickSort(arr, pivotIndex + 1, high); // 递归排序右半部分
    }
}

private static int partition(int[] arr, int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = low - 1; // 较小元素的索引
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            // 交换 arr[i] 和 arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 将基准元素放到正确位置
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

3. 插入排序（Insertion Sort）

• 思想：将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置。

• 时间复杂度：

  • 最好情况（已有序）：O(n)。

  • 最坏情况（逆序）：O(n²)。

• 空间复杂度：O(1)（原地排序）。

• 稳定性：稳定。

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // 待插入元素
        int j = i - 1;
        // 将比 key 大的元素后移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // 插入 key
    }
}

4. 归并排序（Merge Sort）

• 思想：分治法，将数组分为两半，分别排序后合并。

• 时间复杂度：O(n log n)（所有情况）。

• 空间复杂度：O(n)（需要额外空间存储合并结果）。

• 稳定性：稳定。

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // 计算中间位置
        mergeSort(arr, left, mid);      // 递归排序左半部分
        mergeSort(arr, mid + 1, right); // 递归排序右半部分
        merge(arr, left, mid, right);  // 合并两部分
    }
}

private static void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] L = new int[n1]; // 左半部分
    int[] R = new int[n2]; // 右半部分

    // 复制数据到临时数组
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    // 合并临时数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 复制剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

总结对比

选择建议

1. 小规模数据：插入排序或冒泡排序（简单易实现）。

2. 大规模数据：快速排序（性能最优）或归并排序（需稳定排序时）。

3. 稳定性要求：归并排序或插入排序。

4. 内存限制：快速排序（空间复杂度低）。