Go语言实现十大排序算法，讲解超详细

大家好，我是王不错。（欢迎关注我的个人公众号：程序员王不错）

今天为大家介绍排序算法。排序算法是算法领域的基础，可以说是每个程序员都必须熟练掌握的知识。

本文将最常见的十大排序算法进行了完整的总结，相信看完这篇文章，你对排序算法的掌握将会更进一步。

要说明的是，本文的算法实现都是由Go语言实现的，你可以根据自己的习惯用不同语言实现。

01 冒泡排序

冒泡排序是一种比较简单的排序算法，它的原理是：

从左到右遍历数组，相邻元素两两进行比较。每次比较完一轮，就会找到数组中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。

以从小到大排序为例，第一轮比较后，所有数中最大的那个数就会浮到最右边；第二轮比较后，所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较，最后实现从小到大排序。

由于这个排序算法较为简单，就不需要再赘述了。

直接看代码：

func bubbleSort(nums []int) []int {
  numsLen := len(nums)
  if numsLen <= 1 {
    return nums
  } 
  for i := 0; i < numsLen; i++ {
    for j := 0; j < numsLen-i-1; j++ {
      if nums[j] > nums[j+1] {
        nums[j], nums[j+1] = nums[j+1], nums[j]
      }
    }
  }
  return nums
}

这个算法的时间复杂度是O(n^2)，空间复杂度是O(1)。

02 选择排序

选择排序的原理是，首先在开始的时候遍历整个数组，找到序列中的最小元素，然后将这个元素与第一个元素交换，这样最小的元素就放到了它的最终位置上了。

然后，从第二个元素开始遍历，找到剩下的n-1个元素中的最小元素，再与第二个元素进行交换。

以此类推，直到最后一个元素放到了最终位置。

同样，选择排序也不难理解，还是直接看代码：

func selectSort(nums []int) []int {
  numsLen := len(nums)
  if numsLen < 2 {
    return nums
  }
  for i := 0; i < numsLen; i++ {
    min := i
    for j := i+1; j < numsLen; j++ {
      if nums[j] < nums[min] {
        min = j
      }
    }
    nums[min], nums[i] = nums[i], nums[min]
  }
  return nums
}

这个算法的时间复杂度也是O(n^2)。

03 插入排序

插入排序，也叫直接插入排序。

它的原理是，将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。

在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面的有序表进行待插入位置查找，并进行移动。

插入排序的代码如下：

func insertSort(nums []int) []int {
  numsLen := len(nums)
  if numsLen < 2 {
    return nums
  }
  for i := 1; i < numsLen; i++ {
        // 当前值的前一个元素的下标
    preIndex := i - 1
        // 当前值
    nowNums := nums[i]
    for nums[preIndex] > nowNums {
      nums[preIndex+1] = nums[preIndex]
      if preIndex == 0 {
        preIndex--
        break
      }
      preIndex--
    }
    nums[preIndex+1] = nowNums
  }
  return nums
}

这个算法的时间复杂度仍是O(n^2)，空间复杂度是O(1)。

下面介绍几个加快排序的算法。

04 快速排序

快速排序要求我们选择一个基准，根据这个基准为原数组分组，比基准大的一组，比基准小的一组，再重复递归地进行快速排序，重新合并每组排序后的序列，即为排好序的序列。

快速排序需要我们先理解递归的思想，代码如下：

func quickSort(nums []int) []int {
  numsLen := len(nums)
  // base case
  if numsLen < 2 {
    return nums
  }
  pivot := nums[0]
  var low, mid, high []int
  for i := 1; i < numsLen; i++ {
    if nums[i] < pivot {
      low = append(low, nums[i])
    } else if nums[i] == pivot {
      mid = append(mid, nums[i])
    } else {
      high = append(high, nums[i])
    }
  }

  low, high = quickSort(low), quickSort(high)
  res := append(append(low, mid...), high...)
  return res
}

这个算法的时间复杂度是O(nlogn)，空间复杂度为O(logn)。

05 归并排序

归并排序是采用分治法的一个典型的排序算法，将已有序的子序列合并为一个完全有序的序列。

归并排序的过程是：首先将序列拆分成子序列，然后对子序列进行排序，最后将排序好的子序列合并，就得到了一个有序的序列。

func mergeSort(nums []int) []int {
  // base case
  if len(nums) < 2 {
    return nums
  }
  // 1、拆分
  mid := len(nums) / 2
  leftArray, rightArray := mergeSort(nums[:mid]), mergeSort(nums[mid:])
  // 2、合并
  return merge(leftArray, rightArray)
}

func merge(list1, list2 []int) []int {
  i, j := 0, 0
  var tmp []int
  for i < len(list1) && j < len(list2) {
    if list1[i] <= list2[j] {
      tmp = append(tmp, list1[i])
      i++
    } else {
      tmp = append(tmp, list2[j])
      j++
    }
  }
  if len(list1) == i {
    tmp = append(tmp, list2[j:]...)
  } else {
    tmp = append(tmp, list1[i:]...)
  }
  return tmp
}

时间复杂度是O(nlogn)，空间复杂度是O(1)。

06 堆排序

先来介绍一下什么是堆？

堆是一种近似完全二叉树的数据结构，可以分为大根堆，小根堆。

大根堆：每个节点的值都大于或等于他左右孩子节点的值。

小根堆：每个节点的值都小于或等于他左右孩子节点的值。

堆排序就是基于这种结构而产生的一种排序算法。

接着我们来看一下堆排序的过程：

假设我们想得到一个升序序列，那么就需要借助大根堆这种数据结构。

1.将待排序序列构造成一个大根堆，此时，整个数组的最大值就是堆结构顶端的根节点。

2.将堆根节点的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序序列个数为n-1。

3.将剩余的n-1个数再构造成一个大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组。

最后，我们还需要了解如何构造一个大根堆？

构造大根堆，要从堆的最后一个叶子结点起，从后往前调整，每次调整，将叶子结点和根节点中的最大值作为根节点，调整到最后，便构造成了一个大根堆。

下面看上述过程的代码。

// 堆化
func heapify(nums []int, n int, i int) {
  /* 
    n: 数组长度
    i: 待维护节点的下标，即不满足大根堆定义的节点下标
  */
  largest := i
  lson := i * 2 + 1;
  rson := i * 2 + 2;
  if lson < n && nums[lson] > nums[largest] {
    largest = lson
  }
  if rson < n && nums[rson] > nums[largest] {
    largest = rson
  }
  // 需要调整
  if largest != i {
    nums[largest], nums[i] = nums[i], nums[largest]
    // 继续递归维护下一个节点
    heapify(nums, n, largest)
  }
}

func heapSort(nums []int) []int {
  n := len(nums)
  // 1、构造堆
  // 从最后一个叶子结点起，从后往前调整构造堆
  for i := (n-1-1)/2; i >= 0; i-- {
    heapify(nums, n, i)
  }
  // 2、交换堆顶元素和最后一个元素, 堆长减一，再对堆顶元素维护堆结构
  for i := n-1; i > 0; i-- {
    nums[i], nums[0] = nums[0], nums[i]
    heapify(nums, i, 0)
  }
  return nums
}

维护堆性质(heapify)的时间复杂度是O(logN)，因为一个二叉树的高度为O(logN)，建堆过程的时间复杂度是O(N)。

综上，算法的时间复杂度为O(NlogN)。

07 希尔排序

希尔排序是插入排序的一种，也叫缩小增量排序，是直接插入排序算法的一种更高效的改进版本。

希尔排序的原理是：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序的过程如下：

增量表示整个数组中的元素以它为跨度被分在一组中，增量为几数组就会被分成几组。

来看代码：

func shellSort(nums []int) []int {
  for gap := len(nums) / 2; gap > 0; gap /= 2 {
    // 直接插入排序
    for i := gap; i < len(nums); i++ {
      key := nums[i]
      j := i
      for ; j >= gap && key < nums[j-gap]; j-=gap {
        nums[j] = nums[j-gap]
      }  
      nums[j] = key
    }
  }
  return nums
}

希尔排序的时间复杂度有点不同。它不像其他时间复杂度为O(nlogn)的排序算法那么快，但是要比选择排序和插入排序这种时间复杂度为O(n^2)的排序算法快得多。

08 计数排序

计数排序是一种通过计数而不是比较进行排序的算法，适用于范围较小的整数序列。

它的优势在于在对一定范围内的整数排序时，时间复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。

当然这是一种牺牲空间换取时间的做法。

下面通过排序过程了解计数排序的原理：

计数排序代码：

func countSort(nums []int) []int {
  n := len(nums)
  if n < 2 {
    return nums
  }
  // 寻找数组最大值，为其分配一个长度为max+1值均为0的数组存储计数
  max := nums[0]
  for i := 1; i < n; i++ {
    if nums[i] > max {
      max = nums[i]
    }
  }
  count := make([]int, max+1)
  // 计数
  for i := 0; i < n; i++ {
    count[nums[i]]++
  }
  // 新数组（最终结果存在这）
  // 这里声明数组一定要指定长度为0，不然会直接分配n个空间存储0，追加会在后面追加，结果有问题
  output := make([]int, 0, n)
  for k, v := range count {
    for ; v > 0; v-- {
      output = append(output, k)
    }
  }
  return output
}

这个算法的时间复杂度为O(n+m)，空间复杂度为O(m)，m为数组最大值。

09 桶排序

桶排序类似于计数排序，其思想近乎彻底的分治思想。

原理是将数组按照元素所属范围分到有限数量的桶里，再单独对每个桶排序（可以使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。

代码如下：

func BucketSort(nums []int, bucketNum int) []int {
  // bucketNum：桶数量
  numsLen := len(nums)
  // 确定数组元素范围
  min, max := nums[0], nums[0]
  for i := 0; i < numsLen; i++ {
    if min > nums[i] {
      min = nums[i]
    }
    if max < nums[i] {
      max = nums[i]
    }
  }
  bucket := make([][]int, bucketNum)
  for j := 0; j < numsLen; j++ {
    // 分桶：这里比较复杂，重点是地板除
    n := int(math.Floor(float64(nums[j] - min) / (float64(max - min + 1) / float64(bucketNum))))
    bucket[n] = append(bucket[n], nums[j])
    k := len(bucket[n]) - 2
    for k >= 0 && nums[j] < bucket[n][k] {
      bucket[n][k+1] = bucket[n][k]
      k--
    }
    bucket[n][k+1] = nums[j]
  }
  i := 0
  for p, q := range bucket {
    for t := 0; t < len(q); t++ {
      nums[i] = bucket[p][t]
      i++
    }
  }
  return nums
}

桶排序的时间复杂度为O(n)，是一种线性复杂度的排序算法。

10 基数排序

先来举个例子看一下该算法的排序思路。

假设待排序数组为：

1、我们按照个位将待排序数组分组。

然后按照索引大小取出得到新的数组。

2、我们按照十位将待排序数组分组。

然后按照索引大小取出得到新的数组。

3、我们按照百位将待排序数组分组。

然后按照索引大小取出得到新的数组。

总结一下，基数排序的原理是：依次按照个位、十位、百位...的顺序对待排序数组分组，然后将每一次的分组按照索引大小重新组成新的数组。最后一轮的新数组即为排好序的数组。

基数排序需要注意的是，

1）要先知道数组最大值的位数，假设为n，那么就需要n次分组；

2）下面的算法只能对全为正整数的数组排序。

func BaseSort(nums []int) []int {
  numsLen := len(nums)
  if numsLen < 2 {
    return nums
  }
  // 找最大值
  max := nums[0]
  for i := 1; i < numsLen; i++ {
    if max < nums[i] {
      max = nums[i]
    }
  }
  // 计算最大值的位数
  maxDigit := 0
  for max > 0 {
    max /= 10
    maxDigit++
  }
  // 定义一个桶，分别存储每一位对应的数组中的数
  bucket := [10][]int{}
  for i := 0; i < 10; i++ {
    // 为了防止每一位都一样所以将每个桶的长度设为最大,与原数组大小相同
    bucket[i] = make([]int, numsLen)
  }
  // 定义一个计数数组,计算当前每一位对应有多少个数
  count := [10]int{0}
  // 定义一个除数
  divisor := 1
  // 定义一个位数
  var digit int

  for i := 1; i <= maxDigit; i++ {
    // 分组
    for j := 0; j < numsLen; j++ {
      temp := nums[j]
      digit = (temp / divisor) % 10
      bucket[digit][count[digit]] = temp
      count[digit]++
    }
    // 重排数组
    k := 0
    for m := 0; m < 10; m++ {
      if count[m] == 0 {
        continue
      }
      for n := 0; n < count[m]; n++ {
        nums[k] = bucket[m][n]
        k++
      }
      count[m] = 0
    }
    divisor *= 10
  }
  return nums
}

该算法的时间复杂度为O(m*n)，m为数组长度，n为数组最大值位数。

以上就是对十大常见的排序算法的总结。

除了仔细阅读本文，最重要的是，一边看文章，一边也要动手把代码敲起来；如果你对排序算法不是那么熟悉，最好每天都拿出一点时间敲一遍，毕竟这也算是程序员的一件趁手兵器。

好啦，今天的分享就到这里。

我是程序员王不错，如果文章内容有帮助到你，就点个“关注”吧~