今天想试试自己的golang功底，所以想用go实现各种快排，假设我们的测试例子是这样的：
// 测试代码
import (
"fmt"
"math/rand"
)
func main() {
// 测试数据随机产生100以内的10个数
data := []int{}
for i := 0; i < 10; i++ {
data = append(data, rand.Intn(100))
}
// 调用各种快排函数
xxx_sorting(data)
// 打印结果
for i := 0; i < len(data); i++ {
fmt.Printf("%d,", data[i])
}
fmt.Printf("\n")
}随机函数产生的数字可能存在重复，但是对于快排来说无所谓。我们先从最原始的冒泡法开始：
// 冒泡法
func bubble_sorting(data []int) {
// 为什么遍历长度是len(data)-1，因为冒泡法采用的是左右两个元素比较的方法
// 就剩下一个元素没有其他元素比较了，也就是有序的
for i := 0; i < len(data)-1; i++ {
// 从小到大排序
for j := 0; j < len(data)-i-1; j++ {
// 如果左边比右边大就交换
if data[j] > data[j+1] {
// 这种写法对于C/C++程序猿来说不可想象
data[j], data[j+1] = data[j+1], data[j]
}
}
}
}其实冒泡法还有很多改良的方法，我更推崇的是这种方法：无序的数可能部分是有序的，尤其是冒泡了几次后，剩余部分很有可能部分有序。所以我的改良方法是：
// 改良的冒泡法，用一个变量记录从第0个元素开始连续多少个元素是有序的
func bubble_sorting(data []int) {
// 用一个变量记录从0开始的元素已经连续几个是有序的，这里的有序指的不是全局的序
// 是在ordered_size范围内是有序的，这样这个范围里的元素就不用在重复比较了，默认肯定是0
ordered_size := 0
// 这里和普通冒泡法是一样的
for i := 0; i < len(data)-1; i++ {
// 因为前面连续ordered_size个元素已经有序了，我们只要从有序的最后一个元素开始就行了
// 这个循环结束的位置len(data)-i-1，-1的原因是比较的是data[j]和data[j+1]
for j := ordered_size; j < len(data)-i-1; j++ {
// 这块和普通的冒泡没什么区别
if data[j] > data[j+1] {
data[j], data[j+1] = data[j+1], data[j]
// 此处判断的目的是当前的元素还在有序范围内，由于这个元素已经和后面的元素交换了
// 后面的元素很可能比ordered_size - 1那个元素还要小，所以连续有序的数量就要-1
// 因为连续有序的数量最小就是0，所以做一个判断，避免出现负数
// ordered_size == j目的是判断当前索引是否还在连续有序的范围
if ordered_size == j && ordered_size > 0 {
ordered_size--
}
// 当前位置已经超出了连续有序范围就不用关心，如果没有，那么当前元素和前面的元素是有序的
} else if ordered_size == j {
ordered_size++
}
}
}
}上面的冒泡改良法在排序过程中前面元素有序加速效果比较明显，如果中间某些元素有序那就没什么效果了。有人肯定会说，那就把刚交换的元素放到有序的位置上不就可以了么，这就是我们接下来介绍的直接插入法。直接插入法的思想如下图：
初始状态有序的元素数量肯定只有1个 ，通过遍历剩余的元素，然后按序插入到制定位置就可以了。代码实现如下：
// 直接插入法
func insert_sorting(data []int) {
// 第一个元素已经有序了，从第二个元素开始遍历
for i := 1; i < len(data); i++ {
// 倒着比较，直到找到合适位置
for j := i; j > 0; j-- {
// 如果比左面的元素大，那就算找到位置了
if data[j-1] < data[j] {
break
}
// 如果比左边的元素小，那么就要交换了
data[j-1], data[j] = data[j], data[j-1]
}
}
}如果说直接插入法还要面临大量的交换的话，选择排序可能是更好的选择，别小看交换数据，涉及到两次的数据读取和存储，如果都是内存数据，数据的访问开销也要考虑进来。选择排序的思想如下图所示：
在无序的元素内选择最小的放在有序元素的后面，此时有序元素数量的初始值为0，代码实现如下：
// 选择排序
func select_sorting(data []int) {
// 因为有序元素数量是0，初始状态所有元素都是无序的
for i := 0; i < len(data)-1; i++ {
// 假设第i个元素就是最小的
k := i
// 寻找最小的元素
for j := i + 1; j < len(data); j++ {
// 每次只记录索引，所以没有交换数据
if data[j] < data[k] {
k = j
}
}
// 只有到最后才交换一次数据，而且还做了判断，如果第i个元素就是最小的，也就不用交换了
if k != i {
data[k], data[i] = data[i], data[k]
}
}
}前面介绍的这些排序方法复杂度都在n(n-1)/2，接下来我们实现一种时间复杂度在nlog(n)的算法，叫做归并法。归并法是将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并法的思想如下图所示(图片非原创，引用自互联网)：
代码实现为：
// 归并排序法，因为用了递归，所以需要传入起始位置，结束为止，以及缓冲，这个缓冲是和data一样大小
func merge_sorting(data []int, start int, end int, buf []int) {
// 如果元素数量超过2个，那就在继续二分
if start+1 < end {
// 二分
mid := (start + end) / 2
// 递归
merge_sorting(data, start, mid, buf)
merge_sorting(data, mid+1, end, buf)
// 合并两个有序的数组
merge(data, start, end, mid, buf)
// 2个或者1个，只有一种条件就是左面的比右边的大才需要交换，其他条件都不需要操作
} else if data[start] > data[end] {
data[start], data[end] = data[end], data[start]
}
}
// 合并有序数组
func merge(data []int, start int, end int, mid int, buf []int) {
// index是合并后数组的索引，left是左半部分有序数组的索引，right是右半部分有序数组的索引
index, left, right := start, start, mid+1
for {
// 假设左边的是最小的
min := left
if data[left] <= data[right] {
left++
// 如果是右半部分的最小
} else {
min = right
right++
}
// 二者最小的元素放到缓冲中
buf[index] = data[min]
index++
// 一旦有哪个半部分数组提前没有元素了就提前结束了
if left > mid || right >= end {
break
}
}
// 把剩下的左半部分合并到缓冲中
for i := left; i <= mid; i++ {
buf[index] = data[i]
index++
}
// 把剩下的右半部分合并到缓冲中
for i := right; i <= end; i++ {
buf[index] = data[i]
index++
}
// 把排好序的缓冲中的数据拷贝到数据内存中
for i := start; i <= end; i++ {
data[i] = buf[i]
}
}归并法的确定是需要O(n)的临时空间，同时还要搬移2O(n)次数据，而大多数标准库都支持的快速排序的临时空间只有O(1)，搬移次数也只有O(n)，时间复杂度也同样是nlog(n)。快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
如何做到一部分数据都比另一部分数据小？只要在序列中选择一个数据，比这个数据小的放在左边，比这个数据大的放在右边。在选择数方面有很多方法，可以选择第一个，可以选择中间对的那个，也可以随机选择，我们的实现选择第一个数作为基准。实现代码如下：
// 快速排序实现，由于要二分递归，所以要传入每次排序的起始和结束的索引
func quick_sorting(data []int, start, end int) {
if (start < end) {
// 获取基准值
base := data[start]
// 临时变量，左右索引
left := start
right := end
// 进入循环
for left < right {
// 由于左边的(第0个)被取走当成基准值，所以在左边就留下一个洞，用于存储比基准小的值
// 所以先从右边找，找到第一个比基准值小的
for left < right && data[right] >= base {
right--
}
// 找到了比基准值小的，那就把这个值填入左边的洞，做索引要++
if left < right {
data[left] = data[right]
left++
}
// 因为上面的操作让右边留了一个洞，开始从左边找比基准值大的
for left < right && data[left] <= base {
left++
}
// 找到比基准值大的再次把右边洞填上，并且在左边又留了一个洞
if left < right {
data[right] = data[left]
right--
}
}
// 把基准值填入到洞中，这就是本应该他所在的位置
data[left] = base
// 继续分两组递归排序，注意此时基准值已经不用参与排序了
quick_sorting(data, start, left - 1)
quick_sorting(data, left + 1, end)
}
}