3.选择排序

算法 > 排序算法算法排序算法

发布时间 : 2024-04-14 17:25

字数:1.7k 阅读 :

评论:

3.选择排序

3.选择排序

3.1 基础知识

核心思想

每一轮在未排序区选择最小的元素，与未排序区的第一个元素交换位置。不断缩小未排序区域扩大排序区直到完成排序。

算法步骤

初始状态：将整个数组分为已排序区和未排序区，初始时已排序区为空，未排序区为整个数组。
每一轮选择最小元素：在未排序区中找到最小的元素，并记录其索引。
交换最小元素：将找到的最小元素与未排序区的第一个元素交换位置。这样，未排序区的最小元素被移到已排序区的末尾。
更新已排序区和未排序区：将已排序区的范围扩大，未排序区的范围缩小。已排序区的末尾即为刚刚找到的最小元素的位置。
重复直至排序完成：重复上述步骤，直至未排序区为空。每一轮选择和交换都会确定一个未排序区的最小元素，最终完成整个数组的排序。

时间复杂度

选择排序的最坏、平均、最好情况下的时间复杂度都是 O(n^2)。每一轮需要在未排序区域中找到最小（或最大）元素，需要进行 n-1 次比较。

空间复杂度

选择排序是一种原地排序算法，空间复杂度为 O(1)。

稳定性

选择排序是不稳定的。是因为在选择最小元素的过程中，可能会改变相同元素之间的相对顺序。举个简单的例子：假设有一个数组 [5A, 5B, 2 , 9]，我们希望按照数字的大小对数组进行升序排序。在第一轮选择排序时，5A和2交换了位置，导致5A和5B相对位置不稳定。

代码步骤

外层循环：通过外层循环，控制整个排序的轮数。每一轮，都会在未排序区域选择一个最小的元素，将其放到已排序区域的末尾。
记录最小元素索引：在每一轮开始时，假定当前轮次的第一个元素是未排序区域的最小元素，记录其索引为 minIndex。
查找最小元素：通过内层循环，从未排序区域的剩余元素中找到最小的元素，记录其索引为 minIndex。
交换最小元素：将找到的最小元素与未排序区域的第一个元素进行交换，确保最小元素放在已排序区域的末尾。
输出交换后的数组：在每次交换后，输出当前数组的状态，显示排序的过程。
重复直到完成：通过不断重复上述步骤，直到整个数组完全有序。每一轮都会确定一个未排序区域的最小元素，将其放到已排序区域的末尾。

总结说明

尽管选择排序的时间复杂度与冒泡排序相似，但在实际应用中，选择排序通常比冒泡排序稍快，因为它每一轮只进行一次交换操作。然而，对于大规模数据集，更高效的排序算法可能更为适用。

3.2 思路框架

static void SelectionSort(ref int[] array)
{
    循环：有多少元素循环多少-1轮
    {
        定义最小值索引标识为i（i是当前第几次循环，也是当前要确定元素的位置）

        循环：从i+1的位置一直往后找元素
        {
            如果元素值更小就记录到最小值索引
        }

        交换i和最小值索引的对应元素
    }
}

3.3 纯净代码

static void SelectionSort(ref int[] array)
{
    for (int i = 0; i < array.Length - 1; i++)
    {
        int minIndex = i;

        for (int j = i + 1; j < array.Length; j++)
        {
            if (array[j] < array[minIndex])
            {
                minIndex = j;
            }
        }

        SortHelpTool.Swap(ref array[i], ref array[minIndex]);
    }
}

require("Lesson01_SortHelpTool")

-- 排序函数
function SelectionSort(array)

    for i = 1, #array do

        local minIndex = i

        for j = i + 1, #array do
            if array[j] < array[minIndex] then
                minIndex = j
            end
        end

        SortHelpTool.Swap(array, i, minIndex)
        
    end
end

SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序前")

SelectionSort(SortHelpTool.arrayToSort)

SortHelpTool.PrintArray(SortHelpTool.arrayToSort, "排序后")

3.4 带注释代码

using System;
using Lesson01_概述;

class Program
{
    static void Main()
    {
        // 输出排序前的数组
        Console.WriteLine("排序前的数组:");
        SortHelpTool.PrintArray(SortHelpTool.arrayToSort);

        // 调用选择排序函数
        SelectionSort(ref SortHelpTool.arrayToSort);

        // 输出排序后的数组
        Console.WriteLine("排序后的数组:");
        SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
    }

    // 选择排序函数
    static void SelectionSort(ref int[] array)
    {
        // 数组有多长，一共就有多少-1轮，-1是因为最后一轮排序区已经选择了array.Length - 1个数，最后一个数自动有序
        for (int i = 0; i < array.Length - 1; i++)
        {
            // 记录未排序区的最小元素索引
            int minIndex = i;

            // 从未排序区找到最小元素的索引
            for (int j = i + 1; j < array.Length; j++)
            {
                // 更新最小元素的索引
                if (array[j] < array[minIndex])
                {
                    minIndex = j;
                }
            }

            // 将最小元素与未排序区的第一个元素交换位置
            SortHelpTool.Swap(ref array[i], ref array[minIndex]);

            // 输出排序中的数组
            Console.WriteLine($"第{i + 1}轮 选择最小元素与第{i + 1}个元素进行交换 交换后的数组:");
            SortHelpTool.PrintArray(SortHelpTool.arrayToSort);
        }
    }
}

3.5 运行结果

排序前的数组:
5 2 8 1 7 3 10 4 6 9

第1轮选择最小元素与第1个元素进行交换交换后的数组:
1 2 8 5 7 3 10 4 6 9
第2轮选择最小元素与第2个元素进行交换交换后的数组:
1 2 8 5 7 3 10 4 6 9
第3轮选择最小元素与第3个元素进行交换交换后的数组:
1 2 3 5 7 8 10 4 6 9
第4轮选择最小元素与第4个元素进行交换交换后的数组:
1 2 3 4 7 8 10 5 6 9
第5轮选择最小元素与第5个元素进行交换交换后的数组:
1 2 3 4 5 8 10 7 6 9
第6轮选择最小元素与第6个元素进行交换交换后的数组:
1 2 3 4 5 6 10 7 8 9
第7轮选择最小元素与第7个元素进行交换交换后的数组:
1 2 3 4 5 6 7 10 8 9
第8轮选择最小元素与第8个元素进行交换交换后的数组:
1 2 3 4 5 6 7 8 10 9
第9轮选择最小元素与第9个元素进行交换交换后的数组:
1 2 3 4 5 6 7 8 9 10

排序后的数组:
1 2 3 4 5 6 7 8 9 10

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com