选择排序是一种比较简单的排序算法,可以对待排序序列实现升序或降序排序,常用于数据量较少的场景。
选择排序算法的实现原理和冒泡排序算法类似,通过不断地比较两个相邻元素的值,找出待排序序列中的最大值或者最小值。不同之处在于,冒泡排序每次遍历都会频繁地交换相邻元素的位置,从而将最大值或最小值移动至序列的开头或者结尾;选择排序在实现时,每次遍历只需要交换 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