算法通关村-----快速排序的原理和实现

快速排序介绍

快速排序是一种经典高效的排序方法，是分治策略在排序上的具体体现。将一个大的待排序列分割成若干个小的有序序列，最终将各个小的有序序列合并成一个大的有序序列。

快速排序的实现原理

选择一个基准值，将小于基准值的元素放在基准值左侧，大于基准值的元素放在基准值右侧，基准值放在中间。基准值可以选择待排序列的第一个元素，最后一个元素，中间元素，也可以选择三者的中位数提高快排效率。一轮快速排序后，基准值已经有序，之后对基准值两侧的数据分别进行快排，这是一个递归的过程，最终整个序列有序。整个过程类似于树的前序遍历，每一轮的过程使用双指针，所以快排本质上是树的前序遍历+双指针。

快速排序的具体实现

基准值选择不同，代码实现不同，但本质上都是树的前序遍历+双指针

选择第一个元素作为基准值代码实现

代码实现

public void quickSort(int[] array, int left, int right) {if (left < right) {int pivot = array[left];int i = right + 1;for (int j = right; j > left; j--) {if (array[j] > pivot) {i--;int temp = array[i];array[i] = array[j];array[j] = temp;}}int pivotIndex = i - 1;int temp = array[pivotIndex];array[pivotIndex] = array[left];array[left] = temp;quickSort(array, left, pivotIndex - 1);quickSort(array, pivotIndex + 1, right);}
}

选择最后一个元素作为基准值代码实现

代码实现

public void quickSort(int[] array, int left, int right) {if (left < right) {int pivot = array[right];int i = left - 1;for (int j = left; j < right; j++) {if (array[j] < pivot) {i++;int temp = array[i];array[i] = array[j];array[j] = temp;}}int pivotIndex = i + 1;int temp = array[pivotIndex];array[pivotIndex] = array[right];array[right] = temp;quickSort(array, left, pivotIndex - 1);quickSort(array, pivotIndex + 1, right);}
}

选择中值作为基准值代码实现

代码实现

public static void quickSort(int[] array, int start, int end) {if (start >= end) {return;}int left = start;int right = end;int mid = (left + right) / 2;int pivot = array[mid];while (left <= right) {while (left <= right && array[left] < pivot) {left++;}while (left <= right && array[right] > pivot) {right--;}if (left <= right) {int temp = array[left];array[left] = array[right];array[right] = temp;left++;right--;}}quickSort(array, start, right);quickSort(array, left, end);
}

快速排序复杂度分析

时间复杂度：

平均情况下：O(n log n)。在平均情况下，快速排序通常具有优秀的性能。每次分割都将数组分为两部分，每部分的大小约为原数组的一半。因此，在进行 log n 次递归后，每个子数组都会被完全排序，总的时间复杂度是 O(n log n)。

最坏情况下：O(n^2)。最坏情况发生在选择基准值不平衡的情况下，导致每次分割只能减少一个元素。例如，如果数组已经有序或接近有序，且始终选择第一个元素作为基准值，那么就会出现最坏情况。为了避免最坏情况，可以使用随机选择基准值或者三数取中法等策略。

最好情况下：O(n )。最好情况发生在数组有序

空间复杂度

快速排序是一种原地排序算法，不需要额外的内存空间，因此其空间复杂度是 O(1)。

稳定性

快速排序是不稳定的排序算法，即相等元素的相对顺序可能在排序后改变。