白筱汐

想都是问题,做都是答案

0%

选择排序

前言

选择排序是十大经典排序算法之一,选择排序的时间复杂度为 O(n^2)。

基本思路:

  1. 找出数组中最小的元素,与第一个元素交换位置
  2. 重复这个过程,直到排序完成

js代码演示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 选择排序
function selectionSort(array) {
for (let i = 0; i < array.length; i++) {
// 保存当前最小数的索引
let minIndex = i
for (let j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j
}
}
if (i !== minIndex) {
swap(array,i,minIndex)
}
}
return array
}

function swap(arr,i,j) {
const temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}

go代码演示:

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++ {
minIndex := i // 保存当前最小数的索引
for j := i + 1; j < len(arr); j++ { // 每次只用从i的后一个位置开始查找
if arr[j] < arr[minIndex] {
minIndex = j
}
}
if minIndex != i {
arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
}
return arr
}