选择排序算法图文详解
- 作者: 摸几格格
- 来源: 51数据库
- 2022-09-23
选择排序是一种比较简单的排序算法，可以对待排序序列实现升序或降序排序，常用于数据量较少的场景。
选择排序算法的实现原理和冒泡排序算法类似，通过不断地比较两个相邻元素的值，找出待排序序列中的最大值或者最小值。不同之处在于，冒泡排序每次遍历都会频繁地交换相邻元素的位置，从而将最大值或最小值移动至序列的开头或者结尾；选择排序在实现时，每次遍历只需要交换 1 次，即可将最大值或最小值移动至序列的开头或结尾。
选择排序算法的平均时间复杂度为O(n2)。
选择排序算法的基本原理
接下来，我们以对如下序列进行升序排序为例，给您讲解选择排序算法的工作原理。
1) 从第一个元素开始遍历，找到序列中最小的元素 10，将其与第 1 个元素 14 互换位置：
2) 从第 2 个元素开始遍历，找到序列中最小的元素 14，将其与第 2 个元素 33 互换位置：
3) 从第 3 个元素开始遍历，找到序列中最小的元素 19 ，将其与第 3 个元素 27 互换位置：
4) 从第 4 个元素开始遍历，找到序列中最小的元素 27，将其与第 4 个元素 33 互换位置：
5) 从第 5 个元素开始遍历，找到序列中最小的元素 33，将其与第 5 个元素 35 互换位置：
6) 从第 6 个元素开始遍历，找到序列中最小的元素 35，由于其就位于第 6 的位置上，因此不做任何操作。
7) 从第 7 个元素开始遍历，找到序列中最小的元素 42，由于其就位于第 7 的位置上，因此不做任何操作：
8) 从第 8 个元素开始遍历，找到序列中最小的元素 44，由于其就位于第 8 的位置上，因此不做任何操作：
由此，整个序列变成了有序序列，选择排序结束。如下的伪代码描述了选择排序的整个过程：
selection_sort(list): //list 为待排序序列
n <- length(list) //记录序列中的元素个数
for i <- 1 to n-1: //从第 1 个元素一直遍历至倒数第 2 个元素
min <- i //初始化最小值为第 i 个元素
for j <- i+1 to n: // 从第 i+1 个元素开始开始遍历序列
if list[j] < list[min]: //查找待排序序列中的最小值
min = j
if min != i: //如果最小值所在的位置不为 i，交换最小值和第 i 个元素的位置
swap list[min] , list[i]
return list
选择排序算法的具体实现
如下为用选择排序算法对 {14,33,27,10,35,19,42,44} 进行升序排序的 C 语言程序：
#include <stdio.h>
#define N 8 //设定待排序序列中的元素个数
//list[N] 为存储待排序序列的数组
void selection_sort(int list[N]) {
int i, j;
int min,temp;
//从第 1 个元素开始遍历，直至倒数第 2 个元素
for (i = 0; i < N-1; i++) {
min = i; //事先假设最小值为第 i 个元素
//从第 i+1 个元素开始遍历，查找真正的最小值
for (j = i + 1; j < N; j++) {
if (list[j] < list[min]) {
min = j;
}
}
//如果最小值所在位置不为 i，交换最小值和第 i 个元素的位置
if (min != j) {
temp = list[min];
list[min] = list[i];
list[i] = temp;
}
}
}
int main() {
int i;
int list[N] = { 14,33,27,10,35,19,42,44 };
//对待排序序列做选择排序
selection_sort(list);
//输出已排序序列中的各个元素
for (i = 0; i < N; i++) {
printf("%d ", list[i]);
}
}
如下为用选择排序算法对 {14,33,27,10,35,19,42,44} 进行升序排序的 Java 程序：
public class Demo {
// list[N] 为存储待排序序列的数组
public static void selection_sort(int[] list) {
int length = list.length;
int i, j;
// 从第 1 个元素开始遍历，直至倒数第 2 个元素
for (i = 0; i < length - 1; i++) {
int min = i; // 事先假设最小值为第 i 个元素
// 从第 i+1 个元素开始遍历，查找真正的最小值
for (j = i + 1; j < length; j++) {
if (list[j] < list[min]) {
min = j;
}
}
// 如果最小值所在位置不为 i，交换最小值和第 i 个元素的位置
if (min != j) {
int temp = list[min];
list[min] = list[i];
list[i] = temp;
}
}
}
public static void main(String[] args) {
int[] list = { 14, 33, 27, 10, 35, 19, 42, 44 };
selection_sort(list);
// 输出已排好序的序列
for (int i = 0; i < list.length; i++) {
System.out.print(list[i] + " ");
}
}
}
如下为用选择排序算法对 {14,33,27,10,35,19,42,44} 进行升序排序的 Python 程序：
格式化复制
#待排序序列 list = [14,33,27,10,35,19,42,44] def selection_sort(): length = len(list) #从第 1 个元素开始遍历，直至倒数第 2 个元素 for i in range(length-1): min = i #事先假设最小值为第 i 个元素 #从第 i+1 个元素开始遍历，查找真正的最小值 for j in range(i+1,length): if list[j] < list[min]: min = j #如果最小值所在位置不为 i，交换最小值和第 i 个元素的位置 if min != j: list[min],list[i] = list[i],list[min] selection_sort() # 输出已排好序的序列 for i in list: print(i,end=" ")
以上程序的输出结果均为：
10 14 19 27 33 35 42 44
