排序算法
排序算法有很多种，在大部分时候只需要调用语言中封装好的排序算法（大部分都是快速排序）即可，但这些排序方法都可以尝试理解下，也是算法的基础，下文不会给出每个算法的具体实现，而只给出理解总结以及相关的链接。
- 冒泡排序：多次遍历，每次遍历交换相邻元素
- 选择排序：多次遍历，每次寻找最小值然后交换到左侧
- 插入排序：多次遍历，取出某个数，和它左侧的数分别比较，插入到合适的位置
- 合并排序：多次排序，每次对定量且相邻的元素进行排序，也是分而治之
- 计数排序：适用于大量且分散在指定范围内的元素，例如10000个数据，但是每个数据都在0-10之间，这样只需要做11次计数就可以完成排序
- 桶排序：类似于计数排序，只是多个计数整合成一个桶，桶内的排序任务就减轻了很多
- 基数排序：类似于桶排序，但根据键值的每位数字来分配桶，对于十进制来说无论多少数据都是十个桶（0-9），但需要多次的排序
- 随机快速排序：随机获得基准值，然后和快速排序一致
- 快速排序：寻找一个基准值，然后分而治之，最后直接顺序完成
func quickSort(arr []int) []int {
return _quickSort(arr, 0, len(arr)-1)
}
func _quickSort(arr []int, left, right int) []int {
if left < right {
partitionIndex := partition(arr, left, right)
_quickSort(arr, left, partitionIndex-1)
_quickSort(arr, partitionIndex+1, right)
}
return arr
}
func partition(arr []int, left, right int) int {
pivot := left
index := pivot + 1
for i := index; i <= right; i++ {
if arr[i] < arr[pivot] {
swap(arr, i, index)
index += 1
}
}
swap(arr, pivot, index-1)
return index - 1
}
func swap(arr []int, i, j int) {
arr[i], arr[j] = arr[j], arr[i]
}