本文共 1937 字，大约阅读时间需要 6 分钟。

Java四大排序与快速排序实现

一、冒泡排序

冒泡排序是一种简单的排序算法，通过每一次两两比较并交换元素位置，最终将数组按从小到大排序。其工作原理如下：

算法描述：

• 外层循环遍历整个数组。
• 内层循环从当前元素开始，向右比较并交换。
• 重复上述过程，直到整个数组排序完成。

优化与时间复杂度：

• 时间复杂度：O(N²)
• 空间复杂度：O(1)
• 稳定性：稳定排序算法。

二、快速排序

快速排序是一种高效的排序算法，通过选择基准值并将数组划分为左右两部分，最终递归排序左右子数组。其非递归实现通过栈模拟递归：

三、优化快速排序

为了避免栈溢出，快速排序采用了三数取中法和插入排序优化：

四、时间复杂度对比

五、优化代码示例

public static void quickSort(int[] array, int low, int high) {
    if (low == high) {
        return;
    }
    if (high - low + 1 <= 10) {
        insertSort(array, low, high);
        return;
    }
    int mid = takeMiddle(array, low, high);
    int par = partition(array, low, high, mid);
    if (par > low + 1) {
        quickSort(array, low, par - 1);
    }
    if (par < high - 1) {
        quickSort(array, par + 1, high);
    }
}
public static int partition(int[] array, int low, int high, int mid) {
    swap(array, low, mid);
    int i = low + 1;
    int j = high;
    while (i < j) {
        if (array[i] < array[j]) {
            i++;
        } else {
            if (array[i] > array[j]) {
                j--;
            } else {
                swap(array, i++, j--);
            }
        }
    }
    swap(array, low, j);
    return j;
}
public static int takeMiddle(int[] array, int low, int high) {
    int mid = (low + high) / 2;
    if (array[mid] > array[low]) {
        swap(array, low, mid);
    }
    if (array[mid] > array[high]) {
        swap(array, mid, high);
    }
    if (array[low] > array[high]) {
        swap(array, low, high);
    }
    return mid;
}

六、总结

快速排序通过基准值分组和递归排序，时间复杂度为O(N logN)，性能优于冒泡排序。其非递归实现通过栈模拟递归，避免了函数调用栈溢出。通过三数取中和随机化优化，进一步提升了效率。

转载地址：http://fuza.baihongyu.com/