白筱汐

想都是问题，做都是答案

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
}