当前位置：首页 > news >正文

I排序算法.go

news 2025/6/21 13:26:20

前言：在计算机科学中，排序算法是一个重要且基础的主题。

选择排序：挑挑拣拣选出最小的！

插入排序：像插队一样插入正确的位置！

快速排序：分治法的高手！

归并排序：合并的艺术！

总结

冒泡排序，一听这名字就很有画面感，就像小泡泡在水里往上冒一样。它的原理很简单，就是把数组里的元素两两比较，把大的那个往后冒，这样经过一轮比较，最大的元素就 “冒” 到最后面了。

算法原理 ：从第一个元素开始，比较相邻两个元素，如果前者大于后者（假设是升序），则交换它们的位置。遍历一遍后，最大的元素会沉到数组末尾。重复上述过程，未排序部分的长度每次减少 1，直到整个数组有序。

先看代码：

package mainimport "fmt"func BubbleSort(arr []int) {n := len(arr)for i := 0; i < n-1; i++ { // 这是第i轮冒泡for j := 0; j < n-i-1; j++ { // 每轮比较的次数逐渐减少if arr[j] > arr[j+1] { // 如果前一个比后一个大，就交换arr[j], arr[j+1] = arr[j+1], arr[j]}}}
}func main() {arr := []int{64, 34, 25, 12, 22, 11, 90} // 这是我们要排序的数组fmt.Println("原数组：", arr) // 先看看原数组长什么样BubbleSort(arr) // 开始冒泡排序啦！fmt.Println("排序后的数组：", arr) // 看看排序后的效果
}

咱来聊聊这个算法。冒泡排序的平均时间复杂度是 O(n²)，最坏情况也是 O(n²)，所以它适合小规模数据的排序。不过，它的优点是实现简单，代码量少，理解起来也容易。就像你去小卖部买包口香糖，虽然口香糖不贵，但也能解解馋。

选择排序：挑挑拣拣选出最小的！

选择排序就像你去商场买东西，你得在一堆商品里找出最便宜的那个。它的原理是：从数组的第 i 个位置开始，找到后面所有元素中的最小值，和第 i 个元素交换。

算法原理 ：从数组第一个元素开始，假设第一个元素是最小值，然后依次与后面元素比较。如果找到更小的元素，就更新最小值的索引。遍历完未排序部分后，将最小值和未排序部分的第一个元素交换位置。重复这一过程，直到整个数组有序。

代码别走开，这就来：

package mainimport "fmt"func SelectionSort(arr []int) {n := len(arr)for i := 0; i < n-1; i++ { // 这是第i次选择minIndex := i // 假设当前元素是最小的for j := i + 1; j < n; j++ { // 找找看有没有更小的if arr[j] < arr[minIndex] {minIndex = j // 更新最小值的索引}}arr[i], arr[minIndex] = arr[minIndex], arr[i] // 把最小值放到前面}
}func main() {arr := []int{64, 25, 12, 22, 11} // 这是我们的数组fmt.Println("原数组：", arr) // 瞧一瞧原数组SelectionSort(arr) // 开始选择排序之旅fmt.Println("排序后的数组：", arr) // 看看排序后的模样
}

这个算法也挺简单的，时间复杂度是 O(n²)，和冒泡排序差不多。不过，它的交换次数比冒泡排序少，因为每次找到最小值才交换一次。这就像是你在网上购物，虽然花了不少时间挑拣，但最终只下单买了一样东西。

插入排序：像插队一样插入正确的位置！

插入排序就像是你在排队买电影票，新来的人要找到合适的位置插入进去，不然就会被后面的人吐槽。这个算法的原理是：把数组分成已排序区和未排序区，然后从未排序区里挑一个元素，在已排序区里找合适的位置插入。

算法原理 ：从第二个元素开始，把它与前面的有序子数组依次比较。如果比前面的元素小，就交换位置，直到找到合适的位置插入。

代码来了：

package mainimport "fmt"func InsertionSort(arr []int) {n := len(arr)for i := 1; i < n; i++ { // 从未排序区开始key := arr[i] // 挑一个元素j := i - 1for j >= 0 && arr[j] > key { // 在已排序区找位置arr[j+1] = arr[j] // 比key大的元素都往后挪j--}arr[j+1] = key // 插入到正确的位置}
}func main() {arr := []int{12, 11, 13, 5, 6} // 这就是我们的数组fmt.Println("原数组：", arr) // 原数组长啥样呢InsertionSort(arr) // 开始插入排序的旅程fmt.Println("排序后的数组：", arr) // 看看排序后的效果
}

插入排序的平均时间复杂度也是 O(n²)，但在数据基本有序的情况下，它的效率很高。这就好比你去一个几乎没人排队的超市，插队都变得轻松多了。

快速排序：分治法的高手！

快速排序可是排序算法里的高手，它用分治法的思想，把数组分成两部分，左边的都比右边的小。然后对左右两部分分别排序，最后整个数组就排好序啦。

算法原理 ：选取一个分区点（通常可以选首元素、尾元素或中间元素），通过一次划分操作，将数组分成左右两个子数组。再对左右子数组递归进行快速排序。

上代码：

package mainimport "fmt"func QuickSort(arr []int) {if len(arr) <= 1 { // 如果数组只有一个元素，就不用排啦return}pivotIndex := partition(arr) // 找到分区点QuickSort(arr[:pivotIndex]) // 递归排序左边QuickSort(arr[pivotIndex+1:]) // 递归排序右边
}func partition(arr []int) int {pivot := arr[0] // 挑一个基准元素j := 0for i := 1; i < len(arr); i++ { // 遍历数组if arr[i] <= pivot { // 如果比基准小j++ // 就放到左边arr[i], arr[j] = arr[j], arr[i] // 交换位置}}arr[0], arr[j] = arr[j], arr[0] // 把基准放到中间return j // 返回分区点
}func main() {arr := []int{10, 7, 8, 9, 1, 5} // 我们的数组fmt.Println("原数组：", arr) // 原数组是啥样呢QuickSort(arr) // 开始快速排序啦fmt.Println("排序后的数组：", arr) // 看看排序后的效果
}

快速排序的平均时间复杂度是 O(n log n)，在大多数情况下都很快。这就像是你开了一辆跑车，在高速公路上飞驰，效率极高。

归并排序：合并的艺术！

归并排序也是分治法的高手，它把数组分成一个个小块，然后把这些小块合并成一个有序的数组。这就像是你有几段绳子，把它们一段段地接起来，最后变成一根长长的绳子。

算法原理 ：将数组一分为二，分别对左右两个子数组进行归并排序。然后合并两个有序子数组。合并过程是归并排序的关键，它将两个有序数组合并成一个有序数组。

代码走一波：

package mainimport "fmt"func MergeSort(arr []int) []int {if len(arr) <= 1 { // 如果数组只有一个元素return arr // 直接返回}mid := len(arr) / 2 // 找到中间点left := MergeSort(arr[:mid]) // 递归排序左边right := MergeSort(arr[mid:]) // 递归排序右边return merge(left, right) // 合并两个有序数组
}func merge(left, right []int) []int {result := make([]int, 0, len(left)+len(right)) // 创建一个结果数组i, j := 0, 0 // 定义两个指针for i < len(left) && j < len(right) { // 遍历两个数组if left[i] <= right[j] { // 如果左边的元素小result = append(result, left[i]) // 就放到结果里i++} else {result = append(result, right[j]) // 否则放右边的元素j++}}result = append(result, left[i:]...) // 把剩下的元素都放到结果里result = append(result, right[j:]...)return result
}func main() {arr := []int{12, 11, 13, 5, 6, 7} // 这是我们的数组fmt.Println("原数组：", arr) // 原数组的样子sortedArr := MergeSort(arr) // 开始归并排序啦fmt.Println("排序后的数组：", sortedArr) // 看看排序后的效果
}

总结

Go 语言提供了简单而强大的语法来实现这些排序算法。不同的排序算法在时间复杂度、空间复杂度和稳定性等方面各有特点。在实际应用中，要根据具体场景选择合适的排序算法。例如，对于小规模数据或基本有序的数据，插入排序可能比较高效；对于大规模数据，快速排序和归并排序通常是更好的选择。理解这些排序算法的实现原理和性能特点，有助于我们更好地进行编程实践和优化。

查看全文

http://www.lryc.cn/news/572892.html