首页 > 编程笔记 > 算法笔记 阅读：12616

选择排序算法

通义灵码
对数据量较少的序列实现升序或降序排序，可以考虑使用选择排序算法，它对应的时间复杂度为O(n2)。

排序排序算法对含有 n 个元素的序列实现排序的思路是：每次从待排序序列中找出最大值或最小值，查找过程重复 n-1 次。对于每次找到的最大值或最小值，通过交换元素位置的方式将它们放置到适当的位置，最终使整个序列变成有序序列。

举个例子，我们使用选择排序算法对 {14, 33, 27, 10, 35, 19, 42, 44} 完成升序排序，需要经历以下几个步骤：
1) 遍历整个待排序序列，从中找到最小值 10 并与第一个元素 14 交换位置：


2) 待排序序列变成 {33, 27, 14, 35, 19, 42, 44}，从中找到最小值 14 并与 33 交换位置：


3) 待排序序列变成 {27, 33, 35, 19, 42, 44}，从中找到最小值 19 并与 27 交换位置：


4) 待排序序列变成 {33, 35, 27, 42, 44}，从中找到最小值 27 并与 33 交换位置：


5) 待排序序列变成 {35, 33, 42, 44}，从中找到最小值 33 并与 35 交换位置：


6) 待排序序列变成 {35, 42, 44}，从中找到最小值 35，它的位置无需变动：


7) 待排序序列变成 {42, 44}，从中找到最小值 42，它的位置无需变动：


对于包含 n 个元素的待排序序列，选择排序算法中只需要找出 n-1 个“最小值”，最后剩下的元素的值必然最大。由此，我们就得到了一个升序序列 {10, 14, 19, 27, 33, 35, 42, 44}。

选择排序算法可以看作是冒泡排序算法的“改良版”。和后者相比，选择排序算法大大减少了交换数据存储位置的操作。

选择排序算法的具体实现

如下是描述选择排序算法的伪代码： 
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 语言程序： 
  1. #include <stdio.h>
  2. #define N 8   //设定待排序序列中的元素个数
  3. //list[N] 为存储待排序序列的数组
  4. void selection_sort(int list[N]) {
  5.     int i, j;
  6.     int min,temp;
  7.     //从第 1 个元素开始遍历，直至倒数第 2 个元素
  8.     for (i = 0; i < N-1; i++) {
  9.         min = i;   //事先假设最小值为第 i 个元素
  10.         //从第 i+1 个元素开始遍历，查找真正的最小值
  11.         for (j = i + 1; j < N; j++) {
  12.             if (list[j] < list[min]) {
  13.                 min = j;
  14.             }
  15.         }
  16.         //如果最小值所在位置不为 i，交换最小值和第 i 个元素的位置
  17.         if (min != i) {
  18.             temp = list[min];
  19.             list[min] = list[i];
  20.             list[i] = temp;
  21.         }
  22.     }
  23. }
  24. int main() {
  25.     int i;
  26.     int list[N] = { 14,33,27,10,35,19,42,44 };
  27.     //对待排序序列做选择排序
  28.     selection_sort(list);
  29.     //输出已排序序列中的各个元素
  30.     for (i = 0; i < N; i++) {
  31.         printf("%d ", list[i]);
  32.     }
  33. }

如下为使用选择排序算法对 {14, 33, 27, 10, 35, 19, 42, 44} 实现升序排序的 Java 程序： 
  1. public class Demo {
  2.     // list[N] 为存储待排序序列的数组
  3.     public static void selection_sort(int[] list) {
  4.         int length = list.length;
  5.         int i, j;
  6.         // 从第 1 个元素开始遍历，直至倒数第 2 个元素
  7.         for (i = 0; i < length - 1; i++) {
  8.             int min = i; // 事先假设最小值为第 i 个元素
  9.             // 从第 i+1 个元素开始遍历，查找真正的最小值
  10.             for (j = i + 1; j < length; j++) {
  11.                 if (list[j] < list[min]) {
  12.                     min = j;
  13.                 }
  14.             }
  15.             // 如果最小值所在位置不为 i，交换最小值和第 i 个元素的位置
  16.             if (min != i) {
  17.                 int temp = list[min];
  18.                 list[min] = list[i];
  19.                 list[i] = temp;
  20.             }
  21.         }
  22.     }
  23.  
  24.     public static void main(String[] args) {
  25.         int[] list = { 14, 33, 27, 10, 35, 19, 42, 44 };
  26.         selection_sort(list);
  27.         // 输出已排好序的序列
  28.         for (int i = 0; i < list.length; i++) {
  29.             System.out.print(list[i] + " ");
  30.         }
  31.     }
  32. }

如下为使用选择排序算法对 {14, 33, 27, 10, 35, 19, 42, 44} 实现升序排序的 Python 程序： 
  1. #待排序序列
  2. list = [14,33,27,10,35,19,42,44]
  3. def selection_sort():
  4.     length = len(list)
  5.     #从第 1 个元素开始遍历，直至倒数第 2 个元素
  6.     for i in range(length-1):
  7.         min = i  #事先假设最小值为第 i 个元素
  8.         #从第 i+1 个元素开始遍历，查找真正的最小值
  9.         for j in range(i+1,length):
  10.             if list[j] < list[min]:
  11.                 min = j
  12.         #如果最小值所在位置不为 i，交换最小值和第 i 个元素的位置
  13.         if min != i:
  14.             list[min],list[i] = list[i],list[min]
  15.  
  16. selection_sort()
  17. # 输出已排好序的序列
  18. for i in list:
  19.     print(i,end=" ")

以上程序的输出结果均为：

10 14 19 27 33 35 42 44

相关文章