算法基础二：选择排序

选择排序（ Selection sort）是一种简单直观的排序算法。它的工作原理是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

 选择排序算法通过选择和交换来实现排序，其排序流程如下：

（1）首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
（2）接着从剩下的n-1个数据中选择次小的1个元素，将其和第2个位置的数据交换
（3）然后，这样不断重复，直到最后两个数据完成交换。最后，便完成了对原始数组的从小到大的排序。

知识点：①无论是平均还是最坏情况，时间复杂度都是O(n^2)

              ②在数据规模较小时效率较好，适用于对数据量较少的序列实现升序或降序排序

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

              ④稳定性：不稳定

C语言代码

#include <stdio.h>

// 函数声明
void Selection_sort(int a[], int len);

int main() {
    int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
    int len = sizeof(arr) / sizeof(arr[0]);  // 计算数组长度

    Selection_sort(arr, len);  // 调用选择排序函数

    // 打印排序后的数组
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

// 选择排序函数
void Selection_sort(int arr[], int len)
{
    for (int i = 0; i < len -1; i++)//
    {
        int min = i;//第一个值默认最小

        for (int j = i+1; j < len; j++)//挨个比较一遍找出最小的值
        {
            if (arr[j] < arr[min])//如果比默认最小值小，把他的位置记录下来
            {
                min = j;
            }
        }
        if (min != i)//如果默认最小的位置不是实际最小的位置，则把此位置的数交换
        {
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
    }
}

如下为使用选择排序算法对 {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
        if min != i:
            list[min],list[i] = list[i],list[min]


selection_sort()
#输出排列好的数据
for i in list:
    print(i,end=" ")