总结
基于比较的排序（从小到大排序）
冒泡排序
GO实现
func MySort( arr []int ) []int {
// 冒泡
// 大的往后冒
for i := 0; i arr[j + 1]{
arr[j], arr[j + 1] = arr[j + 1], arr[j]
}
}
}
return arr
}
另一种实现
func MySort( arr []int ) []int {
// 小的往前冒
for i := 0; i i ; j-- {
if arr[j] 选择排序
GO实现
func MySort( arr []int ) []int {
// 选择排序
// 不稳定：5 5 1
for i := 0; i arr[j] {
minPoi = j
}
}
arr[i], arr[minPoi] = arr[minPoi], arr[i]
}
}
直接插入排序
GO实现
func MySort( arr []int ) []int {
// 稳定：2 2 1
for i := 1; i = 0 && temp 希尔排序（第一个突破n^2的排序算法）
GO实现
func MySort( arr []int ) []int {
// 不稳定：相同元素不在同一组，则无法保证相对顺序
var shell func(int, int)
shell = func(begin, step int) {
for i := begin + step; i = begin && temp 0 {
for i := 0; i 归并排序
GO实现
func MySort( arr []int ) []int {
// 2 2 1 稳定
if len(arr) 快速排序
GO实现
func MySort( arr []int ) []int {
if len(arr) cur {
arr[right] = arr[left]
isRight = !isRight
}else{
left++
}
}
}
arr[left] = cur
quicSort(begin, left - 1)
quicSort(left + 1, end)
}
quicSort(0, len(arr) - 1)
}
堆排序
有两种建堆方式：从顶向下O(n)(已知堆的大小)，从底向上O(nlogn)（堆的大小动态调整）
参考博文：【堆/排序】堆排序的两种建堆方法
GO实现
func MySort( arr []int ) []int {
if len(arr) end {
break
}
max := arr[left]
if right max{
max = arr[right]
}
if max > arr[start] {
if max == arr[left] {
arr[start], arr[left] = arr[left], arr[start]
start = left
} else {
arr[start], arr[right] = arr[right], arr[start]
start = right
}
}else{
break
}
}
}
end := len(arr) - 1
// 先建堆
// end的父节点是：(end - 1)/2
for i := (end - 1)/2; i >= 0; i-- {
down(i, end)
}
fmt.Println(arr[end])
// 再排序
for end >= 1 {
arr[0], arr[end] = arr[end], arr[0]
end--
down(0, end)
}
}
非比较排序（基于桶排序思想）
计数排序（适合数据跨度小，重复数据多的情况）
相当于为每个数字安排一个桶
GO实现
func MySort( arr []int ) []int {
if len(arr) v {
minArr = v
}
if maxArr 0 {
arr[cur] = i + minArr
cur++
v--
}
}
}
基数排序（桶排序的变种）
一位一位的来处理数据，桶的数量固定为十个，桶间有序，桶内无序。
有两种处理方式：
- 从最高位到最低位：每个桶内要再进行桶排序
- 从最低位到最高位：只要调用最大数的最高位数次排序就行
GO实现
func MySort( arr []int ) []int {
if len(arr) tips
是不是很疑惑我为什么没写桶排序？
- 要使用桶排序算法，首先要确定桶的数量，这一点就很麻烦
- 由于桶内是无序的，所以往往还需要在桶内调用快排之类的基于比较的排序算法，所以我个人觉得桶排序不能算非比较排序，所以没有写
机房租用，北京机房托管，大带宽租用，IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net
