简单选择排序

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

Table of Contents

环境

平台工具集: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;
        }
    }
}
简单选择排序
Scroll to top