简单排序：插入排序、选择排序、
冒泡排序 分治排序：快速排序、归并排序
分配排序：桶排序、基数排序
树状排序：堆排序
其他：计数排序、希尔排序
稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。
非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
非原地排序：需要利用额外的数组来辅助排序。
时间复杂度：一个算法执行所消耗的时间。
空间复杂度：运行完一个算法所需的内存大小。文章来源：https://www.toymoban.com/news/detail-815238.html
/** insertSort * 插入排序法 * @param arr * @return */
func insertSort(arr []int) {
// //判断数组是否为空或者长度是否大于2
if len(arr) < 2 {
return
}
//循环遍历数组
for i := 1; i < len(arr); i++ {
//定义变量保存要插入的值
tem := arr[i]
k := i - 1
for k >= 0 && arr[k] > tem {
arr[k+1] = arr[k]
k--
}
//元素插入
arr[k+1] = tem
}
return
}
// selectSort 选择排序 时间复杂度可能很高
func selectSort(arr []int) {
n := len(arr)
for i := 0; i < n-1; i++ {
m := i
for j := i + 1; j < n; j++ {
if arr[m] > arr[j] {
m = j
}
}
//交换
temp := arr[i]
arr[i] = arr[m]
arr[m] = temp
}
}
// bubbleSort 冒泡排序算法
func bubbleSort(arr []int) {
if len(arr) < 2 {
return
}
flag := true
//加一个标志位，记录上一次是否发生了交换，如果是，我们则进行下一轮，如果没有，说明已经冒泡好了
for i := 1; i < len(arr) && flag; i++ {
//控制次数，第几趟排序，只需要n-1趟，有交换时进行，只有flag=false就说明上一次一个元素都没有进行交换
flag = false
//假定未交换
for j := 0; j < len(arr)-i; j++ {
if arr[j] > arr[j+1] {
temp := arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
flag = true
}
}
}
}
// quickSort 快速排序算法
func quickSort(arr []int, left, right int) []int {
if left < right {
//获取基点元素所处的位置
mid := partition(arr, left, right)
//进行分割
arr = quickSort(arr, left, mid-1)
arr = quickSort(arr, mid+1, right)
}
return arr
}
func partition(arr []int, left, right int) int {
//选取基点元素
pivot := arr[left]
i := left + 1
j := right
for {
// 向右找到第一个小于等于 pivot 的元素位置
for i <= j && arr[i] <= pivot {
i++
}
// 向左找到第一个大于等于 pivot 的元素位置
for i <= j && arr[j] >= pivot {
j--
}
if i >= j {
break
}
//交换两个元素的位置，使得左边的元素不大于pivot,右边的不小于pivot
temp := arr[i]
arr[i] = arr[j]
arr[j] = temp
}
arr[left] = arr[j]
// 使中轴元素处于有序的位置
arr[j] = pivot
return j
}
// 堆排序
func heapSort(arr []int) {
//1.构建大顶堆
for i := len(arr)/2 - 1; i >= 0; i-- {
//从第一个非叶子结点从下至上，从右至左调整结构
sift(arr, i, len(arr))
}
//2.调整堆结构+交换堆顶元素与末尾元素
for i := len(arr) - 1; i > 0; i-- {
//现在的数组第一个就是根结点，最小值所在，进行交换，把它放到最右边
temp := arr[i]
arr[i] = arr[0]
arr[0] = temp
//重新建立堆
sift(arr, 0, i)
//重新对堆进行调整
}
}
/**
建立堆的方法
私有方法，只允许被堆排序调用
@param arr 要排序数组
@param parent 当前的双亲节点
@param len 数组长度
*/
func sift(arr []int, parent, len int) {
value := arr[parent]
//先取出当前元素i
for child := 2*parent + 1; child < len; child = child*2 + 1 {
//从parent结点的左子结点开始，也就是2*parent+1处开始
if child+1 < len && (arr[child] < arr[child+1]) {
//如果左子结点小于右子结点，child指向右子结点
child++
//右孩子如果比左孩子大，我们就将现在的孩子换到右孩子
}
//判断是否符合大顶堆的特性， 如果右孩子大于双亲，自然左孩子也大于双亲，符合
//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换)
if value < arr[child] {
arr[parent] = arr[child]
parent = child
} else {
//如果不是，说明已经符合我们的要求了。
break
}
}
arr[parent] = value
//将value值放到最终的位置
}
附个二分查找算法文章来源地址https://www.toymoban.com/news/detail-815238.html
func Search(n int, f func(int) bool) int {
// Define f(-1) == false and f(n) == true.
// Invariant: f(i-1) == false, f(j) == true.
i, j := 0, n
for i < j {
h := int(uint(i+j) >> 1) // avoid overflow when computing h
// i ≤ h < j
if !f(h) {
i = h + 1 // preserves f(i-1) == false
} else {
j = h // preserves f(j) == true
}
}
// i == j, f(i-1) == false, and f(j) (= f(i)) == true => answer is i.
return i
}
到了这里，关于集中常见的排序方法Go语言版本实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
