快速排序,经典的排序算法,用到了递归。
核心思想
要将一个数组排序,先随机以一个数为基准,将比其大的数放到其右边,比其小的数放到其左边,然后再递归排以这个数为中心的左半区间和右半区间。
注意点
一定要随机化选择切分元素(pivot),否则在输入数组是有序数组或者是逆序数组的时候,快速排序会变得非常慢。
![快速排序示意图](https://cdn.jsdelivr.net/gh/chengzhy/blog-images/img/quick_sort.gif)
时间复杂度
时间复杂度为O(nlogn)。
空间复杂度
空间复杂度为O(h),其中h为快速排序递归调用的层数。我们需要额外的O(h)的递归调用的栈空间,由于划分的结果不同导致了快速排序递归调用的层数也会不同,最坏情况下需O(n)的空间,最优情况下每次都平衡,此时整个递归树高度为logn,空间复杂度为O(logn)。
稳定性
不稳定。
代码示例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
| public int[] sortArray(int[] nums) { quickSort(nums, 0, nums.length - 1); return nums; }
private void quickSort(int[] nums, int left, int right) { if (left < right) {
int i = partition(nums, left, right); quickSort(nums, left, i - 1); quickSort(nums, i + 1, right); } }
private int partition(int[] nums, int left, int right) {
int randomIndex = left + new Random().nextInt(right - left + 1); int temp = nums[left]; nums[left] = nums[randomIndex]; nums[randomIndex] = temp; int base = nums[left]; int i = left, j = right; while (i < j) { while (base <= nums[j] && i < j) { j--; } while (base >= nums[i] && i < j) { i++; } if (i < j) { temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } nums[left] = nums[i]; nums[i] = base; return i; }
|