冒泡排序法： 每次都遍历数组里的最小或最大，两两之间比较 eg: func sort(arr *[5]int){ fmt.Println(“排序前”) fmt.Println(*arr) temp :=0 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 } } } fmt.Println(“排序后”) fmt.Println(*arr) } 选择排序法： 每次选择出排序后该位置相应的值，只是与改换位置的值互换位置 eg： func Selectsort(arr *[6]int){ for j:=0;j<len(arr)-1;j++{ max:=arr[j] maxIndex:=j for i:=j+1;i<len(arr);i++{ if arr[i]>max{ max=arr[i] maxIndex=i } } //实现交换 if maxIndex!=j{ arr[maxIndex],arr[j]=arr[j],arr[maxIndex] } fmt.Printf(“第%d次 %v\n”,j+1,*arr) } }
插入排序: //比较插入元素跟前面已经排序好的数组 //选择位置插入
时间复杂度（平均） 时间复杂度（最坏) 时间复杂度（最好) 空间复杂度 稳定性 复杂性 直接插入排序 O(n2) O(n2) O(n2) O(n2) O(n)O(n) O(1)O(1) 稳定 简单 eg func insertsort(arr *[7]int){ //从第二个元素开始选择插入 for j:=1;j<len(arr);j++{ insertval:=arr[j] insertIndex:=j-1 //比较插入元素跟前面已经排序好的数组 //选择位置插入 //退出条件为Index>=0 && 插入的值>=Index元素 //循环条件，不断向前遍历，即index– //元素逐渐后移 for insertIndex>=0 && insertval>=arr[insertIndex]{ arr[insertIndex+1]=arr[insertIndex] insertIndex– }
if insertIndex!=j-1{ //赋值在该在的位置 arr[insertIndex+1]=insertval } fmt.Printf("第%d次插入%v\n",j,arr) }}
快速排序： 快速排序,说白了就是给基准数据找其正确索引位置的过程.
时间复杂度： 平均时间复杂度也是：O(nlogn) 最差的情况下时间复杂度为：O( n^2 ) 快速排序的平均时间复杂度也是：O(nlogn) 空间复杂度： 最优的情况下空间复杂度为：O(logn) 最差的情况下空间复杂度为：O( n )
eg package main import( “fmt” ) //说明： //1.left表示数组左边的下标 //2.right表示数组右边的下标 //3.array表示要排序的数组 func QuickSort(left int,right int,array *[9]int){ l:=left r:=right //pivot是中轴，支点 pivot:=array[(left+right)/2] temp:=0 //for循环的目标是将比pivot小的数放在左边 //比pivot大的放右边 for ;l<r;{ //从pivot的左边找到大于等于pivot的值 for ;array[l]<pivot;{ l++ } //从pivot的右边找到小于等于pivot的值 for ;array[r]>pivot;{ r– } //l>=r表明本次分解任务完成，break if l>=r{ break } //交换 temp=array[l] array[l]=array[r] array[r]=temp //优化 if array[l]==pivot{ r– } if array[r]==pivot{ l++ } }
//如果l==r,再移动下 if l==r{ l++ r-- } //向左递归 if left<r{ QuickSort(left,r,array) } //向右递归 if right>l{ QuickSort(l,right,array) }} func main(){ //arr:=[9]int{-9,75,86,96,35,55,78,21,945} arr:=[9]int{9,15,19,8,11,4,5,3,2} fmt.Println(arr) QuickSort(0,len(arr)-1,&arr) fmt.Println(arr) }
堆排序： 堆排序的基本思想是：将待排序序列构造成一个大顶堆（即二叉树），此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
