本文实例讲述了Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法。分享给大家供大家参考。具体分析如下:
算法是程序的灵魂,而排序算法则是一种最基本的算法。排序算法有许多种,这里介绍4中排序算法:冒泡排序,选择排序,快速排序和插入排序,以从小到大为例。
一、冒泡排序
冒泡排序的原理是,对给定的数组进行多次遍历,每次均比较相邻的两个数,如果前一个比后一个大,则交换这两个数。经过第一次遍历之后,最大的数就在最右侧了;第二次遍历之后,第二大的数就在右数第二个位置了;以此类推。
复制代码 代码如下://冒泡排序(排序10000个随机整数,用时约145ms)
func bubbleSort(nums []int) {
for i := 0; i < len(nums); i++ {
for j := 1; j < len(nums)-i; j++ {
if nums[j] < nums[j-1] {
//交换
nums[j], nums[j-1] = nums[j-1], nums[j]
}
}
}
}
二、选择排序
选择排序的原理是,对给定的数组进行多次遍历,每次均找出最大的一个值的索引。
复制代码 代码如下://选择排序(排序10000个随机整数,用时约45ms)
func selectSort(nums []int) {
length := len(nums)
for i := 0; i < length; i++ {
maxIndex := 0
//寻找最大的一个数,保存索引值
for j := 1; j < length-i; j++ {
if nums[j] > nums[maxIndex] {
maxIndex = j
}
}
nums[length-i-1], nums[maxIndex] = nums[maxIndex], nums[length-i-1]
}
}
三、快速排序
快速排序的原理是,首先找到一个数pivot把数组‘平均'分成两组,使其中一组的所有数字均大于另一组中的数字,此时pivot在数组中的位置就是它正确的位置。然后,对这两组数组再次进行这种操作。
复制代码 代码如下://快速排序(排序10000个随机整数,用时约0.9ms)
func quickSort(nums []int) {
recursionSort(nums, 0, len(nums)-1)
}
func recursionSort(nums []int, left int, right int) {
if left < right {
pivot := partition(nums, left, right)
recursionSort(nums, left, pivot-1)
recursionSort(nums, pivot+1, right)
}
}
func partition(nums []int, left int, right int) int {
for left < right {
for left < right && nums[left] <= nums[right] {
right--
}
if left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
}
for left < right && nums[left] <= nums[right] {
left++
}
if left < right {
nums[left], nums[right] = nums[right], nums[left]
right--
}
}
return left
}
四、插入排序
插入排序的原理是,从第二个数开始向右侧遍历,每次均把该位置的元素移动至左侧,放在放在一个正确的位置(比左侧大,比右侧小)。
复制代码 代码如下://插入排序(排序10000个整数,用时约30ms)
func insertSort(nums []int) {
for i := 1; i < len(nums); i++ {
if nums[i] < nums[i-1] {
j := i - 1
temp := nums[i]
for j >= 0 && nums[j] > temp {
nums[j+1] = nums[j]
j--
}
nums[j+1] = temp
}
}
}
通过多次测试可以发现,快速排序是效率最高的。
希望本文所述对大家的Go语言程序设计有所帮助。
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
更新日志
- Taylor Swift《THE TORTURED POETS DEPARTMENT- THE ANTHOLOGY》[320K/MP3][279.09MB]
- 崔健《85回顾+梦中的倾诉》2CD [WAV+CUE][771M]
- 群星《安桥试音碟》3CD[FLAC][1.1G]
- Taylor Swift《THE TORTURED POETS DEPARTMENT- THE ANTHOLOGY》][24bit 48kH][FLAC/分轨]
- 群星1995-阿诗玛·中国歌剧金曲[中唱][WAV+CUE]
- [JVC]吴文光-中国古琴:流水[FLAC分轨]
- 刘欢.2004-经典20年珍藏锦集【新索】【WAV+CUE】
- 中唱唱片群星《好歌珍藏-游子情深》2CDWAV
- CD圣经上榜天碟1995-乌仁娜-《蒙古草原之歌》[WAV+CUE].
- 【电影原声】武满彻《旭日东升》1993[WAV+CUE整轨]
- Taylor Swift《THE TORTURED POETS DEPARTMENT》[320K/MP3][148.54MB]
- Taylor Swift《THE TORTURED POETS DEPARTMENT》[FLAC/分轨][405.72MB]
- Joyce Jonathan《法式松弛感 漫步香榭丽舍》[320K/MP3][80.8MB]
- 女神异闻录5佐仓双叶coop攻略 p5r佐仓双叶对话选项攻略
- 【民谣】张智《尼勒克小镇》[FLAC]