数据结构常见的排序算法（golang版）

排序算法是比较基础的内容，在工作过程中可能使用的场景不多（现存的语言框架已经实现了常用数据类型的排序算法，一般会根据
使用场景选择不同的排序策略），但对个人的代码逻辑锻炼却有帮助。

排序算法分类

十种常见排序算法可以分为两大类：

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

算法复杂度：

1、交换排序

• 冒泡排序

  func bubbleSort(array []int) []int {
    length := len(array)
    for i := 0; i < length-1; i++ {
        var hasSort bool
        for j := i; j < length-1-i; j++ {
            if array[j+1] < array[j] {
                hasSort = true
                array[j+1], array[j] = array[j], array[j+1]
            }
        }
        if !hasSort {
            break
        }
    }
    return array
  }

• 快速排序

2、插入排序

• 简单插入排序

  func insertSort(array []int) []int {
    length := len(array)
    for i := 1; i < length; i++ {
        for j := i; j >= 1; j-- {
            if array[j] < array[j-1] {
                array[j], array[j-1] = array[j-1], array[j]
            }
        }
    }
    return array
  }
  

• 希尔排序

3、选择排序

• 简单选择排序

  func selectionSort(array []int) []int {
    length := len(array)
    for i := 0; i < length; i++ {
        minIndex := i
        for j := i + 1; j < length; j++ {
            if array[minIndex] > array[j] {
                minIndex = j
            }
        }
        if minIndex == i {
            continue
        }
        array[i], array[minIndex] = array[minIndex], array[i]
    }
    return array
  }

• 堆排序

4、归并排序

• 二路归并排序

• 多路归并排序

5、计数排序

6、桶排序

7、基数排序

参考：https://www.cnblogs.com/onepixel/articles/7674659.html