共计 502 个字符,预计需要花费 2 分钟才能阅读完成。
概念
选择排序通过重复找到最小元素并将最小元素放在序列的开头来进行排序。
代码实现
func selectSort(arr []int) []int {for i := 0; i < len(arr)-1; i++ {
minIndex := i
for j := i + 1; j < len(arr); j++ {if arr[j] < arr[minIndex] {minIndex = j}
}
arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
return arr
}
在这个实现中,我们使用两个循环来执行选择排序。外层循环从数组的第一个元素开始,一直到倒数第二个元素,内层循环从当前元素的下一个元素开始,一直到数组的最后一个元素。内层循环将查找未排序部分中的最小值,并将其与未排序部分的第一个元素进行交换。这样,外层循环每次迭代后,未排序部分中的最小值就会被放到已排序部分的末尾。通过这样的迭代,整个数组最终被排序。
时间复杂度
在选择排序的时间复杂度方面,最坏情况下需要进行 n - 1 轮比较,每轮需要进行 n - i 次比较,因此选择排序的时间复杂度为 O(n^2)。然而,选择排序的空间复杂度为 O(1),因为它只需要一个额外的变量来存储最小元素的索引。
正文完
发表至: 算法与数据结构
2023-04-02