golang实现常用排序算法

1.冒泡排序，算法复杂度O(n^2)

packagemain

import(

"fmt"

)

funcmain(){

vararr=[]int{10,17,19,18,77,55}

fori:=0;i<len(arr)-1;i++{

forj:=i+1;j<len(arr);j++{

ifarr[i]>arr[j]{

arr[i],arr[j]=arr[j],arr[i]

}

}

}

fmt.Println(arr)

}

2.快速排序

它的基本思想是：通过一趟排序将数据一分为二，其中一部分的所有数据都比另外一部分的所有数据都要小，然后对两部分递归，直至完成。时间复杂度介于O(nlogn)和O(n^2)

一趟快速排序的算法是：

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]赋给A[i]；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]赋给A[j]；

5）重复第3、4步，直到i=j；

packagemain

import(

"fmt"

)

funcmain(){

quictSort()

}

funcquictSort(){

vararr=[]int{50,66,44,99,24}

recurtion(arr,len(arr)-1)

fmt.Println(arr)

}

funcrecurtion(arr[]int,leftint,rightint){

ifleft<right{

vari,j=left,right

varkey=arr[i]

fori<j{

fori<j&&arr[j]>=key{

j--

}

arr[i]=arr[j]

fori<j&&arr[i]<=key{

i++

}

arr[j]=arr[i]

}

arr[i]=key

recurtion(arr,left,i-1)

recurtion(arr,i+1,right)

}

}

3.插入排序

时间复杂度O(n^2)，不适合大量数据处理

从第二个值开始遍历，与前面的有序列比较，若比前面值小则交换

packagemain

import(

"fmt"

)

funcmain(){

insertSort()

}

funcinsertSort(){

vararr=[]int{50,24}

fori:=1;i<len(arr);i++{

forj:=0;j<i;j++{

ifarr[i]<arr[j]{

arr[i],arr[i]

}

}

}

fmt.Println(arr)

}

4.归并排序 算法复杂度O(nlogn)

是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。

packagemain

import"fmt"

funcmain(){
arr:=[]int{39,28,6,15}
mergeSort(arr,len(arr)-1)
fmt.Println(arr)
}
funcmerge(arr[]int,first,mid,lastint){
buf:=make([]int,last+1)
i:=first
j:=mid+1
varnumint=first
fori<=mid&&j<=last{
ifarr[i]<arr[j]{
buf[num]=arr[i]
i++
}else{
buf[num]=arr[j]
j++
}
num++
}
fori<=mid{
buf[num]=arr[i]
num++
i++
}
forj<=last{
buf[num]=arr[j]
num++
j++
}
copy(arr[first:],buf[first:])
}
funcmergeSort(arr[]int,lastint){
iffirst<last{
mid:=(first+last)/2
mergeSort(arr,mid)
mergeSort(arr,mid+1,last)
merge(arr,last)
}
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!