Quick Sort 快速排序
快速排序（Quick Sort）是一种常用的排序算法，其思路如下：
- 选择一个元素作为基准（通常选择数组的第一个或最后一个元素）。
- 将数组分成两个子数组，小于基准的元素放在左边，大于基准的元素放在右边，基准元素放在两个子数组中间。
- 对左右两个子数组递归地进行步骤1和步骤2，直到子数组的长度为1或0，即已经有序。
以下是快速排序的具体步骤：
- 选择基准元素（例如选择第一个元素）。
- 使用双指针，一个指向数组的起始位置，一个指向数组的末尾位置。
- 将比基准元素小的元素移到左边，比基准元素大的元素移到右边，同时记录基准元素的最终位置。
- 递归地对左右两个子数组进行步骤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 <= right && arr[right] > 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)，因为递归调用需要使用额外的栈空间。
快速排序是一种原地排序算法，不需要额外的空间来存储临时数组。
