Go语言实现常用排序算法的示例代码

2024-04-02 19:04:59 898人浏览薄情痞子

摘要

目录冒泡排序快速排序选择排序插入排序排序算法是在生活中随处可见，也是算法基础，因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题，可以说是每个程序员都必须得

排序算法是在生活中随处可见，也是算法基础，因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题，可以说是每个程序员都必须得掌握的了。为了方便大家学习，花了一天的时间用Go语言实现一下常用的算法且整理了一下，如有需要可以参考。

冒泡排序

思路：从前往后对相邻的两个元素依次进行比较，让较大的数往下沉，较小的网上冒，即每当两个相邻的元素比较后发现他们的排序要求相反时，就将它们互换。

时间复杂度：O(N^2)

空间复杂度：O(1)

func main() {
	fmt.Println(bubbleSort([]int{2, 4, 1, 6, 3}))
}

func bubbleSort(list []int) []int {
	lenth := len(list)
	for i := 0; i <= lenth; i++ {//循环对比的轮数
		exchange := false
		for j := 1; j < lenth-i; j++ {//当前轮相邻元素循环对比
			if list[j-1] > list[j]{//如果前边的大于后边的
				list[j-1], list[j] = list[j], list[j-1]//交换数据
				exchange = true
			}
		}
		if !exchange {
			break
		}
	}
	return list
}

快速排序

思路：以一个基准数将数组拆分为两组，一边大于这个数，一边小于这个数，再最左右两个组重复这个过程，直到各个区域只有一个数。

时间复杂度：O(nlogn)

空间复杂度：O(1)

func quickSort(list []int) []int {
	length := len(list)
	if length <= 1 {
		return list
	}
	//基准值
	base := list[0]
    left := make([]int, 0)
	right := make([]int, 0)
	for i := 1; i < length; i++ {
		if list[i]  > base {
			right  = append(right, list[i])
		} else {
			left = append(left, list[i])
		}
	}
	left, right  = quickSort(left), quickSort(right)
	return append(append(left, base),right...)
}

选择排序

思路：首先找到数组中的最小元素，然后将这个最小元素和数组的第一个元素交换位置，如果第一个元素就是最小元素，就和自己交换位置；再次，在剩下的元素中找到最小元素和数组中的第二个元素交换位置，如此往复，直到将整个数组排序，一句话总结就是，不断在剩余元素中找最小元素。

时间复杂度：O(n^2)

空间复杂度：O(1)

func selectSort(list []int) []int {
	length := len(list)

	for i := 0; i < length; i++ {
		minIndex := i
		//每次循环找出i+1到最后一个元素区间的最小值，然后当前元素和当前最小值比较
		for j := i + 1; j < length; j++ {
			if list[j] < list[minIndex] {
				minIndex = j
			}
		}
		if i != minIndex {
			list[i], list[minIndex] = list[minIndex], list[i]
		}
	}
	return list
}

插入排序

思路：与选择排序一样，当前索引左边的所有元素都是有序的，但是他们的最终位置还不确定，为了给更小的元素腾出空间，他们可能会被移动，但是当索引到达数组的末端，数组排序就完成了。

时间复杂度：O(N^2)

空间复杂度：O(1)

func insertSort(list []int) []int {
	length := len(list)
	for i := 0; i < length; i++ {
		for j := i; j > 0; j-- {
			if list[j] > list[j-1] {
				break
			}
			list[j], list[j-1] = list[j-1], list[j]
		}
	}
	return list
}

排序思路算法几乎一样。暂时就介绍这几种常用的也是面试中经常问道的排序算法。

到此这篇关于Go语言实现常用排序算法的示例代码的文章就介绍到这了,更多相关Go语言排序算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

您可能感兴趣的文档: