首页 > 代码库 > 排序算法详解(Go语言实现):冒泡排序/选择排序/快速排序/插入排序
排序算法详解(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语言实现):冒泡排序/选择排序/快速排序/插入排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。