Quick Sort 快速排序

快速排序（Quick Sort）是一种常用的排序算法，其思路如下：

1. 选择一个元素作为基准（通常选择数组的第一个或最后一个元素）。
2. 将数组分成两个子数组，小于基准的元素放在左边，大于基准的元素放在右边，基准元素放在两个子数组中间。
3. 对左右两个子数组递归地进行步骤1和步骤2，直到子数组的长度为1或0，即已经有序。

以下是快速排序的具体步骤：

1. 选择基准元素（例如选择第一个元素）。
2. 使用双指针，一个指向数组的起始位置，一个指向数组的末尾位置。
3. 将比基准元素小的元素移到左边，比基准元素大的元素移到右边，同时记录基准元素的最终位置。
4. 递归地对左右两个子数组进行步骤1到步骤3，直到子数组的长度为1或0。

以下是快速排序的示例代码：

public class Sort {  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[low]; // 选择第一个元素作为基准  int left = low + 1;  int right = high;  while (left <= right) {  while (left <= right && arr[left] <= pivot) {  left++;  }  while (left  pivot) {  right--;  }  if (left <= right) {  swap(arr, left, right); // 交换左右指针所指向的元素  }  }  swap(arr, low, right); // 将基准元素放置到最终位置  return right;  }  private static void swap(int[] arr, int i, int j) {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  public static void main(String[] args) {  int[] array = {5, 2, 8, 12, 1, 6};  quickSort(array);  System.out.println("排序结果：");  for (int num : array) {  System.out.print(num + " ");  }  } }

快速排序的时间复杂度取决于基准的选择和数组的划分情况，最坏情况下为O(n^2)，最好情况下可达到O(n log n)。

平均情况下，快速排序的时间复杂度为O(n log n)。

快速排序的空间复杂度为O(log n)，因为递归调用需要使用额外的栈空间。

快速排序是一种原地排序算法，不需要额外的空间来存储临时数组。