选择排序
选择排序(selection sort)是一种原地(in-place)排序算法,适用于数据量较少的情况。由于选择操作是基于键值的且交换操作只在需要时才执行,所以选择排序长用于数值较大和键值较小的文件。
思想: 对一个数组进行排序,从未排序的部分反复找到最小的元素,并将其放在开头。
给定长度为
的序列和位置索引
的数组,选择排序将:
-
遍历一遍序列,寻找序列中的最小值。在
范围内找出最小值minValue
的位置minIndex
, -
用当前位置的值交换最小值。第 i 项的值与交换 minIndex 的值交换,
swap(nums[i],nums[minIndex])
-
对所有元素重复上述过程,直到整个序列排序完成。将下限
增加1,并重复步骤 1 直到
。
伪代码:
func selectionSort(nums []int, length int) {
for i := 0; i < length-1; i++ { // O(N)
minValue = nums[minIdx] // O(N)
swap(nums[i], nums[minIndex]); // O(1), X may be equal to L (no actual swap)
}
}
复制代码
动画演示
Go 代码实现
package main
import "fmt"
func main() {
unsorted := []int{40, 13, 20, 8, 12, 10, 27}
length := len(unsorted)
selectionSort(unsorted, length)
for i := 0; i < length; i++ {
fmt.Printf("%d\t", unsorted[i])
}
}
func selectionSort(nums []int, length int) {
var minIdx int // 被选择的最小的值的位置
for i := 0; i < length-1; i++ {
minIdx = i
// 每次循环的第一个元素为最小值保存
var minValue = nums[minIdx]
for j := i; j < length-1; j++ {
if minValue > nums[j+1] {
minValue = nums[j+1]
minIdx = j + 1
}
}
// 如果最小值的位置改变,将当前的最小值位置保存
if i != minIdx {
var temp = nums[i]
nums[i] = nums[minIdx]
nums[minIdx] = temp
}
}
}
复制代码
运行结果为:
[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 数据结构\选择排序\main.go"\
8 10 12 13 20 27 40
复制代码
总结
选择排序的优点:
- 易于实现,容易理解
- 原地排序(不需要额外的存储空间),即 空间复杂度为
缺点:
- 扩展性较差
- 时间复杂度为
稳定性:
- 选择排序是不稳定的排序算法。
近期评论