java-快速排序 1

## Java中的快速排序

### 1. 快速排序的基本概念

快速排序（Quick Sort）是一种高效的排序算法，由Tony Hoare在1960年提出。它采用分治法（Divide and Conquer）策略来将一个数组分成较小的子数组，并分别对它们进行排序。快速排序通常被认为是最实用的排序算法之一，因为它在大多数情况下具有非常好的平均性能。

### 2. 快速排序的工作原理

快速排序的核心思想是通过一个称为“基准”（Pivot）的元素将数组分为两部分，使得基准左侧的元素都小于基准，右侧的元素都大于基准。然后，递归地对左右两部分进行同样的操作，直到整个数组有序。

#### 2.1 分治法

快速排序使用分治法，将问题递归地分解成更小的子问题。具体步骤如下：

1. **选择基准**：从数组中选择一个元素作为基准，通常选择第一个元素或最后一个元素。
2. **划分数组**：重排数组，使得基准左侧的元素都小于基准，右侧的元素都大于基准。
3. **递归排序**：递归地对基准左侧和右侧的子数组进行排序。

#### 2.2 示例

假设有一个待排序的数组 `[10, 7, 8, 9, 1, 5]`，快速排序的过程如下：

1. 选择基准元素，假设选择最后一个元素 `5`。
2. 划分数组，将小于 `5` 的元素移到左侧，大于 `5` 的元素移到右侧，得到 `[1, 7, 8, 9, 10, 5]`。
3. 基准 `5` 已经在正确的位置，现在对左侧 `[1, 7, 8, 9, 10]` 和右侧空数组进行递归排序。
4. 重复上述步骤，直到数组有序。

### 3. 快速排序的实现

在Java中实现快速排序可以使用递归方法，下面是详细的实现步骤。

#### 3.1 基本实现

```java
public class QuickSort {

// 快速排序主方法
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
// 找到划分点
int pi = partition(array, low, high);
// 递归排序划分点左侧的数组
quickSort(array, low, pi - 1);
// 递归排序划分点右侧的数组
quickSort(array, pi + 1, high);
}
}

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

for (int j = low; j < high; j++) {
if (array[j] < pivot) {
i++;
// 交换元素
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// 交换基准元素到正确的位置
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;

return i + 1;
}

public static void main(String[] args) {
int[] array = {10, 7, 8, 9, 1, 5};
quickSort(array, 0, array.length - 1);
System.out.println("Sorted array:");
for (int i : array) {
System.out.print(i + " ");
}
}
}
```

在这个实现中，`quickSort`方法是快速排序的主方法，它递归地对数组进行排序。`partition`方法是划分数组的方法，它选择一个基准元素，并将数组划分为两部分。

### 4. 快速排序的时间复杂度

快速排序的时间复杂度取决于选择基准的策略和输入数组的初始顺序：

- **最好情况**：每次划分都能将数组均匀地分成两部分，时间复杂度为 O(n log n)。
- **最坏情况**：每次划分只能减少一个元素，例如输入数组已经有序或逆序，时间复杂度为 O(n^2)。
- **平均情况**：通过随机选择基准或三数取中法等策略，可以避免最坏情况，平均时间复杂度为 O(n log n)。

### 5. 快速排序的空间复杂度

快速排序的空间复杂度主要由递归调用栈的深度决定：

- **最好情况**：递归调用栈的深度为 O(log n)。
- **最坏情况**：递归调用栈的深度为 O(n)。
- **平均情况**：递归调用栈的深度为 O(log n)。

### 6. 快速排序的优化

为了提高快速排序的性能，可以进行以下优化：

#### 6.1 三数取中法

选择基准时，使用三数取中法可以避免选择最小或最大的元素作为基准，从而避免最坏情况。

```java
private static int medianOfThree(int[] array, int low, int high) {
int mid = (low + high) / 2;
if (array[low] > array[mid]) swap(array, low, mid);
if (array[low] > array[high]) swap(array, low, high);
if (array[mid] > array[high]) swap(array, mid, high);
return array[mid];
}

private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}

private static int partition(int[] array, int low, int high) {
int pivot = medianOfThree(array, low, 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;
}
```

#### 6.2 随机选择基准

随机选择基准可以避免最坏情况的发生，保证平均时间复杂度为 O(n log n)。

```java
private static int partition(int[] array, int low, int high) {
int pivotIndex = low + (int)(Math.random() * (high - low + 1));
swap(array, pivotIndex, 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;
}
```