什么是快速排序
快速排序简单的说就是选择一个基准，将比起大的数放在一边，小的数放到另一边。对这个数的两边再递归上述方法
时间复杂度
| 时间复杂度（平均） | 时间复杂度（最坏) | 时间复杂度（最好) | 空间复杂度 | 稳定性 | 复杂性 |
|---|---|---|---|---|---|
| O(nlog2n) | O(n^2 ) | O(nlog2n) | O(nlog2n) | 不稳定 | 较复杂 |
基本思想
- 1、先从数列中取出一个数作为基准数
- 2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
- 3、再对左右区间重复第二步，直到各区间只有一个数
/************************************************************
** @Description: quickSort
** @Author: george hao
** @Date: 2018-05-08 09:08
** @Last Modified by: george hao
** @Last Modified time: 2018-05-08 09:08
*************************************************************/
package main
import "fmt"
func quickSort(arr []int, start, end int) {
if start >= end {
return
}
i, j := start, end
//选择中间作为基准值
mid := (start + end) / 2
key := arr[mid]
//fmt.Println("基准值：", mid, key)
for i <= j {
for arr[i] < key {
i++
}
for arr[j] > key {
j--
}
if i <= j {
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
}
//fmt.Println(arr)
if start < j {
quickSort(arr, start, j)
}
if end > i {
quickSort(arr, i, end)
}
}
func main() {
arr := []int{3, 7, 9, 8, 38, 93, 12, 222, 45, 93, 23, 84, 65, 2}
quickSort(arr, 0, len(arr)-1)
fmt.Println(arr)
}
