当前位置：首页 > article >正文

排序与算法：选择排序

article 2025/2/21 9:52:30

执行效果
选择排序的执行效果是这样的：

呃……看不懂吗？没关系，接着往下看介绍

算法介绍
选择排序（Selection sort）是一种简单直观的排序算法。选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对 n 个元素的表进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

算法档案

时间复杂度：O(n2)
最优时间复杂度：O(n2)
平均时间复杂度：O(n2)
空间复杂度：总共 O(n)，需要辅助空间 O(1)
稳定性：不稳定

算法步骤

在序列中找到最小（大）元素
把它存放到排序序列的起始位置
重复 1 和 2 两个步骤，直到所有元素均排序完毕

算法实现

#include <stdio.h>

void selection_sort(int array[], int length);

void selection_sort(int array[], int length)
{
        int i, j, min, temp;

        for (i = 0; i < length - 1; i++)
        {
                min = i;
                for (j = i + 1; j < length; j++)
                {
                        if (array[zxsq-anti-bbcode-min] > array[zxsq-anti-bbcode-j])
                        {
                                min = j;
                        }
                }
                temp = array[zxsq-anti-bbcode-min];

                array[zxsq-anti-bbcode-min] = array[zxsq-anti-bbcode-i];

                array[zxsq-anti-bbcode-i] = temp;
        }
}


int main(void)
{
        int array[] = {73, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109};
        int i, length;

        length = sizeof(array) / sizeof(array[zxsq-anti-bbcode-0]);
        selection_sort(array, length);
        printf("排序后的结果是：");

        for (i = 0; i < length; i++)
        {
                printf("%d ", array[zxsq-anti-bbcode-i]);
        }

        putchar('\n');
        return 0;
}

程序实现如下：