快速排序算法详解及Java实现示例

快速排序

快速排序（Quick Sort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略来对数据进行排序。它的基本思想是通过一个“基准”元素将数组分成两个子数组，其中一个子数组的所有元素都小于基准元素，另一个子数组的所有元素都大于基准元素，然后递归地对这两个子数组进行排序。

快速排序的步骤

1. 选择基准：从数组中选择一个元素作为基准（pivot），通常选择第一个元素、最后一个元素或随机选择一个元素。
2. 分区：重新排列数组，使得所有小于基准的元素都在基准的左侧，所有大于基准的元素都在基准的右侧。此时，基准元素的位置就是它在排序后数组中的最终位置。
3. 递归排序：对基准左侧和右侧的子数组递归执行快速排序。

快速排序的时间复杂度

• 平均时间复杂度：O(n log n)
• 最坏时间复杂度：O(n²)（当数组已经是有序的，或者所有元素相同）
• 空间复杂度：O(log n)（递归调用栈的空间）

Java 实现快速排序

下面是一个简单的 Java 实现快速排序的示例代码：

public class QuickSort {

    // 主方法
    public static void main(String[] args) {
        int[] array = {10, 7, 8, 9, 1, 5};
        System.out.println("原始数组:");
        printArray(array);
        
        quickSort(array, 0, array.length - 1);
        
        System.out.println("排序后的数组:");
        printArray(array);
    }

    // 快速排序方法
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            // 找到分区索引
            int partitionIndex = partition(array, low, high);
            
            // 递归排序左侧和右侧
            quickSort(array, low, partitionIndex - 1);
            quickSort(array, partitionIndex + 1, high);
        }
    }

    // 分区方法
    public static int partition(int[] array, int low, int high) {
        // 选择最后一个元素作为基准
        int pivot = array[high];
        int i = (low - 1); // 小于基准的元素索引

        for (int j = low; j < high; j++) {
            // 如果当前元素小于或等于基准
            if (array[j] <= pivot) {
                i++;
                // 交换元素
                swap(array, i, j);
            }
        }
        // 交换基准元素到正确的位置
        swap(array, i + 1, high);
        return i + 1; // 返回基准的索引
    }

    // 交换数组中的两个元素
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // 打印数组
    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

代码分析

1. 主方法：创建一个整数数组并调用 quickSort 方法进行排序。
2. quickSort 方法：检查当前子数组的边界，如果 low 小于 high，则调用 partition 方法进行分区，并递归地对左右子数组进行排序。
3. partition 方法：选择最后一个元素作为基准，遍历数组并将小于基准的元素移动到左侧，最后将基准元素放到正确的位置并返回其索引。
4. swap 方法：用于交换数组中两个元素的位置。
5. printArray 方法：用于打印数组的内容。

总结

快速排序是一种高效的排序算法，适用于大多数情况下的排序需求。通过合理选择基准和优化分区过程，可以提高其性能。希望这个详细的解释和代码示例能帮助你理解快速排序的原理和实现。