1. 快速排序算法
算法描述：是对插入算法的一种优化，利用对问题的二分化，实现递归完成快速排序 ，在所有算法中二分化是最常用的方式，将问题尽量的分成两种情况加以分析， 最终以形成类似树的方式加以利用，因为在比较模型中的算法中，最快的排序时间 负载度为 O(nlgn).
算法步骤
- 将数据根据一个值按照大小分成左右两边，左边小于此值，右边大于
- 将两边数据进行递归调用步骤1
- 将所有数据合并
package sort
import "fmt"
func QuickSort(arr []int) []int {
if len(arr) <= 1 {
return arr
}
splitdata := arr[0] //第一个数据
low := make([]int, 0, 0) //比我小的数据
hight := make([]int, 0, 0) //比我大的数据
mid := make([]int, 0, 0) //与我一样大的数据
mid = append(mid, splitdata) //加入一个
for i := 1; i < len(arr); i++ {
if arr[i] < splitdata {
low = append(low, arr[i])
} else if arr[i] > splitdata {
hight = append(hight, arr[i])
} else {
mid = append(mid, arr[i])
}
}
low, hight = QuickSort(low), QuickSort(hight)
myarr := append(append(low, mid...), hight...)
return myarr
}
//快读排序算法
func main() {
arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
fmt.Println(QuickSort(arr))
}
2. 堆排序算法
算法描述：首先建一个堆，然后调整堆，调整过程是将节点和子节点进行比较，将 其中最大的值变为父节点，递归调整调整次数lgn,最后将根节点和尾节点交换再n次 调整O(nlgn).
算法步骤
- 创建最大堆或者最小堆（我是最小堆）
- 调整堆
- 交换首尾节点(为了维持一个完全二叉树才要进行收尾交换)
package sort
import "fmt"
//堆排序
func main() {
arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
fmt.Println(HeapSort(arr))
}
func HeapSortMax(arr []int, length int) []int {
// length := len(arr)
if length <= 1 {
return arr
}
depth := length/2 - 1 //二叉树深度
for i := depth; i >= 0; i-- {
topmax := i //假定最大的位置就在i的位置
leftchild := 2*i + 1
rightchild := 2*i + 2
if leftchild <= length-1 && arr[leftchild] > arr[topmax] { //防止越过界限
topmax = leftchild
}
if rightchild <= length-1 && arr[rightchild] > arr[topmax] { //防止越过界限
topmax = rightchild
}
if topmax != i {
arr[i], arr[topmax] = arr[topmax], arr[i]
}
}
return arr
}
func HeapSort(arr []int) []int {
length := len(arr)
for i := 0; i < length; i++ {
lastlen := length - i
HeapSortMax(arr, lastlen)
if i < length {
arr[0], arr[lastlen-1] = arr[lastlen-1], arr[0]
}
}
return arr
}3. 冒泡排序算法
算法描述：冒泡算法，数组中前一个元素和后一个元素进行比较如果大于或者小于 前者就进行交换，最终返回最大或者最小都冒到数组的最后序列时间复杂度为 O(n^2).
算法步骤
- 从数组开头选择相邻两个元素进行比较，并进行交换
- 不停向后移动
package sort
import "fmt"
//冒泡排序
func main() {
arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
fmt.Println(GetMax(arr))
fmt.Println(BubbleSort(arr))
}
//冒泡排序获取最大值
func GetMax(arr []int) int {
for j := 1; j < len(arr); j++ {
if arr[j-1] > arr[j] {
arr[j-1], arr[j] = arr[j], arr[j-1]
}
}
return arr[len(arr)-1]
}
//冒泡排序
func BubbleSort(arr []int) []int {
for i := 0; i < len(arr); i++ {
for j := i + 1; j < len(arr); j++ {
if arr[i] > arr[j] {
arr[i], arr[j] = arr[j], arr[i]
}
}
}
return arr
}4. 选择排序算法
算法描述：从未排序数据中选择最大或者最小的值和当前值交换 O(n^2).
算法步骤
- 选择一个数当最小值或者最大值，进行比较然后交换
- 循环向后查进行
package sort
import "fmt"
//获取切片里面的最大值
func SelectMax(arr []int) int {
length := len(arr)
if length <= 1 {
return arr[0]
}
max := arr[0]
for i := 1; i < length; i++ {
if arr[i] > max {
max = arr[i]
}
}
return max
}
//切片排序
func SelectSort(arr []int) []int {
length := len(arr)
if length <= 1 {
return arr
}
for i := 1; i < length; i++ {
min := i
for j := i + 1; j < length; j++ {
if arr[min] > arr[j] {
min = j
}
}
if i != min {
arr[i], arr[min] = arr[min], arr[i]
}
}
return arr
}
//选择排序
func main() {
arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
max := SelectMax(arr)
selectsort := SelectSort(arr)
fmt.Println(max)
fmt.Println(selectsort)
}5. 基数排序算法
算法描述：基数排序类似计数排序，需要额外的空间来记录对应的基数内的数据 额外的空间是有序的，最终时间复杂度O(nlogrm),r是基数，r^m=n.当给定 特定的范围，计数排序又可以叫桶排序，当以10进制为基数时就是简单的桶排序
算法步骤
- 从个位开始排序，从低到高进行递推
- 比较过程中如果遇到高位相同时，顺序不变
算法分两类
- 低位排序LSD
- 高位排序MSD
package sort
import "fmt"
func main() {
var arr [3][]int
myarr := []int{1, 2, 3, 1, 1, 2, 2, 2, 2, 2, 3}
for i := 0; i < len(myarr); i++ {
arr[myarr[i]-1] = append(arr[myarr[i]-1], myarr[i])
}
fmt.Println(arr)
}