数据结构与算法 - 排序
代码实现基于golang version 1.18
1. 冒泡排序
冒泡排序是一种交换排序，核心是冒泡，把数组中最大的那个往上冒，冒的过程就是和他相邻的元素交换。
重复走访要排序的数列，通过两两比较相邻记录的排序码。排序过程中每次从后往前冒一个最小值，且每次能确定一个数在序列中的最终位置。若发生逆序
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
冒泡排序
代码实现
type Num interface {
~int | ~int8 | ~int16 | ~int32 | ~int64 | ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr | ~float32 | ~float64
}
func BubbleSort[T Num](s []T) {
var isSort = true
for i := 0; i < len(s); i++ {
isSort = true
for j := 0; j < len(s)-i-1; j++ {
if s[j] > s[j+1] {
isSort = false
s[j], s[j+1] = s[j+1], s[j]
continue
}
}
if isSort {
return
}
}
return
}
2. 选择排序
选择排序是一种简单直观的排序算法， 时间复杂度是O(n^2)。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了
算法思想：第一趟从n个元素的数据序列中选出关键字最小/大的元素并放在最前/后位置，下一趟从n-1个元素中选出最小/大的元素并放在最前/后位置。以此类推，经过n-1趟完成排序
选择排序是不稳定的算法，例如 [4,2,4,1] , 在第一次选择最小值 1时，此时4， 1交换位置[1,2,4,4],导致第一个4 进入了最后的位置， 4的相对顺序已经改变，稳定的算法应该是第一个4 的相对顺序在第二个4之前
选择排序
代码实现
func SelectionSort[T Num](s []T) {
var minId int
for i := 0; i < len(s); i++ {
minId = i
for j := i + 1; j < len(s); j++ {
if s[minId] > s[j] {
minId = j
}
}
s[i], s[minId] = s[minId], s[i]
}
}
3. 堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
以大顶堆为例， 此时按照图中的序号编号，可以映射为一个数组：
对于任意索引的节点i，有如下的性质
- 左孩子节点为索引为 2 * i + 1
- 右孩子节点为索引为 2 * i + 2
- 父节点索引为 （ i - 1 ）/ 2
所以大顶堆的任一节点有如下属性：
arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆的任一节点有如下属性：
arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了,步骤如下
-
将无序的序列构造成大顶堆（升序大顶堆，降序小顶堆）
对于给定的如下的无序数组
image.png
此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整
找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换如图a，这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6，如图b， 这就是heapify 的过程
图a
图b
- 根据大顶堆的属性，根节点的值是最大的，所以只要每次讲首末尾元素交换， 此时末尾元素就是最大的，然后继续调整除了末尾元素的堆，如此循环，直至最后一个元素
将堆顶元素9和末尾元素4进行交换，如图c
图c
重新调整结构(heapify)，使剩下[0-3]的元素继续满足堆定义
图d
再将堆顶元素8与末尾元素5进行交换，得到第二大元素8
图e
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
图f
堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级
代码实现
// 堆化
func HeapifyMax[T Num](s []T, n int, i int) {
if i >= n {
return
}
max := i
// 左右孩子节点
lc := i*2 + 1
rc := i*2 + 2
if lc < n && s[lc] > s[max] {
max = lc
}
if rc < n && s[rc] > s[max] {
max = rc
}
if max != i {
s[max], s[i] = s[i], s[max]
HeapifyMax(s, n, max)
}
}
// 堆化
func HeapifyMin[T Num](s []T, n int, i int) {
if i >= n {
return
}
min := i
// 左右孩子节点
lc := i*2 + 1
rc := i*2 + 2
if lc < n && s[lc] < s[min] {
min = lc
}
if rc < n && s[rc] < s[min] {
min = rc
}
if min != i {
s[min], s[i] = s[i], s[min]
HeapifyMin(s, n, min)
}
}
// 构建大顶堆
func BuildMaxHeap[T Num](s []T) {
lastNode := len(s) - 1
parent := (lastNode - 1) / 2
for i := parent; i >= 0; i-- {
HeapifyMax(s, len(s), i)
}
}
// 构建小顶堆
func BuildMinHeap[T Num](s []T) {
lastNode := len(s) - 1
parent := (lastNode - 1) / 2
for i := parent; i >= 0; i-- {
HeapifyMin(s, len(s), i)
}
}
// 降序排序
func HeapSortMin[T Num](s []T) {
BuildMinHeap(s)
fmt.Println(s)
for i := len(s) - 1; i > 0; i-- {
s[0], s[i] = s[i], s[0]
HeapifyMin(s, i, 0)
}
}
// 升序排序
func HeapSortMax[T Num](s []T) {
BuildMaxHeap(s)
fmt.Println(s)
for i := len(s) - 1; i > 0; i-- {
s[0], s[i] = s[i], s[0]
HeapifyMax(s, i, 0)
}
}
4. 插入排序
插入排序(InsertionSort)，一般也被称为直接插入排序。
对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表
在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动
插入排序
代码实现
func InsertSort[T Num](s []T) {
for i := 0; i < len(s); i++ {
current := s[i]
preIndex := i - 1
for preIndex = i - 1; preIndex >= 0 && current < s[preIndex]; preIndex-- {
s[preIndex+1] = s[preIndex]
}
s[preIndex+1] = current
}
}
5. 快速排序
快速排序的基本思想是任取待排序序列的一个元素作为中心元素(可以用第一个，最后一个，也可以是中间任何一个)，习惯将其称为pivot，枢轴元素；
将所有比枢轴元素小的放在其左边；
将所有比它大的放在其右边；
形成左右两个子表；
然后对左右两个子表再按照前面的算法进行排序，直到每个子表的元素只剩下一个。
可见快速排序用到了分而治之的思想。
将一个数组分成两个数组的方法为：
先从数组右边找到一个比枢轴元素小的元素，将数组的第一个位置赋值为该元素；
再从数组的左边找到一个比枢轴元素大的元素，将从上面取元素的位置赋值为该值；
依次进行，直到左右相遇，把枢轴元素赋值到相遇位置。
快速排序
快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下空间复杂度为 O(logn)，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 O(n)。所以我们一般认为快速排序的空间复杂度为 O(logn)
代码实现
// 轴元素左右划分
func partition[T Num](s []T, left, right int) int {
pivot := left
index := pivot + 1
for i := index; i <= right; i++ {
if s[i] < s[pivot] {
s[i], s[index] = s[index], s[i]
index++
}
}
s[pivot], s[index-1] = s[index-1], s[pivot]
return index - 1
}
// 通过枢轴元素，划分分区，递归调用
func quickSort[T Num](s []T, left, right int) {
if left < right {
index := partition(s, left, right)
quickSort(s, left, index-1)
quickSort(s, index+1, right)
}
}
// 快速排序对外函数入口
func QuickSort[T Num](s []T) {
quickSort(s, 0, len(s)-1)
}
6. 希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
func shellSort[T Num](s []T) []T {
length := len(s)
gap := 1
for gap < length/3 {
gap = gap*3 + 1
}
for gap > 0 {
for i := gap; i < length; i++ {
temp :=s[i]
j := i - gap
for j >= 0 &&s[j] > temp {
s[j+gap] =s[j]
j -= gap
}
s[j+gap] = temp
}
gap = gap / 3
}
return s
}
7. 归并排序
基本速思路：
归并排序用到了分治 和 递归的思想， 主要流程如下图所示，包括了拆分和合并两部分
image.png
- 将序列中带排序数字分为若干组，每个数字分为一组
- 将若干组两两合并， 保证合并后的组是有序的
- 重复第二部操作知道只剩下一组，排序完成
mergeSort.gif
代码实现
func MergeSort[T Num](s []T) []T {
if len(s) == 1 {
return s
}
mid := len(s) / 2
left := s[:mid]
right := s[mid:]
return merge(MergeSort(left), MergeSort(right))
}
func merge[T Num](left, right []T) []T {
result := make([]T, len(left)+len(right))
index := 0
for len(left) != 0 && len(right) != 0 {
if left[0] <= right[0] {
result[index] = left[0]
left = left[1:]
} else {
result[index] = right[0]
right = right[1:]
}
index++
}
for len(left) != 0 {
result[index] = left[0]
left = left[1:]
index++
}
for len(right) != 0 {
result[index] = right[0]
right = right[1:]
index++
}
return result
}
8. 比较
| 算法 | 时间复杂度 | 空间复杂度 | 是否稳定 |
|---|---|---|---|
| 冒泡排序 | O(n^2) | O(1) | 是 |
| 选择排序 | O(n^2) | O(1) | 否 |
| 插入排序 | O(n^2) | O(1) | 是 |
| 堆排序 | O(nlogn) | O(1) | 否 |
| 希尔排序 | O(nlogn) | O(1) | 否 |
| 归并排序 | O(nlogn) | O(n) | 是 |
| 快速排序 | O(nlogn) | O(logn) | 否 |
