Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法
本文实例讲述了Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法。分享给大家供大家参考。具体分析如下：
算法是程序的灵魂，而排序算法则是一种最基本的算法。排序算法有许多种，这里介绍4中排序算法：冒泡排序，选择排序，快速排序和插入排序，以从小到大为例。
一、冒泡排序
冒泡排序的原理是，对给定的数组进行多次遍历，每次均比较相邻的两个数，如果前一个比后一个大，则交换这两个数。经过第一次遍历之后，最大的数就在最右侧了；第二次遍历之后，第二大的数就在右数第二个位置了；以此类推。
//冒泡排序（排序10000个随机整数，用时约145ms）
funcbubbleSort(nums[]int){
fori:=0;i<len(nums);i++{
forj:=1;j<len(nums)-i;j++{
ifnums[j]<nums[j-1]{
//交换
nums[j],nums[j-1]=nums[j-1],nums[j]
}
}
}
}二、选择排序
选择排序的原理是，对给定的数组进行多次遍历，每次均找出最大的一个值的索引。
//选择排序（排序10000个随机整数，用时约45ms）
funcselectSort(nums[]int){
length:=len(nums)
fori:=0;i<length;i++{
maxIndex:=0
//寻找最大的一个数，保存索引值
forj:=1;j<length-i;j++{
ifnums[j]>nums[maxIndex]{
maxIndex=j
}
}
nums[length-i-1],nums[maxIndex]=nums[maxIndex],nums[length-i-1]
}
}三、快速排序
快速排序的原理是，首先找到一个数pivot把数组‘平均'分成两组，使其中一组的所有数字均大于另一组中的数字，此时pivot在数组中的位置就是它正确的位置。然后，对这两组数组再次进行这种操作。
//快速排序（排序10000个随机整数，用时约0.9ms）
funcquickSort(nums[]int){
recursionSort(nums,0,len(nums)-1)
}
funcrecursionSort(nums[]int,leftint,rightint){
ifleft<right{
pivot:=partition(nums,left,right)
recursionSort(nums,left,pivot-1)
recursionSort(nums,pivot+1,right)
}
}
funcpartition(nums[]int,leftint,rightint)int{
forleft<right{
forleft<right&&nums[left]<=nums[right]{
right--
}
ifleft<right{
nums[left],nums[right]=nums[right],nums[left]
left++
}
forleft<right&&nums[left]<=nums[right]{
left++
}
ifleft<right{
nums[left],nums[right]=nums[right],nums[left]
right--
}
}
returnleft
}四、插入排序
插入排序的原理是，从第二个数开始向右侧遍历，每次均把该位置的元素移动至左侧，放在放在一个正确的位置（比左侧大，比右侧小）。
//插入排序（排序10000个整数，用时约30ms）
funcinsertSort(nums[]int){
fori:=1;i<len(nums);i++{
ifnums[i]<nums[i-1]{
j:=i-1
temp:=nums[i]
forj>=0&&nums[j]>temp{
nums[j+1]=nums[j]
j--
}
nums[j+1]=temp
}
}
}
通过多次测试可以发现，快速排序是效率最高的。
希望本文所述对大家的Go语言程序设计有所帮助。