常用排序算法的Golang实现

Golang 算法
Golang
发布日期:   2022-06-28
更新日期:   2022-07-27
文章字数:   4.9k
阅读时长:   19 分
阅读次数:  

常用排序算法的Golang实现

在实际生活中，经常会涉及到数字排序的问题，如何快速排序，人们就研究了许多的算法，下面就将常用的算法进行总结：

分类

根据排序顺序分类：

1 .插入类排序：直接插入排序和希尔排序

2 .选择类排序：直接选择排序和堆排序

3.交换类排序：冒泡排序和快速排序

4.特殊类排序：并归排序

根据算法稳定性分类：
稳定性概念

定义：能保证两个相等的数，经过排序之后，其在序列的前后位置顺序不变。（A1=A2，排序前A1在A2前面，排序后A1还在A2前面）

意义：稳定性本质是维持具有相同属性的数据的插入顺序，如果后面需要使用该插入顺序排序，则稳定性排序可以避免这次排序。

稳定：

直接插入排序、冒泡排序、并归排序

不稳定：

希尔排序、直接选择排序、堆排序、快速排序

根据时间复杂度分类：

平均时间复杂度在O(n^2)：

直接插入排序、冒泡排序、直接选择排序

平均时间复杂度在O(n^1.5)：

希尔排序

平均时间复杂度在O(nlogn)：

并归排序、堆排序、快速排序

快速了解：

冒泡排序可以说是最差的排序算法。

我们把冒泡排序，直接选择排序，直接插入排序认为是初级的排序算法，其中直接插入排序的性能是综合最好的，一般来说，当排序数组规模 n 较小时，直接插入排序可能比任何排序算法都要快，建议只在小规模排序中使用。

希尔排序是对直接插入排序的改进版本，比直接选择排序和直接插入排序快，且随着规模的递增，这种性能提升越明显。因为算法容易理解，在排序数组中等规模下，我们可以使用它。在非常大的规模下，它的性能也不那么糟糕，但大规模排序还是建议使用以下的高级排序算法。

快速排序，归并排序和堆排序是比较高级的排序算法。

目前被认为综合最好的高级排序算法是快速排序，快速排序的平均用时最短，大多数的编程库内置的排序算法都是它。

堆排序也是一种很快的排序算法，通过维持一棵二叉树，树的根节点总是最大或最小从而可实现排序。

归并排序和快速排序一样使用分治法，递归地先使每个子序列有序，再将两个有序的序列进行合并成一个有序的序列。

糟糕排序算法之一：冒泡排序

原理：循环比较相邻两个数，直到数列从小到大排序

代码实现：

package main

import "fmt"

func BubbleSort(list []int) {
	n := len(list)
	// 在一轮中有没有交换过
	didSwap := false

	// 进行 N-1 轮迭代
	for i := n - 1; i > 0; i-- {
		// 每次从第一位开始比较，比较到第 i 位就不比较了，因为前一轮该位已经有序了
		for j := 0; j < i; j++ {
			// 如果前面的数比后面的大，那么交换
			if list[j] > list[j+1] {
				list[j], list[j+1] = list[j+1], list[j]
				didSwap = true
			}
		}

		// 如果在一轮中没有交换过，那么已经排好序了，直接返回
		if !didSwap {
			return
		}
	}
}

func main() {
	list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	BubbleSort(list)
	fmt.Println(list)
}

冒泡排序交换和比较的次数相加是一个和 N 有关的平方数，所以冒泡排序的最好和最差时间复杂度都是：O(n^2)。也就是说在最好的情况下：对已经排好序的数列进行冒泡排序，只需比较 N 次，最好时间复杂度从 O(n^2)
骤减为 O(n)。

冒泡排序算法是稳定的，因为如果两个相邻元素相等，是不会交换的，保证了稳定性的要求。

糟糕排序算法之二：直接选择排序

原理：通过选择最小的元素，每轮迭代只需交换一次，放到对应位置，与打扑克牌类似。

代码实现：

package main

import "fmt"

func SelectSort(list []int) {
	n := len(list)
	// 进行 N-1 轮迭代
	for i := 0; i < n-1; i++ {
		// 每次从第 i 位开始，找到最小的元素
		min := list[i] // 最小数
		minIndex := i  // 最小数的下标
		for j := i + 1; j < n; j++ {
			if list[j] < min {
				// 如果找到的数比上次的还小，那么最小的数变为它
				min = list[j]
				minIndex = j
			}
		}

		// 这一轮找到的最小数的下标不等于最开始的下标，交换元素
		if i != minIndex {
			list[i], list[minIndex] = list[minIndex], list[i]
		}
	}
}

func main() {
	list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	SelectSort(list)
	fmt.Println(list)
}

比较的次数和冒泡排序一样多，因为扫描过程也是比较的过程，只不过交换的次数减少为每轮 1 次。最佳和最坏时间复杂度仍然是：O(n^2)。选择排序是一个不稳定的排序算法，因为它在交换时将后面的数字排列变化了。

糟糕排序算法之三：直接插入排序

原理：每次把一个数插到已经排好序的数列里面形成新的排好序的数列，以此反复。与打麻将类似。

举个简单例子，有 4 个元素的数列：4 2 9 1，我们使用插入排序：

[]表示排好序

第一轮： [4] 2 9 1 拿待排序的第二个数 2，插入到排好序的数列 [4]
与排好序的数列 [4] 比较
第一轮进行中：2 比 4 小，插入到 4 前

第二轮： [2 4] 9 1 拿待排序的第三个数 9，插入到排好序的数列 [2 4]
与排好序的数列 [2 4] 比较
第二轮进行中： 9 比 4 大，不变化

第三轮： [2 4 9] 1 拿待排序的第四个数 1，插入到排好序的数列 [2 4 9]
与排好序的数列 [2 4 9] 比较
第三轮进行中： 1 比 9 小，插入到 9 前
第三轮进行中： 1 比 4 小，插入到 4 前
第三轮进行中： 1 比 2 小，插入到 2 前

结果： [1 2 4 9]

代码实现：

package main

import "fmt"

func InsertSort(list []int) {
	n := len(list)
	// 进行 N-1 轮迭代
	for i := 1; i <= n-1; i++ {
		deal := list[i] // 待排序的数
		j := i - 1      // 待排序的数左边的第一个数的位置

		// 如果第一次比较，比左边的已排好序的第一个数小，那么进入处理
		if deal < list[j] {
			// 一直往左边找，比待排序大的数都往后挪，腾空位给待排序插入
			for ; j >= 0 && deal < list[j]; j-- {
				list[j+1] = list[j] // 某数后移，给待排序留空位
			}
			list[j+1] = deal // 结束了，待排序的数插入空位
		}
	}
}

func main() {
	list2 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
	InsertSort(list2)
	fmt.Println(list2)
}

时间复杂度和冒泡排序、直接选择排序一样，都是：O(n^2)。因为是从右到左，将一个个未排序的数，插入到左边已排好序的队列中，所以插入排序，相同的数在排序后顺序不会变化，这个排序算法是稳定的。

小结：数组规模 n 较小的大多数情况下，我们可以使用插入排序，它比冒泡排序，选择排序都快，甚至比任何的排序算法都快。

数列中的有序性越高，插入排序的性能越高，因为待排序数组有序性越高，插入排序比较的次数越少。

大家都很少使用冒泡、直接选择，直接插入排序算法，因为在有大量元素的无序数列下，这些算法的效率都很低。

直接插入排序改进型：希尔排序

原理：这是一种分组插入方法，最后一次迭代就相当于是直接插入排序，其他迭代相当于每次移动 n 个距离的直接插入排序，这些整数是两个数之间的距离，我们称它们为增量。

我们取数列长度的一半为增量，以后每次减半，直到增量为1。

x 表示不需要排序的数 
取 d = 6 对 [5 x x x x x 6 x x x x x] 进行直接插入排序，没有变化。 
取 d = 3 对 [5 x x 6 x x 6 x x 4 x x] 进行直接插入排序，排完序后：[4 x x 5 x x 6 x x 6 x x]。 
取 d = 1 对 [4 9 1 5 8 14 6 49 25 6 6 3] 进行直接插入排序，因为 d=1 完全就是直接插入排序了。

越有序的数列，直接插入排序的效率越高，希尔排序通过分组使用直接插入排序，因为步长比 1 大，在一开始可以很快将无序的数列变得不那么无序，比较和交换的次数也减少，直到最后使用步长为 1
的直接插入排序，数列已经是相对有序了，所以时间复杂度会稍好一点。

代码实现：

package main

import "fmt"

// 增量序列折半的希尔排序
func ShellSort(list []int) {
	// 数组长度
	n := len(list)

	// 每次减半，直到步长为 1
	for step := n / 2; step >= 1; step /= 2 {
		// 开始插入排序，每一轮的步长为 step
		for i := step; i < n; i += step {
			for j := i - step; j >= 0; j -= step {
				// 满足插入那么交换元素
				if list[j+step] < list[j] {
					list[j], list[j+step] = list[j+step], list[j]
					continue
				}
				break
			}
		}
	}
}

func main() {
	list := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3, 2, 4, 23, 467, 85, 23, 567, 335, 677, 33, 56, 2, 5, 33, 6, 8, 3}
	ShellSort(list)
	fmt.Println(list)
}

希尔排序不是稳定的，因为每一轮分组，都使用了直接插入排序，希尔排序的时间复杂度大约在这个范围：O(n^1.3)~O(n^2)。

按照之前分析的几种排序算法，一般建议待排序数组为小规模情况下使用直接插入排序，在规模中等的情况下可以使用希尔排序，但在大规模还是要使用快速排序，归并排序或堆排序。

以下三种算法由于代码实现复杂，此阶段仅作原理了解：

2022.7.15更新，将之前没有补完的算法解析补上，接着撸代码…

优秀排序算法之一：并归排序

原理：归并排序先排序较小的数组，再将有序的小数组合并形成更大有序的数组。

归并排序有两种递归做法，一种是自顶向下，一种是自底向上。

自顶向下：

从一个大数组开始，不断地往下切分，从上往下进行递归，直到切分的小数组无法切分了，然后不断地对这些有序数组进行合并。

每次都是一分为二，特别均匀，所以最差和最坏时间复杂度都一样，总的时间复杂度为：O(nlogn)。

自底向上：

从小数组开始排序，不断地合并形成更大的有序数组。时间复杂度和自顶向上归并排序一样，也都是 O(nlogn)

代码实现：使用自顶向下法

package main

import (
	"fmt"
	"math/rand"
)

func mergeSort(data []int) []int {
	//确定数组长度
	length := len(data)
	//长度小于等于一直接返回
	if length <= 1 {
		return data
	}
	//切分数组
	num := length / 2
	//不断切分数组,递归调用函数，直到切分最小
	//小于等于num为左数组
	left := mergeSort(data[:num])
	//大于num为右数组
	right := mergeSort(data[num:])
	//并调用数组排序并合并
	return merge(left, right)
}

//数组合并，对左右数组并入到一个新数组
func merge(left, right []int) (result []int) {
	l, r := 0, 0
	//左右数组不超过原数组
	for l < len(left) && r < len(right) {
		//若左数组最小位小于右数组最小位，则将左数组元素加至数组尾部
		if left[l] < right[r] {
			result = append(result, left[l])
			l++
			//反之，则将右数组元素加至数组尾部
		} else {
			result = append(result, right[r])
			r++
		}
	}
	//因为左右数组的长度会变化，所以(数组[0:]...)表示可变长度的数组
	//将新的左数组全部添加至新数组
	result = append(result, left[l:]...)
	//再将新的右数组全部添加至新数组
	result = append(result, right[r:]...)
	//回参已经定义了就直接return
	return
}

func main() {
	s := make([]int, 0, 16)
	for i := 0; i < 16; i++ {
		s = append(s, rand.Intn(100))
	}
	fmt.Println(s)
	s = mergeSort(s)
	fmt.Println(s)
}

优秀排序算法之二：堆排序

原理：优先队列是一种能完成以下任务的队列：插入一个数值，取出最小或最大的数值（获取数值，并且删除）。

优先队列可以用二叉树来实现，我们称这种结构为二叉堆。

最小堆和最大堆是二叉堆的一种，是一棵完全二叉树（一种平衡树）。

最小堆的性质：

  1. 父节点的值都小于左右儿子节点，且左儿子小于右儿子。
  2. 这是一个递归的性质。
   1
  / \
 2   3
/ \ / \
4 5 6 7

最大堆的性质：

  1. 父节点的值都大于左右儿子节点，且左儿子小于右儿子。
  2. 这是一个递归的性质。
   7
  / \
 5   6
/ \ / \
1 2 3 4

最大堆和最小堆实现方式一样，只不过根节点一个是最大的，一个是最小的。时间复杂度为：O(nlogn)

这个算法实现起来非常抽象，借用菜鸟教程的动态演示可能会更加清晰
动图演示
再配合堆排序详解 食用，理解更加通透

代码实现：

package main

import (
	"fmt"
	"math/rand"
)

//堆排序函数
func heapSort(arr []int) []int {
	arrLen := len(arr)
	//第一步，先构造最大堆
	buildMaxHeap(arr, arrLen)
	//构造最大堆完成后
	for i := arrLen - 1; i >= 0; i-- {
		//交换最大根和尾部子树
		swap(arr, 0, i)
		//长度减一
		arrLen -= 1
		//从根部开始构建最大堆
		heapify(arr, 0, arrLen)
	}
	return arr
}

//构造最大堆函数
func buildMaxHeap(arr []int, arrLen int) {
	for i := (arrLen / 2)-1; i >= 0; i-- {
		heapify(arr, i, arrLen)
	}
}

//核心算法，将大于根的子树进行交换
func heapify(arr []int, i, arrLen int) {
	//左子树下标
	left := 2*i + 1
	//右子树下标
	right := 2*i + 2
	//根下标
	largest := i

	//当arrLen>left和right 时，表示该子树存在
	//并且左子树大于根，则根的下标等于作子树的下标
	if left < arrLen && arr[left] > arr[largest] {
		largest = left
	}
	//在这个时候largest = left,就相当于右子树和左子树进行比较
	//若右子树大于左子树，则根的下标等于右子树的下标
	if right < arrLen && arr[right] > arr[largest] {
		largest = right
	}
	//若上面的if满足，则largest != i，进行元素交换
	if largest != i {
		swap(arr, i, largest)
		//递归变化位置后的子树，保证满足最大堆规则
		heapify(arr, largest, arrLen)
	}
}

//交换函数
func swap(arr []int, i, j int) {
	arr[i], arr[j] = arr[j], arr[i]
}

func main() {
	s := make([]int, 0, 16)
	for i := 0; i < 16; i++ {
		s = append(s, rand.Intn(100))
	}
	fmt.Println(s)
	heapSort(s)
	fmt.Println(s)
}

优秀排序算法之三：快速排序

原理：本质上来看，快速排序是对冒泡排序的一种改进，属于交换类的排序算法。

快速排序通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

步骤如下：

  1. 先从数列中取出一个数作为基准数。一般取第一个数。
  2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
  3. 再对左右区间重复第二步，直到各区间只有一个数。

举一个例子：5 9 1 6 8 14 6 49 25 4 6 3。

一般取第一个数 5 作为基准，从它左边和最后一个数使用[]进行标志，

如果左边的数比基准数大，那么该数要往右边扔，也就是两个[]数交换，这样大于它的数就在右边了，然后右边[]数左移，否则左边[]数右移。

5 [9] 1 6 8 14 6 49 25 4 6 [3]  因为 9 > 5，两个[]交换位置后，右边[]左移
5 [3] 1 6 8 14 6 49 25 4 [6] 9  因为 3 !> 5，两个[]不需要交换，左边[]右移
5 3 [1] 6 8 14 6 49 25 4 [6] 9  因为 1 !> 5，两个[]不需要交换，左边[]右移
5 3 1 [6] 8 14 6 49 25 4 [6] 9  因为 6 > 5，两个[]交换位置后，右边[]左移
5 3 1 [6] 8 14 6 49 25 [4] 6 9  因为 6 > 5，两个[]交换位置后，右边[]左移
5 3 1 [4] 8 14 6 49 [25] 6 6 9  因为 4 !> 5，两个[]不需要交换，左边[]右移
5 3 1 4 [8] 14 6 49 [25] 6 6 9  因为 8 > 5，两个[]交换位置后，右边[]左移
5 3 1 4 [25] 14 6 [49] 8 6 6 9  因为 25 > 5，两个[]交换位置后，右边[]左移
5 3 1 4 [49] 14 [6] 25 8 6 6 9  因为 49 > 5，两个[]交换位置后，右边[]左移
5 3 1 4 [6] [14] 49 25 8 6 6 9  因为 6 > 5，两个[]交换位置后，右边[]左移
5 3 1 4 [14] 6 49 25 8 6 6 9  两个[]已经汇总，因为 14 > 5，所以 5 和[]之前的数 4 交换位置
第一轮切分结果：4 3 1 5 14 6 49 25 8 6 6 9  

现在第一轮快速排序已经将数列分成两个部分：

4 3 1 和 14 6 49 25 8 6 6 9

左边的数列都小于 5，右边的数列都大于 5。

使用递归分别对两个数列进行快速排序。

代码实现：

package main

import (
	"fmt"
	"math/rand"
)

//快速排序
func quickSort(data []int) {
	if len(data) <= 1 {
		return
	}
	//第一轮排序，先选出基准数
	base := data[0]
	l, r := 0, len(data)-1
	//i是要交换位置的下标
	for i := 1; i <= r; {
		//如果左边的数比基准数大，那么该数要往右边扔
		if data[i] > base {
			//将大于基准数的数字移至最右边
			data[i], data[r] = data[r], data[i]
			//右边进行比较的数下标减一位
			r--
			//如果左边的数比基准数小，那么该数要往左边扔
		} else {
			//将小于基准数的数字移至最左边
			data[i], data[l] = data[l], data[i]
			//左边进行比较的下标加一位
			l++
			//交换位置的下标加一位
			i++
		}
	}
	//一次循环结束后，以基准数位置分成左右两个部分分别在进行递归
	quickSort(data[:l])
	quickSort(data[l+1:])
}

func main() {
	s := make([]int, 0, 16)
	for i := 0; i < 16; i++ {
		s = append(s, rand.Intn(100))
	}
	fmt.Println(s)
	quickSort(s)
	fmt.Println(s)
}

时间复杂度为：O(nlogn)

参考文章：
数据结构与算法
菜鸟教程：排序算法

文章作者: hypo
文章链接: https://github.com/hypo-Z/hypo-Z.github.io/2022/06/28/chang-yong-pai-xu-suan-fa-de-golang-shi-xian/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 hypo !
Golang 算法
评论
 上一篇
使用Pandoc把Markdown转为PDF文件 使用Pandoc把Markdown转为PDF文件
Pandoc可以很方便地对不同 Markup 语言的文件进行格式转换，因此被誉为格式转换的「瑞士军刀」。使用 Pandoc 把 Markdown 文件转为 PDF 文件，实际上包含两个步骤：
2022-07-06 笔记
笔记 pandoc markdown pdf
下一篇 
Go语言进阶——数据结构之栈和队列 Go语言进阶——数据结构之栈和队列
由之前的文章可知，存储数据元素将数据放入或删除存储空间内，最基本的结构是数组和链表，而获取数据元素的方式有多种形式，但最简单的是取最前或最后。
2022-03-02 Golang
Golang 进阶
  目录