八大基础排序算法总结（golang实现）-阿南达文事网

八大基础排序算法总结（golang实现）

自己写的代码tm都不知道啥意思了，还是要定时复习啊

一、冒泡排序n^2

基本思想：对于升序来说，两层for循环，第一层表示需要冒多少次，第二层用于比较，两两比较，如果前数大于后数，交换，否则不交换

package main
import "fmt"
func Swap(arr []int, i, j int){arr[i],arr[j]=arr[j],arr[i]
}
func MaoPaoSort(arr []int){for i:=0;i<len(arr);i++{for j:=1;j<len(arr)-i;j++ {if arr[j]<arr[j-1] {Swap(arr, j,j-1)}}}
}
func main(){arr := []int{9,5,7,4,1,3,6,0,6,8}MaoPaoSort(arr)fmt.Println(arr)
}

二、快速排序nlogn

基本思想：选择一个基准，两个游标low，high，0-low全比基准小，high-len(arr)全比基准大，对0-low和high-len(arr)递归

package mainimport ("fmt""time""math/rand"
)//交换的函数
func Swap(arr []int, i, j int){arr[i],arr[j]=arr[j],arr[i]
}
func QuickSort2(arr []int, left,right int){if (right-left)<1{//递归结束标志，当数组只有一个时认为时有序的return}//以第一个作为基准(升序)posnum := arr[left]//定义区域low := left  //low需要++，最终使arr[left, low]都是小于基准high := right+1  //high-- 使arr[high, right]都是大于基准的//可以将high := right，后面的代码相继就要改i := left+1   //i++使[low+1, i]都是等于基准的//开始移动,大的一后面，小的移前面，等的一中间for i<(high){//当i与 high+1重回结束循环if arr[i]>posnum{Swap(arr, i, high-1)high--}else if arr[i]<posnum{Swap(arr, i, low+1)i++low++//为什么>的时候不用i++呢：在小于的时候，交换过来的数已经做过了判断，// 已经是比基准小的数，而大于的时候， 交换的是后面的数，后面的数没有遍历到，//所以需要i不变，以便继续判断交换过来的数	}else{i++//等于则跳到下一个继续判断}}//不要忘了这一步，基准与low区间最后那个交换，要知道(left,low]都是比基准小的Swap(arr,left,low)//大小区域分别递归QuickSort2(arr, left, low-1)QuickSort2(arr, high, right)}func main(){//创建数组arr := make([]int, 20,20)r := rand.New(rand.NewSource(time.Now().UnixNano()))for i:=0;i<20;i++{arr[i]=r.Intn(100)}fmt.Println("before sort",arr)QuickSort2(arr, 0, len(arr)-1)fmt.Println("after  sort",arr)}

三、二分插入排序nlogn

基本思路：i从1开始到n结束，以0到i-1是有序序列，对arr[i]，用二分查找，在0到i-1范围内查找对应位置，以升序为例，找到第一个比arr[i]稍大的。

 package mainimport ("fmt""time""math/rand"
)func MakeArr()[]int{var list []intre := rand.New(rand.NewSource(time.Now().UnixNano()))for i := 0;i<10;i++{list = append(list, re.Intn(1000))}return list
}func BinaryFindPos(area []int, start, end, cur int)int{//结束标志,返回start与cur值较大的数if start == end{if area[start]>area[cur]{return start}else{return cur}}med := (start+end)/2//递归逼近该位置//找到比area[cur]稍稍大的数if area[med]<area[cur]{return BinaryFindPos(area, med+1, end, cur)}else {return BinaryFindPos(area, start, med, cur)}
}
func BinaryInsertSort(area []int)[]int{for  i:=1;i<len(area);i++{pos := BinaryFindPos(area, 0, i-1, i)fmt.Println("pos :",pos)if pos != i{//123 0for j:=i;j>pos;j--{area[j], area[j-1]=area[j-1],area[j]}}}return area
}
func main(){area := MakeArr()fmt.Println(area)area = BinaryInsertSort(area)fmt.Println(area)
}

四、希尔排序n^1.3

基本思路：以数组长度一半为步长，每次步长减半，循环步长次。其中每次循环都要分成步长组数据，每组数据是arr[i+步长]，对每组数据进行冒泡排序，插入排序也可以

package mainimport ("time""fmt"
)func ShellSort(arr []int)[]int{length := len(arr)if length<=1{return arr}stap := length/2for stap>0{for i:=0;i<stap;i++{ShellSortInsert(arr, i, stap)}stap/=2}time.Sleep(1*time.Second)return arr
}func ShellSortInsert(arr []int ,start, stap int)[]int{length := len(arr)if length<=1{return arr}for i:=start+stap;i<length;i+=stap{tmp := arr[i]for j:=i-stap;j>=0;j-=stap{if arr[j]>tmp{arr[j+stap],arr[j]=arr[j],arr[j+stap]}}}return arr
}func main(){arr:=[]int{1,9,2,8,3,7,6,4,5,112,102,1,9,2,8,3,7,6,4,5,112,102,1,9,2,8,3,7,6,4,5,112,102,1,9,2,8,3,7,6,4,5,112,102,1,9,2,8,3,7,6,4,5,112,102,1,9,2,8,3,7,6,4,5,112,102}start:=time.Now()ShellSort(arr)fmt.Println(time.Since(start))fmt.Println(arr)
}

5、选择排序n^2

基本思路：每次选择最小的（最大的）放到i的位置

package mainimport ("fmt"
)func SelectSort(arr []int)[]int{if len(arr)<=1{return arr}for i:=0;i<len(arr)-1;i++{min := ifor j:=i+1;j<len(arr);j++{if arr[j]<arr[min]{min=j}}arr[min], arr[i]=arr[i],arr[min]fmt.Println(arr)}return arr
}func main(){arr := []int{9,8,6,5,7,1,2,3,5}arr = SelectSort(arr)fmt.Println(arr)
}

6、堆排序nlogn

就是二叉树，保证每个子节点都小于父节点（对于升序来说），一共需要循环n次，每次维护一个最大堆，将arr[0]与二叉树最后一个节点交换，二叉树长度减一，循环进行。也就是利用最大堆循环的找出0到len-i最大值，与len-i交换

package mainimport ("fmt"
)func HeapSort(arr []int)[]int{if len(arr)<=1{return arr}length := len(arr)for i:=0;i<length-1;i++{lastlen := length-iBinaryTreeFindMax(arr, lastlen)arr[lastlen-1], arr[0]=arr[0],arr[lastlen-1]fmt.Println(arr)}return arr
}
func BinaryTreeFindMax(arr []int, length int){if length<=1{return}depth := length/2-1for i:=depth;i>=0;i--{max:=ileftchild := 2*i+1rightchild := 2*i+2if leftchild<=length-1&&arr[leftchild]>arr[max]{max=leftchild}if rightchild<=length-1&&arr[rightchild]>arr[max]{max=rightchild}if max != i{arr[max], arr[i]=arr[i],arr[max]}}
}
func main(){arr := []int{5,7,4,1,9,6,3,8,2}arr = HeapSort(arr)fmt.Println(arr)
}

7.基数排序d(r+n)

先以个位排序，再十位，再百位，以此类推。
也就是说个位是0的放一个桶里，1放一个桶里。。。。。。再把这是个桶连起来。
再十位的。。。。。。
这个算法很幼稚

package main
import "fmt"
func jishuSort(arr []int, base int)[]int{//base 是 得到对应位的帮助比如 123 得到个位123%10/1，得到十位123%100/10，得到百位数字123%1000/100if len(arr)<=1 {return arr}tong0:=make([]int,0)tong1:=make([]int,0)tong2:=make([]int,0)tong3:=make([]int,0)tong4:=make([]int,0)tong5:=make([]int,0)tong6:=make([]int,0)tong7:=make([]int,0)tong8:=make([]int,0)tong9:=make([]int,0)//首先需要知道有多少位，这里直接假设有最多三位for i :=0;i<len(arr);i++ {if arr[i]%base/(base/10)==0 {tong0 = append(tong0, arr[i])}if arr[i]%base/(base/10)==1 {tong1 = append(tong1, arr[i])}if arr[i]%base/(base/10)==2 {tong2 = append(tong2, arr[i])}if arr[i]%base/(base/10)==3 {tong3 = append(tong3, arr[i])}if arr[i]%base/(base/10)==4 {tong4 = append(tong4, arr[i])}if arr[i]%base/(base/10)==5 {tong5 = append(tong5, arr[i])}if arr[i]%base/(base/10)==6 {tong6 = append(tong6, arr[i])}if arr[i]%base/(base/10)==7 {tong7 = append(tong7, arr[i])}if arr[i]%base/(base/10)==8 {tong8 = append(tong8, arr[i])}if arr[i]%base/(base/10)==9 {tong9 = append(tong9, arr[i])}}arr = append(tong0,tong1...)arr = append(arr,tong2...)arr = append(arr,tong3...)arr = append(arr,tong4...)arr = append(arr,tong5...)arr = append(arr,tong6...)arr = append(arr,tong7...)arr = append(arr,tong8...)arr = append(arr,tong9...)if base*10>1000 {return arr}return jishuSort(arr,base*10)
}func main() {arr := []int{1,17,87,12,2,3,175,958,14,6,8,8,7,1,10,21}arr = jishuSort(arr,10)fmt.Println(arr)
}

8.归并排序nlogn

package mainimport ("fmt""time""math/rand")func IncorporateArr(left, right []int)[]int{i,j :=0,0res := []int{}ilen,jlen := len(left), len(right)for i<ilen&&j<jlen{if left[i]<right[j]{res = append(res, left[i])i++}else if left[i]>right[j]{res = append(res, right[j])j++}else{res = append(res, left[i])res = append(res, right[j])i++j++}}for i<ilen{res = append(res, left[i])i++}for j<jlen{res = append(res, right[j])j++}return res
}func IncorporateSort(arr []int)[]int{if len(arr)<=1{return arr}med := len(arr)/2left := IncorporateSort(arr[0:med])right := IncorporateSort(arr[med:])return IncorporateArr(left, right)
}
func MakeArr()[]int{var list []intre := rand.New(rand.NewSource(time.Now().UnixNano()))for i := 0;i<10;i++{list = append(list, re.Intn(100))}return list
}
func main(){arr := MakeArr()fmt.Println(arr)arr = IncorporateSort(arr)fmt.Println(arr)
}