概述:选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是,首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

选择排序

选择排序

分类 数据结构 时间复杂度 最优时间复杂度 平均时间复杂度 空间复杂度
选择排序 数组 О(n²) О(n²) О(n²) 总共О(n), 辅助空间 O(1)

代码范例

C语言

1
2
3
4
5
6
7
8
9
10
11
12
void selection_sort(int arr[], int len) {
int i, j, min, temp;
for (i = 0; i < len - 1; i++) {
min = i;
for (j = i + 1; j < len; j++)
if (arr[min] > arr[j])
min = j;
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def selection_sort(L):
N = len(L)
exchanges_count = 0
for i in range(N-1):
min_index = i
for j in range(i+1, N):
if L[min_index] > L[j]:
min_index = j
if min_index != i:
L[min_index], L[i] = L[i], L[min_index]
exchanges_count += 1
print('iteration #{}: {}'.format(i, L))
print('Total {} swappings'.format(exchanges_count))
return L
testlist = [17, 23, 20, 14, 12, 25, 1, 20, 81, 14, 11, 12]
print('Before selection sort: {}'.format(testlist))
print('After selection sort: {}'.format(selection_sort(testlist)))

Java

1
2
3
4
5
6
7
8
9
10
11
12
public static void selection_sort(int[] arr) {
int i, j, min, temp, len = arr.length;
for (i = 0; i < len - 1; i++) {
min = i;
for (j = i + 1; j < len; j++)
if (arr[min] > arr[j])
min = j;
temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
Array.prototype.selection_sort = function() {
var i, j, min;
var temp;
for (i = 0; i < this.length - 1; i++) {
min = i;
for (j = i + 1; j < this.length; j++)
if (this[min] > this[j])
min = j;
temp = this[min];
this[min] = this[i];
this[i] = temp;
}
};

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function swap(&$x, &$y) {
$t = $x;
$x = $y;
$y = $t;
}
function selection_sort(&$arr) {//php的陣列視為基本型別,所以必須用傳參考才能修改原陣列
for ($i = 0; $i < count($arr) - 1; $i++) {
$min = $i;
for ($j = $i + 1; $j < count($arr); $j++)
if ($arr[$min] > $arr[$j])
$min = $j;
swap($arr[$min], $arr[$i]);
}
}

复杂度分析

选择排序的交换操作介于 0(n-1)次之间。选择排序的比较操作为 n(n-1)/2次之间。选择排序的赋值操作介于 03(n-1)次之间。
比较次数 О(n²),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n * (n-1)/2。交换次数O(n),最好情况是,已经有序,交换0次;最坏情况是,逆序,交换n-1次。交换次数比冒泡排序较少,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。
原地操作几乎是选择排序的唯一优点,当空间复杂度要求较高时,可以考虑选择排序;实际适用的场合非常罕见。

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