1.2 选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

选择排序基本思想是每次从待排序的数据中选择最小（或最大）的元素，放到已排序序列的末尾，直到全部数据排序完成。

1. 算法步骤初始化：将列表分为已排序部分和未排序部分。初始时，已排序部分为空，未排序部分为整个列表。

查找最小值：在未排序部分中查找最小的元素。

交换位置：将找到的最小元素与未排序部分的第一个元素交换位置。

更新范围：将未排序部分的起始位置向后移动一位，扩大已排序部分的范围。

重复步骤：重复上述步骤，直到未排序部分为空，列表完全有序。

2. 动图演示

假设有一个待排序的列表 [64, 25, 12, 22, 11]，选择排序的过程如下：

第一轮：

未排序部分：[64, 25, 12, 22, 11]。

找到最小值 11，将其与第一个元素 64 交换。

列表变为 [11, 25, 12, 22, 64]。

已排序部分：[11]，未排序部分：[25, 12, 22, 64]。

第二轮：

未排序部分：[25, 12, 22, 64]。

找到最小值 12，将其与第一个元素 25 交换。

列表变为 [11, 12, 25, 22, 64]。

已排序部分：[11, 12]，未排序部分：[25, 22, 64]。

第三轮：

未排序部分：[25, 22, 64]。

找到最小值 22，将其与第一个元素 25 交换。

列表变为 [11, 12, 22, 25, 64]。

已排序部分：[11, 12, 22]，未排序部分：[25, 64]。

第四轮：

未排序部分：[25, 64]。

找到最小值 25，它已经在正确的位置，无需交换。

列表保持不变：[11, 12, 22, 25, 64]。

已排序部分：[11, 12, 22, 25]，未排序部分：[64]。

第五轮：

未排序部分：[64]。

只有一个元素，无需操作。

列表完全有序：[11, 12, 22, 25, 64]。

实例

def selection_sort(arr):

n = len(arr)

for i in range(n):

# 假设当前未排序部分的第一个元素是最小值

min_idx = i

# 在未排序部分中查找最小值的索引

for j in range(i+1, n):

if arr[j] < arr[min_idx]:

min_idx = j

# 将最小值与未排序部分的第一个元素交换

arr[i], arr[min_idx] = arr[min_idx], arr[i]

return arr

# 示例

arr = [64, 25, 12, 22, 11]

sorted_arr = selection_sort(arr)

print(sorted_arr) # 输出: [11, 12, 22, 25, 64]

时间复杂度

最坏情况：O(n²)，无论输入数据是否有序，都需要进行 n(n-1)/2 次比较。

最好情况：O(n²)，即使列表已经有序，仍需进行相同数量的比较。

平均情况：O(n²)。

空间复杂度

O(1)，选择排序是原地排序算法，不需要额外的存储空间。

优缺点

优点：

实现简单，代码易于理解。

原地排序，不需要额外的存储空间。

对于小规模数据集，性能尚可接受。

缺点：

时间复杂度较高，不适合大规模数据集。

不稳定排序算法（如果存在相同元素，可能会改变它们的相对顺序）。

适用场景

数据量较小且对性能要求不高的场景。

需要简单实现的场景。

代码实现

JavaScript 代码实现

实例

function selectionSort(arr) {

var len = arr.length;

var minIndex, temp;

for (var i = 0; i < len - 1; i++) {

minIndex = i;

for (var j = i + 1; j < len; j++) {

if (arr[j] < arr[minIndex]) { // 寻找最小的数

minIndex = j; // 将最小数的索引保存

}

}

temp = arr[i];

arr[i] = arr[minIndex];

arr[minIndex] = temp;

}

return arr;

}

Python 代码实现

实例

def selectionSort(arr):

for i in range(len(arr) - 1):

# 记录最小数的索引

minIndex = i

for j in range(i + 1, len(arr)):

if arr[j] < arr[minIndex]:

minIndex = j

# i 不是最小数时，将 i 和最小数进行交换

if i != minIndex:

arr[i], arr[minIndex] = arr[minIndex], arr[i]

return arr

Go 代码实现

实例

func selectionSort(arr []int) []int {

length := len(arr)

for i := 0; i < length-1; i++ {

min := i

for j := i + 1; j < length; j++ {

if arr[min] > arr[j] {

min = j

}

}

arr[i], arr[min] = arr[min], arr[i]

}

return arr

}

Java 代码实现

实例

public class SelectionSort implements IArraySort {

@Override

public int[] sort(int[] sourceArray) throws Exception {

int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

// 总共要经过 N-1 轮比较

for (int i = 0; i < arr.length - 1; i++) {

int min = i;

// 每轮需要比较的次数 N-i

for (int j = i + 1; j < arr.length; j++) {

if (arr[j] < arr[min]) {

// 记录目前能找到的最小值元素的下标

min = j;

}

}

// 将找到的最小值和i位置所在的值进行交换

if (i != min) {

int tmp = arr[i];

arr[i] = arr[min];

arr[min] = tmp;

}

}

return arr;

}

}

PHP 代码实现

实例

function selectionSort($arr)

{

$len = count($arr);

for ($i = 0; $i < $len - 1; $i++) {

$minIndex = $i;

for ($j = $i + 1; $j < $len; $j++) {

if ($arr[$j] < $arr[$minIndex]) {

$minIndex = $j;

}

}

$temp = $arr[$i];

$arr[$i] = $arr[$minIndex];

$arr[$minIndex] = $temp;

}

return $arr;

}

C 语言

实例

void swap(int *a,int *b) //交換兩個變數

{

int temp = *a;

*a = *b;

*b = temp;

}

void selection_sort(int arr[], int len)

{

int i,j;

for (i = 0 ; i < len - 1 ; i++)

{

int min = i;

for (j = i + 1; j < len; j++) //走訪未排序的元素

if (arr[j] < arr[min]) //找到目前最小值

min = j; //紀錄最小值

swap(&arr[min], &arr[i]); //做交換

}

}

C++

实例

template //整數或浮點數皆可使用，若要使用物件（class）時必須設定大於（>）的運算子功能

void selection_sort(std::vector& arr) {

for (int i = 0; i < arr.size() - 1; i++) {

int min = i;

for (int j = i + 1; j < arr.size(); j++)

if (arr[j] < arr[min])

min = j;

std::swap(arr[i], arr[min]);

}

}

C#

实例

static void selection_sort(T[] arr) where T : System.IComparable{//整數或浮點數皆可使用

int i, j, min, len = arr.Length;

T temp;

for (i = 0; i < len - 1; i++) {

min = i;

for (j = i + 1; j < len; j++)

if (arr[min].CompareTo(arr[j]) > 0)

min = j;

temp = arr[min];

arr[min] = arr[i];

arr[i] = temp;

}

}

Swift

实例

import Foundation

/// 选择排序

///

/// - Parameter list: 需要排序的数组

func selectionSort(_ list: inout [Int]) -> Void {

for j in 0..

var minIndex = j

for i in j..

if list[minIndex] > list[i] {

minIndex = i

}

}

list.swapAt(j, minIndex)

}

}

原文地址：https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/2.selectionSort.md

参考地址：https://zh.wikipedia.org/wiki/%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F