排序算法详解(Go语言实现):冒泡排序/选择排序/快速排序/插入排序

books1958 · · 1334 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

算法是程序的灵魂,而排序算法则是一种最基本的算法。排序算法有许多种,本文介绍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大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:812540095

1334 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传