最近像在看闲书一样在看一本《啊哈！算法》
当时在amazon上面闲逛挑书，看到巨多人推荐这本算法书，说深入浅出简单易懂便买来阅读。实际上作者描述算法的能力的确令人佩服。就当复习常用算法吧。
后面会依次纪录一下我觉得有意思的常用算法使用，这次就是快排。
快速排序简介：
快排的中心思想还是二分法，通过partition算法，先将需要排序的数组分为两个部分，再用递归的思想反复这个过程。最后将排序好的最小单元再依次组装起来获得最后的数据。快排的平均时间复杂度是O(nlogN)，最糟糕的情况是O(N平方)。
Partition算法：
partition算法是一种分类算法，简单来说就把一个序列分成前后两部分，前一部分都是满足某一条件的元素，后一部分都是不满足该条件的元素。最著名的应用可能就是快速排序中的partition了。我们先找出一个元素，然后以该元素为基准点将小于他的全部放置到一边，将大于他的数全部放置到另外一边。最后返回pivot索引位置。这里我们默认使用数组的第一个数作为pivot
下面来看快速排序中partition的实现：
func partition(left int, right int, list []int) (int) {
i := left
j := right
temp := list[left]
for i != j {
for i < j && list[j] >= temp {
j--
}
for i < j && list[i] <= temp {
i++
}
if i < j {
list[i], list[j] = list[j], list[i]
}
}
list[left], list[i] = list[i], list[left]
return i
}
我们接收数组，左起始点，右结束索引作为参数。
默认将数组的第一个数作为索引点，然后将小于他的数放置在左边，将大于他的数放置在右边。
快速排序：
通过递归partition函数我们就能始终将数分成左右两边，最后再合并起来就可以了。
所以实际快速排序只是在partition算法的基础上使用递归法。最后获取结果。上面的partition算法我使用了两根指针同时从左右两边进行扫描。把扫描到的左右两个数调换位置，从而二分效率。
完整的代码：
func quickSort(left int, right int, list []int) {
if left >= right {
return
}
i := left
j := right
temp := list[left]
for i != j {
for i < j && list[j] >= temp {
j--
}
for i < j && list[i] <= temp {
i++
}
if i < j {
list[i], list[j] = list[j], list[i]
}
}
list[left], list[i] = list[i], list[left]
quickSort(left, i, list)
quickSort(i+1, right, list)
return
}
Reference:
《啊哈！算法》-> 啊哈磊著