排序-快速排序

快速排序（Quick Sort）是一种高效的排序算法，由英国计算机科学家霍尔（C. A. R. Hoare）在1960年提出。它的基本思想是：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。以下是快速排序的主要知识点：

1. 基本思想：

   • 选择一个基准元素（pivot）。
   • 通过一趟排序将待排序列分割成独立的两部分，其中一部分的所有元素都比基准元素小，另一部分的所有元素都比基准元素大。
   • 然后对这两部分分别进行快速排序，整个排序过程可以递归进行。

2. 选择基准元素：

   • 基准元素的选择有多种方法，如选择序列的第一个、最后一个或中间元素作为基准。
   • 基准元素的选择对快速排序的性能有很大影响，因此有些优化版本的快速排序会采用更复杂的策略来选择基准元素。

3. 分割过程：

   • 从序列的右端开始，向左扫描，找到第一个小于基准元素的元素。
   • 从序列的左端开始，向右扫描，找到第一个大于基准元素的元素。
   • 交换这两个元素的位置。
   • 重复以上步骤，直到左、右指针相遇或交错。

4. 递归排序：

   • 对基准元素左边的子序列和右边的子序列分别进行快速排序。

5. 优化策略：

   • 三数取中法：选择序列首、尾、中间三个数中的中值作为基准元素，以减少最坏情况（O(n^2)）的发生概率。
   • 小数组直接插入排序：当子序列的长度较小时，直接采用插入排序而不是递归调用快速排序，因为插入排序在处理小数组时效率更高。
   • 处理相等元素：在分割过程中，当遇到与基准元素相等的元素时，可以将其与基准元素交换到同一侧，以减少不必要的交换和比较。

6. 时间复杂度：

   • 平均时间复杂度：O(nlogn)，其中n是待排序列的长度。
   • 最坏时间复杂度：O(n2)，当输入序列已经有序或接近有序时，快速排序的性能会退化为O(n2)。
   • 最好时间复杂度：O(nlogn)，当每次分割都能将序列均匀地分成两部分时，快速排序的性能最好。

7. 空间复杂度：

   • 快速排序是原地排序算法，空间复杂度为O(logn)，其中logn是递归调用栈的最大深度。但在最坏情况下，递归调用栈的深度可能达到n，因此空间复杂度为O(n)。然而，这种情况在实际应用中很少出现。

8. 稳定性：

   • 快速排序是不稳定的排序算法，因为在分割过程中可能会改变相等元素的相对顺序。

9. 代码示例：

public class QuickSort {  
  
    public static void quickSort(int[] array, int left, int right) {  
        if (left < right) {  
            int pivotIndex = partition(array, left, right);  
            quickSort(array, left, pivotIndex - 1);  
            quickSort(array, pivotIndex + 1, right);  
        }  
    }  
  
    private static int partition(int[] array, int left, int right) {  
        int pivot = array[right]; // 通常选择最右侧的元素作为基准  
        int i = left - 1; // i为小于基准元素的索引  
  
        for (int j = left; j <= right - 1; j++) {  
            if (array[j] <= pivot) {  
                i++;  
                // 交换array[i]和array[j]  
                int temp = array[i];  
                array[i] = array[j];  
                array[j] = temp;  
            }  
        }  
  
        // 将基准元素放到正确的位置  
        int temp = array[i + 1];  
        array[i + 1] = array[right];  
        array[right] = temp;  
  
        // 返回基准元素的索引  
        return i + 1;  
    }  
  
    public static void main(String[] args) {  
        int[] array = {3, 6, 8, 10, 1, 2, 1};  
        quickSort(array, 0, array.length - 1);  
  
        // 打印排序后的数组  
        for (int num : array) {  
            System.out.print(num + " ");  
        }  
    }  
}

在这个实现中，quickSort 方法是递归的主体部分，它调用 partition 方法来选择一个基准元素，并将数组分为两部分。partition 方法负责选择基准元素（这里选择的是最右侧的元素），并重新排列数组，使得小于基准的元素都在其左边，大于基准的元素都在其右边。然后，quickSort 方法递归地对基准元素左右两边的子数组进行排序。

在 main 方法中，我们创建了一个需要排序的数组，并调用了 quickSort 方法。最后，我们打印出排序后的数组。

注意，这个实现假设输入的数组 array 不会被其他线程修改，并且在排序过程中不会改变原数组（因为它是在原数组上进行原地排序的）。