冒泡排序——Bubble Sort
算法原理
它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
算法描述
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
package main
import "fmt"
func main() {
arr := []int{1, 3, 45, 32, 74, 33, 22, 8, 23, 75, 44, 26, 9}
result := bubbleSort(arr)
fmt.Println(result)
}
func bubbleSort(arr []int) []int {
for i := 0; i < len(arr)-1; i++ {
for j := 0; j < len(arr)-1-i; j++ {
//相邻元素两两对比
if arr[j] > arr[j+1] {
// 元素交换
temp := arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
}
}
}
return arr
}
选择排序——Selection Sort
算法原理
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法描述
- 初始状态：无序区为R[1..n]，有序区为空；
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- n-1趟结束，数组有序化了
package main
import "fmt"
func main() {
arr := []int{1, 3, 45, 32, 74, 33, 22, 8, 23, 75, 44, 26, 9}
result := selectionSort(arr)
fmt.Println(result)
}
func selectionSort(arr []int) []int {
var minIndex, temp int
for i := 0; i < len(arr)-1; i++ {
minIndex = i
for j := i + 1; j < len(arr); j++ {
// 寻找最小的数,将最小数的索引保存
if arr[j] < arr[minIndex] {
minIndex = j
}
}
//将最小数放到当前的遍历位置
temp = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
}
return arr
}
插入排序——Insertion Sort
算法原理
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法描述
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
- 将新元素插入到该位置后；
- 重复步骤2~5。
package main
import "fmt"
func main() {
arr := []int{3, 1, 45, 32, 74, 33, 22, 8, 23, 75, 44, 26, 9}
result := insertionSort(arr)
fmt.Println(result)
}
func insertionSort(arr []int) []int {
for i := 1; i < len(arr); i++ {
current := arr[i]
index := i
//从前一位开始遍历
for j := i - 1; j >= 0; j-- {
//如果前一位的数值比当前的小，则将前一位的数赋值到当前位
if arr[j] > current {
//将前一位的数赋值到当前位
arr[j+1] = arr[j]
//将前一位的索引设置为当前数值应该存在的位置
index = j
} else {
break
}
}
arr[index] = current
}
return arr
}
快速排序——quick Sort
算法原理
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述
- 从数列中挑出第一个元素，称为中位数；
- 重新排序数列，所有元素比基准值小的摆放在基准前面,称为左区间。所有元素比基准值大的摆在基准的后面,称为右区间（相同的数可以到任一边）；
- 对左区间进行快速排序
- 对右区间进行快速排序
- 重新合并左区间、中位数、右区间
package main
import "fmt"
func main() {
arr := []int{3, 1, 45, 32, 74, 33, 22, 8, 23, 75, 44, 26, 9}
result := quickSort(arr)
fmt.Println(result)
}
func quickSort(arr []int) []int {
length := len(arr)
if length <= 1 {
return arr
}
//设定基数
middle := arr[0]
left := []int{}
right := []int{}
//划分区间，左边都比中位数小，右边都比中位数大
for i := 1; i < length; i++ {
if middle < arr[i] {
right = append(right, arr[i])
} else {
left = append(left, arr[i])
}
}
//左边区间递归进行快速排序
left = quickSort(left)
//右边区间递归进行快速排序
right = quickSort(right)
result := append(append(left, middle), right...)
return result
}
归并排序——Merge Sort
算法原理
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法描述
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
package main
import "fmt"
func main() {
arr := []int{3, 1, 45, 32, 74, 33, 22, 8, 23, 75, 44, 26, 9}
result := mergeSort(arr)
fmt.Println(result)
}
func mergeSort(arr []int) []int {
if len(arr) < 2 {
return arr
}
i := len(arr) / 2
left := mergeSort(arr[0:i])
right := mergeSort(arr[i:])
result := merge(left, right)
return result
}
func merge(left, right []int) []int {
result := make([]int, 0)
m, n := 0, 0 // left和right的index位置
l, r := len(left), len(right)
for m < l && n < r {
if left[m] > right[n] {
result = append(result, right[n])
n++
continue
}
result = append(result, left[m])
m++
}
result = append(result, right[n:]...)
result = append(result, left[m:]...)
return result
}
计数排序——Counting Sort
算法原理
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
算法描述
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
package main
import "fmt"
func main() {
arr := []int{3, 1, 45, 32, 74, 33, 22, 8, 23, 75, 44, 26, 9}
result := countingSort(arr)
fmt.Println(result)
}
func countingSort(arr []int) []int {
maxValue := arr[0]
//找到最大值
for _, val := range arr {
if val > maxValue {
maxValue = val
}
}
//初始化计数桶
bucketLen := maxValue + 1
bucket := make([]int, bucketLen)
//入桶
for _, val := range arr {
bucket[val] += 1
}
//获取排序结果
sortedIndex := 0
for j := 0; j < bucketLen; j++ {
for bucket[j] > 0 {
arr[sortedIndex] = j
sortedIndex += 1
bucket[j] -= 1
}
}
return arr
}
算法复杂度
| 排序算法 | 时间复杂度（平均） | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(n) | O(1) | 不稳定 |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 插入排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
| 快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(nlog2n) | 不稳定 |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |