十大排序算法-选择排序(golang实现)
2021-08-22 20:00:00 # 数据结构与算法

选择排序

简单描述

首先,找到数组中最小的那个元素,其次,将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次,在剩下的元素中找到最小的元素,将它与数组的第二个元素交换位置。如此往复,直到将整个数组排序。这种方法我们称之为选择排序。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func SelectionSort(arr []int) []int {
for i := 0; i < len(arr); i++ {
min := i

for j := i + 1; j < len(arr); j++ {
if arr[min] > arr[j] {
temp := arr[j]
arr[j] = arr[min]
arr[min] = temp
}
}
}
return arr
}

总结

  1. 时间复杂度:O(n2)
  2. 空间复杂度:O(1)
  3. 非稳定排序
  4. 原地排序