十大排序—选择排序

Akari2023-11-092024-03-09

[TOC]

参考网站

1.2 选择排序 | 菜鸟教程
数组、链表的基本操作都涉及到排序，排序有很多种，根据情况选择合适的算法即可。
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

动图演示

理解

就是每一次从未排序的所有元素中，“选出”最小（或最大）的，放在首位，然后递推其余未排序的元素，每一次都选出余下最小的。

例题

ZZULIOJ-Contest 1908-I: 混乱的成绩表

Zero 是一名学习委员，他负责很多有关学习上的任务，今天辅导员给了他一张成绩单，这个成绩单是按学号排序的，但是它是成绩单，应该按成绩排序。Zero 作为一个 acmer，对排序还算了解，但他想考考你，你能完成这个任务吗？

一个正整数 n，代表成绩单上学生的人数(n <= 2000)
接下来 n 行，每行两个整数 ID 和 x，ID是学生的编号(递增给出），x 是学生成绩 (0 <= x <= 100)

输出按成绩排名的成绩单，成绩越高，排名越靠前，相同成绩的人 ID 较小的排名在前

结构体代码选择排序

考察点：结构体、排序
很明显本题让我们对成绩排序，但难点在于每个人的成绩和学号是绑定在一起的，这个时候我们就有两种选择：

两个数组，排序时一起交换这两数组的值
开一个结构体，排序时交换结构体的值

#include <stdio.h>
struct Student
{
    int id, soc;    // 学号 成绩
}a[2001];

void Sort_select(struct Student a[], int n);

int main(void)
{
    int n;

    scanf("%d", &n);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d", &a[i].id, &a[i].soc);
    }

    Sort_select(a, n);  //调用函数

    for(int i=0;i<n;i++)
    {
        printf("%d %d\n", a[i].id, a[i].soc);
    }

    return 0;
}

// 选择排序的实现
void Sort_select(struct Student a[], int n)
{
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            int flag = 0;   // 是否需要排序，0 代表不需要，1 代表需要
            
            if(a[i].soc < a[j].soc)
            {
                flag = 1;   // 成绩较高的在前
            }
            if(a[i].soc == a[j].soc && a[i].id > a[j].id)
            {
                flag = 1;   // 相同成绩，编号较小的在前
            }
            
            if(flag)
            {   
                // 交换
                struct Student t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
    }
}

数组代码选择排序

#include <stdio.h>

int id[2001], sco[2001];    // 1.为什么放外面？
void Sort_select(int n);    // 2.函数定义为什么只有n？

int main(void)
{
    int n;
    scanf("%d", &n);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d", &id[i], &sco[i]);
    }

    Sort_select(n);

    for(int i=0;i<n;i++)
    {
        printf("%d %d\n", id[i], sco[i]);
    }

    return 0;
}

// 选择排序的实现
void Sort_select(int n)
{
    for(int i=0;i<n-1;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            // 是否需要排序，0 代表不需要，1 代表需要
            int flag = 0;
            
            if(sco[i] < sco[j])
            {
                flag = 1;   // 成绩较高在前
            }
            if(sco[i] == sco[j] && sco[i] > sco[j])
            {
                flag = 1;   // 相同成绩，编号较小的在前
            }
            
            if(flag)        // 交换
            {
                int t = id[i];
                id[i] = id[j];
                id[j] = t;
                t = sco[i];
                sco[i] = sco[j];
                sco[j] = t;
            }
        }
    }
}

Tip

1. 为什么数组放外面？

将数组定义放在main函数之外更好，因为这样可以使得数组在整个程序中都可见，而不仅仅是在main函数中可见。这样可以使得代码更加清晰易懂。如果数组定义在main函数内部，那么它的作用域就只在main函数内部，而在main函数外部就无法访问该数组。
此外，如果数组定义在main函数内部，那么它的内存分配在栈区内，而栈区的内存是比较小的。因此，如果数组比较大，就会出现爆出的问题，程序无法访问内存就会出错。相对的，如果数组定义在main函数外部，那么它的内存分配在数据区内，数据区的内存较大，所以开数组开在数据区/main函数外面，就不易出现这样的问题。