选择排序（Selection Sort）是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。选择排序基本思想是每次从待排序的数据中选择最小（或最大）的元素，放到已排序序列的末尾，直到全部数据排序完成。

一、算法步骤

  1. 初始化：将列表分为已排序和未排序部分。初始时，已排序部分为空，未排序部分为全部。

  2. 查找最小值：在未排序部分中查找最小的元素。

  3. 交换位置：将找到的最小元素与未排序部分的第一个元素交换位置。

  4. 更新范围：将未排序部分的起始位置向后移动一位，扩大已排序部分的范围。

  5. 重复步骤：重复上述步骤，直到未排序部分为空，列表完全有序。

二、动图演示

假设有一个待排序的列表 [64, 25, 12, 22, 11]，选择排序的过程如下：

  1. 第一轮：

    • 未排序部分：[64, 25, 12, 22, 11]。

    • 找到最小值 11，将其与第一个元素 64 交换。

    • 列表变为 [11, 25, 12, 22, 64]。

    • 已排序部分：[11]，未排序部分：[25, 12, 22, 64]。

  2. 第二轮：

    • 未排序部分：[25, 12, 22, 64]。

    • 找到最小值 12，将其与第一个元素 25 交换。

    • 列表变为 [11, 12, 25, 22, 64]。

    • 已排序部分：[11, 12]，未排序部分：[25, 22, 64]。

  3. 第三轮：

    • 未排序部分：[25, 22, 64]。

    • 找到最小值 22，将其与第一个元素 25 交换。

    • 列表变为 [11, 12, 22, 25, 64]。

    • 已排序部分：[11, 12, 22]，未排序部分：[25, 64]。

  4. 第四轮：

    • 未排序部分：[25, 64]。

    • 找到最小值 25，它已经在正确的位置，无需交换。

    • 列表保持不变：[11, 12, 22, 25, 64]。

    • 已排序部分：[11, 12, 22, 25]，未排序部分：[64]。

  5. 第五轮：

    • 未排序部分：[64]。

    • 只有一个元素，无需操作。

    • 列表完全有序：[11, 12, 22, 25, 64]。

 三、代码实现 

       实例

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 标记是否发生了交换
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                # 交换位置
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # 如果没有发生交换，说明列表已经有序，提前退出
        if not swapped:
            break
    return arr

# 示例
arr = [5, 3, 8, 4, 6]
sorted_arr = bubble_sort(arr)
print(sorted_arr)  # 输出: [3, 4, 5, 6, 8]

        JavaScript

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

        Python

def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

        Go

func selectionSort(arr []int) []int {
        length := len(arr)
        for i := 0; i < length-1; i++ {
                min := i
                for j := i + 1; j < length; j++ {
                        if arr[min] > arr[j] {
                                min = j
                        }
                }
                arr[i], arr[min] = arr[min], arr[i]
        }
        return arr
}

        Java

public class SelectionSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        // 总共要经过 N-1 轮比较
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;

            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }

        }
        return arr;
    }
}

        PHP

function selectionSort($arr)
{
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        $temp = $arr[$i];
        $arr[$i] = $arr[$minIndex];
        $arr[$minIndex] = $temp;
    }
    return $arr;
}

        C

void swap(int *a,int *b) //交換兩個變數
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selection_sort(int arr[], int len) 
{
    int i,j;

        for (i = 0 ; i < len - 1 ; i++) 
    {
                int min = i;
                for (j = i + 1; j < len; j++)     //走訪未排序的元素
                        if (arr[j] < arr[min])    //找到目前最小值
                                min = j;    //紀錄最小值
                swap(&arr[min], &arr[i]);    //做交換
        }
}

        C++

template<typename T> //整數或浮點數皆可使用，若要使用物件（class）時必須設定大於（>）的運算子功能
void selection_sort(std::vector<T>& arr) {
        for (int i = 0; i < arr.size() - 1; i++) {
                int min = i;
                for (int j = i + 1; j < arr.size(); j++)
                        if (arr[j] < arr[min])
                                min = j;
                std::swap(arr[i], arr[min]);
        }
}

        C#

static void selection_sort<T>(T[] arr) where T : System.IComparable<T>{//整數或浮點數皆可使用
        int i, j, min, len = arr.Length;
        T temp;
        for (i = 0; i < len - 1; i++) {
                min = i;
                for (j = i + 1; j < len; j++)
                        if (arr[min].CompareTo(arr[j]) > 0)
                                min = j;
                temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
        }
}

        Rust

fn selection_sort<T:Ord + Debug>(array: &mut [T]) {
    for i in 0..array.len() {
        let mut temp = i;
        for j in i..array.len() {
            if array[j] < array[temp] {
                temp = j;
            }
        }
        array.swap(i, temp);
    }
}

        Swift 

import Foundation
/// 选择排序
///
/// - Parameter list: 需要排序的数组
func selectionSort(_ list: inout [Int]) -> Void {
    for j in 0..<list.count - 1 {
        var minIndex = j
        for i in j..<list.count {
            if list[minIndex] > list[i] {
                minIndex = i
            }
        }
        list.swapAt(j, minIndex)
    }
}

        Kotlin

class SelectionSort { 
    /** 
    * 拓展IntArray为他提供数据两个数交换位置的方法 
    * @param i 第一个数的下标 
    * @param j 第二个数的下标 
    */ 
    fun IntArray.swap(i:Int,j:Int){ 
        var temp=this[i] 
        this[i]=this[j] 
        this[j]=temp 
    } 
    fun selectionSort(array: IntArray):IntArray{
        for (i in array.indices){ 
            //假设最小值是i 
            var min=i 
            var j=i+1 
            while (j in array.indices){ 
                if (array[j]<array[min]){ 
                    min=j
                }
                j++ 
            } 
            if (i!=min){
                array.swap(i,min) 
            } 
        } 
        return array; 
    }
}

四、复杂度

1、时间复杂度

  • 最坏情况：O(n²)，无论输入数据是否有序，都需要进行 n(n-1)/2 次比较。

  • 最好情况：O(n²)，即使列表已经有序，仍需进行相同数量的比较。

  • 平均情况：O(n²)。

2、空间复杂度

  • O(1)，选择排序是原地排序算法，不需要额外的存储空间。

五、优缺点

  • 优点：

    • 实现简单，代码易于理解。

    • 原地排序，不需要额外的存储空间。

    • 对于小规模数据集，性能尚可接受。

  • 缺点：

    • 时间复杂度较高，不适合大规模数据集。

    • 不稳定排序算法（如果存在相同元素，可能会改变它们的相对顺序）。


————————————————

                            版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
                        
原文链接：https://blog.csdn.net/yjl_201110086213/article/details/149461437

# 排序算法 # 算法 # 数据结构
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

【计算机视觉】Pixel逐像素分类&Mask掩码分类理解摘要

avatar 魔乐社区

计算机视觉（opencv）实战三十二——CascadeClassifier 人脸微笑检测（摄像头）

本文从原理到实现，详细介绍了基于 OpenCV Haar 分类器的人脸与微笑检测：讲解了 Haar 特征和级联检测原理。对代码逐行拆解并解释参数含义。画出完整流程图，帮助理解执行过程。给出了常见问题和优化建议，甚至扩展到深度学习方法。这种方法简单、轻量、实时性好，非常适合入门和小型应用项目。但如果需要更高准确率和更强鲁棒性，建议使用深度学习检测器替代 Haar 分类器。

avatar 魔乐社区
cover

小杰机器学习（seven）——贝叶斯分类

avatar 魔乐社区