算法——快速排序

介绍

使用分治策略来把一个大数组分为两个小数组。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

实现策略

1、从数列中挑出一个元素，称为 “基准”;

2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；

3、递归地把小于基准值元素的子数组和大于基准值元素的子数组排序；

时间复杂度：

最好情况：数组升序排列，时间复杂度为：O(n)

最坏情况：数组降序排列，时间复杂度为：O(n²)

空间复杂度

O(n2)

代码

//快速排序public static void quickSort(int[] arr, int left, int right) { if (left < right) { int pivot = partition(arr, left, right); quickSort(arr, left, pivot - 1); quickSort(arr, pivot + 1, right); }}//分区private static int partition(int[] arr, int left, int right) { int pivot = arr[left]; while (left < right) { while (left < right && arr[right] >= pivot) { right--; } arr[left] = arr[right]; while (left < right && arr[left] <= pivot) { left++; } arr[right] = arr[left]; } arr[left] = pivot; return left;}//测试算法public static void main(String[] args) { int[] arr = {109, 108, 107, 106, 105, 104, 103, 102, 1011}; quickSort(arr, 0, arr.length - 1); for (int i : arr) { System.out.println(i); }}