快速排序是一种高效的排序算法，也是面试中经常会考到的算法题。

快速排序的原理是，首先找到一个分割位pivot把数组分成 独立的 两组，使其中一组的所有数字均大于另一组中的数字，此时pivot在数组中的位置就是它正确的位置。 然后再按此方法对这两组数据分别进行快速排序，整个排序过程可以 递归 进行，最终达到整个数据变成有序 序列。

解法一： 
 func QuickSort(values []int) {
   if len(values) <= 1 {
      return
   }
   mid, i := values[0], 1
   head, tail := 0, len(values)-1
   for head < tail {
      fmt.Println(values)
      if values[i] > mid {
         values[i], values[tail] = values[tail], values[i]
         tail--
      } else {
         values[i], values[head] = values[head], values[i]
         head++
         i++
      }
   }
   values[head] = mid
   QuickSort(values[:head])
   QuickSort(values[head+1:])
}
解法二： 
 func quickSort(nums []int) {
 recursionSort(nums, 0, len(nums)-1)
}

func recursionSort(nums []int, left int, right int) {
if left < right {
pivot := partition(nums, left, right)
recursionSort(nums, left, pivot-1)
recursionSort(nums, pivot+1, right)
}
} 
 //确定分割位
func partition(nums []int, left int, right int) int {
for left < right {
for left < right && nums[left] <= nums[right] {
right--
}
if left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
}
for left < right && nums[left] <= nums[right] {
left++
}
if left < right {
nums[left], nums[right] = nums[right], nums[left]
right--
}
}
return left
}

快速排序的平均时间复杂度也是O( nlogn )，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归， 平均递归次数是log(n)次，所以平均空间复杂度是O(log(n))。最坏的情况是O(n)（初始是逆序的情况）。