快速排序

时间复杂度：O(n log n)

• 最好：O(n log n)
• 最坏：O(n^2)

空间复杂度：O(log n)

原理
快速排序（Quick Sort）是对冒泡排序的改进。

快速排序的基本思想是：通过一趟排序，将序列中的数据分割为两部分，其中一部分的所有数值都比另一部分的小；然后按照此种方法，对两部分数据分别进行快速排序，直到参与排序的两部分都有序为止。

实现
将序列划分为如上所述的两部分：

1. 需要在开始的时置一个参考值，通过与参考值的比较来划分数据；
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面；

3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

   // 快速排序
   func QuickSort(slice []int) []int {
    if len(slice) < 2 {
        return slice
    }
    temp := slice[0]
    left, right := 0, len(slice)-1
    for left < right {
        for left < right && slice[right] <= temp {
            right--
        }
        slice[left] = slice[right]
        for left < right && slice[left] >= temp {
            left++
        }
        slice[right] = slice[left]
    }
    slice[left] = temp
    QuickSort(slice[:left])
    QuickSort(slice[left+1:])
    return slice
   }