总结
基于比较的排序（从小到大排序）冒泡排序
GO实现
func MySort( arr []int ) []int { // 冒泡 // 大的往后冒 for i := 0; i < len(arr); i++{ for j := 0; j 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] < arr[j - 1]{ arr[j], arr[j - 1] = arr[j - 1], arr[j] } } } return arr}选择排序
GO实现
func MySort( arr []int ) []int { // 选择排序 // 不稳定：5 5 1 for i := 0; i < len(arr); i++{ minPoi := i for j := i + 1; j 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 < len(arr); i++ { if arr[i] = 0 && temp < arr[j] { arr[j + 1] = arr[j] j-- } arr[j + 1] = temp } }}希尔排序（第一个突破n^2的排序算法）
GO实现
func MySort( arr []int ) []int { // 不稳定：相同元素不在同一组，则无法保证相对顺序 var shell func(int, int) shell = func(begin, step int) { for i := begin + step; i < len(arr); i += step { if arr[i] = begin && temp 0 { for i := 0; i < step; i++{ shell(i, step) } step /= 2 }}归并排序
GO实现
func MySort( arr []int ) []int { // 2 2 1 稳定 if len(arr) < 2 { return arr } mid := len(arr)/2 left := arr[:mid] right := arr[mid:] var merge func([]int, []int) []int merge = func(left []int, right []int)(ans []int){ i := 0 j := 0 for i < len(left) && j < len(right){ if left[i] <= right[j] { ans = append(ans, left[i]) i++ }else{ ans = append(ans, right[j]) j++ } } ans = append(ans, left[i:]...) ans = append(ans, right[j:]...) return } return merge(MySort(left), MySort(right))}快速排序
GO实现
func MySort( arr []int ) []int { if len(arr) < 2 { return arr } // 2,2,1 不稳定 var quicSort func(int, int) quicSort = func(begin, end int) { if(end - begin <= 0){ return } cur := arr[begin] left := begin right := end isRight := true for left != right { if isRight { if arr[right] 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) < 2 { return arr } // 不稳定 2 2 1 // 从小到大排序，用大顶堆，每次把根节点放最后，然后end - 1 var down func(int, int) down = func(start int, end int){ for start 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) < 2 { return arr } // 找到最大值 maxValue := -1 for _, v := range arr { if maxValue < v { maxValue = v } } // 找到最高位 maxBit := 0 for maxValue != 0 { maxValue /= 10 maxBit++ } // fmt.Println(maxBit) // 声明十个桶 buckets := make([][]int, 10) base := 1 for i := 0; i < maxBit; i++ { for _, v := range arr { buckets[(v / base) % 10] = append(buckets[(v/base)%10], v) } index := 0 for j, bucket := range buckets { if len(bucket) == 0 { // fmt.Println(len(bucket)) continue } for _, v := range bucket{ arr[index] = v index++ } // 清空桶 buckets[j] = buckets[j][:0] } base *= 10 } return arr}tips
是不是很疑惑我为什么没写桶排序？
- 要使用桶排序算法，首先要确定桶的数量，这一点就很麻烦
- 由于桶内是无序的，所以往往还需要在桶内调用快排之类的基于比较的排序算法，所以我个人觉得桶排序不能算非比较排序，所以没有写