Golang 快速排序

思路

data = [3 2 6 1  2 7]

middle = 3

? 2 6 1 2 7

//第一轮:
// data[i] = 2
// middle = 3
if data[i] < middle {
    //则与头指针进行交换
    //然后 i++
    //头指针也 ++
    //即头指针一直指向那个 ？的值.
} 

第二轮时
data[i] = 6
head = 1
此时就会进入 else 那个分支了：

将它从尾开始交换后变成：

2 ? 7 1 2 6

变化：
head 不变：因为头是在?那里，位置 没有交换过，则不用改变
i 不变： 因为它与尾的值交换了，但原来的那个尾的值还没有比较，所以，还是从 i 的位置开始比较
tail -- ： 因为尾那里已经将元素交换过去了，那个元素就不用再进行比较了


第一次完成后，进行递归，递归前，要将原来的 miidle 的值保存到 ? 的位置(data[head])

然后开始递归

快速排序

package main

import "helper/number"
import "helper/time"
import "fmt"

func main() {
	//待排序的数据
	data := number.GenerateInt(29, 1000)
	fmt.Printf("before %v\n", data)
	start := time.CurrentMillis()
	quitSort(data)
	fmt.Printf("after %v\n", data)
	fmt.Printf("quitSort %v ms", time.CurrentMillis()-start)
}

func quitSort(data []int) {
	if len(data) <= 1 {
		return
	}

	//假设第一个元素为 0，并且假设为"中值"
	middleValue := data[0]

	//这个是索引值了，不是表示大小了, 头尾指针
	head, tail := 0, len(data)-1

	//
	i := 1

	for head < tail {
		//如果下一个元素，比中值小，那从头开始交换位置
		if data[i] < middleValue {
			data[head], data[i] = data[i], data[head]

			//因为已经交换了，头指针向前移动一个
			head++
			//则进行下一个元素比较
			i++
		} else {
			//这个表示下一个元素比中值大，则从 尾开始交换
			data[tail], data[i] = data[i], data[tail]
			tail--
		}
	}

	data[head] = middleValue
	quitSort(data[:head])

	quitSort(data[head+1:])

}