排序算法--快速排序
6、快速排序(Quick Sort)
快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
6.1 算法描述
快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:
- 从数列中挑出一个元素,称为 “基准”(pivot);
- 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
- 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
6.2 动图演示
6.3 代码实现
/** * @author cai-xiansheng * @Description 快速排序 * @create 2021-01-16 17:28 */ public class QuickSort { /** * 最快:nlogn * 最慢:n*n * @param arr * @param left * @param right */ public static void quickSort(int[] arr, int left, int right) { int len = arr.length; if (left < right) { int mid = midPosition(arr, left, right); quickSort(arr, left, mid - 1); quickSort(arr, mid + 1, right); } } private static int midPosition(int[] arr, int left, int right) { int pivot = left; int index = pivot + 1; for (int i = index; i <= right; i++) { if (arr[i] < arr[pivot]) { Util.swap(arr, i, index); index++; } } Util.swap(arr, pivot, index - 1); return index - 1; } }
一种更好的解题思路:
https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/ohwddh/
class Solution { public int[] getLeastNumbers(int[] arr, int k) { quickSort(arr, 0, arr.length - 1); return Arrays.copyOf(arr, k); } private void quickSort(int[] arr, int l, int r) { // 循环的退出条件 if(l >= r) return; int i = l, j = r; // 大循环,用来保证我们的数据全部经过处理 while (i < j) { // 小循环,用来压缩比我们基准大的数,如果小于基准时跳出循环(j位置的元素也就是从当前位置到最后的唯一一个比基准值小的数) while (i < j && arr[j] >= arr[l]) j--; // 小循环,用来压缩比我们基准小的数,如果大于基准时跳出循环(i位置的元素也是从开头到当前位置的为一个比基准值大的元素) while (i < j && arr[i] <= arr[l]) i++; // 交换我们确定的两个位置的值 swap(arr, i, j); } // 最终交换基准和最后一个比当前基准值小的元素。 swap(arr, i, l); // 递归 quickSort(arr, l, i - 1); quickSort(arr, i + 1, r); } private void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }