Quick Sort 快速排序

题目

快速排序，就是选定一个目标数flag，然后将这个数组中，比这个数小的放左边，比这个数大的放右边。这样形成两个数组，继续迭代，一直到这个数组只剩下0 个 或 1 个元素，直接返回。

解析

我们希望得到一个界限，在这个界限左边，是比 flag 小的数字，这个界限右边，是比 flag 大的数字。所以需要两个指针指向头和尾，然后通过某种移动方式，当两个指针相遇时，相遇的位置，就是 flag 数分离的位置，我们就将数组分为两个了。
假设我们选定 flag 为第一个元素，这样我们空出了第一个字符，我们希望找到一个比 flag 小的数放在这里，我们应该从后往前找，这样移动之后，后边会空出一个数，然后我们再从前往后找一个小的数，数字放到后边空出来的位置。

更一般的，我们可以通过交换来达到这个目的。即从左往右，找到一个想交换的数，从右往左，找到一个想交换的数。交换。
由于一般我们选择第一个数作为 flag 。所以我们希望将 第一个数交换到右边，也就是说，我们希望和 flag 相同的数位于右侧。

1. 从左往右，找到第一个数作为左交换数
2. 从右往左，找到一个比 flag 小的数，作为交换数
3. 一旦找到，即交换，然后步进直到两个指针相遇
4. 当左指针一直没找到大于等于 flag 的数时，说明左边的数都比 flag 小，此时左右相遇，而此时，右边的数都比 flag 大。说明是边界了。
5. 当左指针找到一个数，而右指针没找到，相遇时，这个数比 flag 大，交换这个数和 flag。

所以无论如何，当循环结束时，两个指针相遇的位置，就是 flag 应该所在的位置。

快速排序有很多细节需要处理。
如果我们选定 0 为坐标，如果我们不想移动这个元素，那么需要先移动 j 再移动 i，这样两数相遇时。指针会落到分区的左边界，也就是说，左边界的数都是小于等于 0 元素的。这样最终交换不影响结果。

伪代码

for i<j
  for i< j && nums[j] >= nums[0]
    i++
  for i<j && nums[i] < nums[0]
    j--
  nums[i],nums[j] = nums[j], nums[i]
nums[j],nums[0] = nums[0],nums[j]

代码

func quicksort(nums []int) {
    if len(nums) == 0 || len(nums) == 1 {
        return
    }
    flag := partition(nums)
    quicksort(nums[:flag])
    quicksort(nums[flag+1:])
}

func partition(nums[]int) int {
    i:=0
    j:=len(nums)-1
    for i<j{
        for i<j && nums[j] > nums[0] {
            j--
        }
        for i<j && nums[i] <= nums[0] {
            i++
        }
        nums[i],nums[j] = nums[j],nums[i]
    }
    nums[j],nums[0] = nums[0], nums[j]
    return i
}