简单选择排序

最近更新于 2024-05-06 07:58

环境

平台工具集：Visual Studio 2022 v143
C 语言标准：C17
字符集：Unicode

算法实现

简单选择排序的思想感觉和冒泡排序比较相似。
简单选择排序，每一轮找出未排序部分的最小值的下标，然后将这个最小值和当前轮次对应下标的数交换。比如第一轮找出的最小值和下标 0 交换，第二轮从下标 1 开始找最小值记录其下标，然后将最小值和下标 1 的数交换，第三轮从下标 2 开始找最小值，接着和下标 2 的数交换……
相比于冒泡排序，并不需要每次都去交换，只需要记录其下标，直到本轮找到最小值，最后才交换，性能会好一点
时间复杂度为 O(n^2)，不稳定的排序算法

void sort(int array[], int n)
{
    for (int i = 0; i < n - 1; ++i)
    {
        int minIdx = i;
        for (int j = i + 1; j < n; ++j)
        {
            if (array[minIdx] > array[j])
            {
                minIdx = j;
            }
        }
        if (minIdx != i)
        {
            int tmp = array[i];
            array[i] = array[minIdx];
            array[minIdx] = tmp;
        }
    }
}