[数据结构与算法] LeetCode力扣Golang:十大排序算法

两层循环，第一层循环数组长度，第二层比较相邻进行交换（每一层循环总会有一个元素到达理想位置）

func BubbleSort(nums []int)[]int{
   for i:=0;i<len(nums)-1;i++{
       for j:=0;j<len(nums)-1-i;j++{
          if nums[j]>nums[j+1]{
               nums[j],nums[j+1]=nums[j+1],nums[j]
            }  
    }  
    return nums    
}

二、选择排序

冒泡的优化，在剩余的整体中交换，找到最大或最小的和自己交换可以减少减缓次数


func selectionSort(nums []int){
    
    for i := 0; i < len(nums) ; i++ {    
        minIndex := i
        for j := i + 1; j < len(nums); j++ {
            if nums[minIndex] > nums[j] {
                minIndex = j
            }
        }
    nums[i],nums[minIndex] = nums [minIndex],nums[i]

    }
}

三、插入排序

不是通过比较，而是扫描到合适的位置插入，所有插入位置后的元素向后移

自己写了下感觉没有这个哥的清晰,但是好像不导入地址导入数组数据也可以

func insertSort(a []int)[]int{
   for i:=1;i<len(a);i++{
      temp := a[i]
      j := i-1
      for j >= 0 && a[j] > temp {
         a[j+1] = a[j]
         j--
      }
      if j != i-1 {
         a[j+1] = temp
      }
   }
   return a
}

四、快速排序

对冒泡的改进，分治的应用，借用分区指示器，并不需要额外数组

准备：选择基准数，和尾元素进行位置交换，设置分区指示器（默认-1）和遍历指示器

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 若当前元素下标大于分区指示器，则和分区指示器所指元素交换? }

package main

import "fmt"

func QuickSort(nums []int){
	l:= len(nums)-1
	Index:= -1
	target := nums[0]
	nums[0] , nums[l] = nums[l],nums[0]

	for i := 0 ;i<len(nums);i++{
		if nums[i] < target{
			Index = Index+ 1
			if i >Index{
				nums[Index],nums[i] = nums[i],nums[Index]
            }
        }
    }
	//m,n := nums[:Index+1],nums[Index+1:l+1]
	var m =  make([]int,Index+1)
	var n = make([]int,l-Index+1)
	m,n = nums[:Index+1],nums[Index+1:l+1]
QuickSort(m)
QuickSort(n)
}

func main()  {
	nums := []int{88,44,66,75,95,13,4,6}
	QuickSort(nums)
	fmt.Println(nums)
}

出错了：panic: runtime error: index out of range [0] with length 0

?五、希尔排序/缩小增量排序

设置增量，每次依照增量进行分组，然后插入排序让组内有序，再不断缩小增量

增量序列递减最后为1即可，目前还没有最好序列，目前常用：

六、归并排序

递归和分治将序列划分为越来越小的半子表，对半子表排序后再用递归将排好的半子表合并为越来越大的有序序列

大哥写的挺清楚的，最后result那里竟然还有个解压切片，之前没见过


 
import "fmt"
 
// 自顶向下归并排序，排序范围在 [begin,end) 的数组
func MergeSort(array []int, begin int, end int) {
    // 元素数量大于1时才进入递归
    if end - begin > 1 {
 
        // 将数组一分为二，分为 array[begin,mid) 和 array[mid,high)
        mid := begin + (end-begin+1)/2
 
        // 先将左边排序好
        MergeSort(array, begin, mid)
 
        // 再将右边排序好
        MergeSort(array, mid, end)
 
        // 两个有序数组进行合并
        merge(array, begin, mid, end)
    }
}
 
// 归并操作
func merge(array []int, begin int, mid int, end int) {
    // 申请额外的空间来合并两个有序数组，这两个数组是 array[begin,mid),array[mid,end)
    newSize := end-begin+1 // 辅助数组的长度
    result := make([]int, 0, newSize)
 
    l, r := 0, 0
    for l < leftSize && r < rightSize {
        lValue := array[begin+l] // 左边数组的元素
        rValue := array[mid+r]   // 右边数组的元素
        // 小的元素先放进辅助数组里
        if lValue < rValue {
            result = append(result, lValue)
            l++
        } else {
            result = append(result, rValue)
            r++
        }
    }
 
    // 将剩下的元素追加到辅助数组后面
    result = append(result, array[begin+l:mid]...)
    result = append(result, array[mid+r:end]...)
 
    // 将辅助数组的元素复制回原数组，这样该辅助空间就可以被释放掉
    for i := 0; i < newSize; i++ {
        array[begin+i] = result[i]
    }
    return
}

?七、堆排序

先构成当前的最大堆，然后与最后一个结点比较并交换位置，循环往复

八、计数排序、基数排序、桶排序

计数排序：需要额外空间

新建一个计数数组，原数组的值出现几次，将计数数组的对应下标位置计几，然后把原数组按照对应下标的个数存入

基数排序：从右向左依次入桶，根据键值的每位数字来分配桶

依次实现个位、十位桶……最大位数，决定几轮排序，然后依次输入

?桶排序：每个桶存储一定范围内的值

总结：

快速排序与归并排序时间复杂度一样，但快速的常数因子小得多，空间复杂度低

有的时候会频繁出栈入栈，可能反而会增大时间复杂度，可以综合使用插入和快排