本文将介绍简单选择排序和直接插入排序，并介绍 sort 函数及其用法。

一、选择排序

选择排序是最简单的排序算法之一，主要介绍众多选择排序算法中最常用的简单选择排序。

简单选择排序是指，进行 n 趟操作，每一轮操作遍历序列后找出最小的一项，使其归位（将该项与待排序序列中的首项交换）。

算法代码如下：

void SelectSort(int A[], int n){
	for (i = 0; i < n; i++){
		min = i;
		for (j = i; j < n; j++)
			if (A[j] < A[min])  min = j;
		swap(a[i], a[min]);
	}
}

​

二、插入排序

主要介绍直接插入排序。

直接插入排序是指，遍历序列，将每一个新的元素插入到已排序序列中的合适位置，使已排序序列在插入新元素后仍然保持有序状态。

算法代码如下：

在已排序序列中从后往前扫描，若新元素应该插到前面，则将已排序序列依次后移。

因为序列的后移会覆盖新元素，所以用 temp 保存其值。

void InsertSort(int A[], int n){
	for (i = 1; i < n; i++){
		temp = A[i];
		for (j = i - 1; j >= 0 && A[j] > temp; j--){
			A[j + 1] = A[j];
		}
		A[j + 1] = temp;
	}
}

​

三、排序题和 sort 函数的应用

考试中的排序题大部分只需要得到排序的最终结果，而不需要去写排序的完整过程（例如冒泡排序、快速排序等），因此推荐直接使用 C 语言中的库函数 qsort 或是 C++ 中的 sort 函数进行排序，这将有助于读者把更多的精力用在题目本身上。

在一些题目中，使用自己编写的排序可能会出现超时的情况，例如：

每日一题 20210226 - LD’s BLOG

考虑到 qsort 的使用需要对指针的用法由一定了解，且写法上也没有sort函数简洁，因此更推荐读者使用 C++ 中的 sort 函数。

关于 sort 函数的用法：

此部分为第六章的内容，待更新

1.相关结构体的定义

对于排序题，往往会在题目中给出个体的许多信息，例如学生的姓名、准考证号、分数等。这些信息可以都放置到结构体中，用结构体表示单个个体及其信息，结构体数组表示多个个体。

struct Student{
	char name[10];
	char id[10];
	int score;
	int rank;
};
struct Student stu[100];

2. cmp 函数的编写

bool cmp(struct Student a, struct Student b){
	if (a.score > b.score)  return true;
	else if(a.score == b.score){
		if (strcmp(a.name, b.name) < 0)  return true;
		else return false;
	}
	else return false;
}

strcmp(str1, str2);

是 string.h 头文件下用于比较两个 char 型数组的字典序大小的函数。当 str1 的字典序小于 str2 时，返回一个负数；相等时返回 0 ；否则返回一个正数。

3.排名的实现

许多排序题都会有要求在排序后计算出每个个体的排名，并且规则一般是：分数不同的排名不同，分数相同的排名相同但占用一个排位。例如由五个学生的分数分别是 90、88、88、88、86 ，那么这五个学生的排名分别为 1、2、2、2、5 。

对于这种要求，一般都需要在结构体类型定义时就把排名这一项加到结构体中。于是在数组排序完成后就有下面两种方法实现排名的计算。

(1) 方法 1

先将数组第一个个体（假设数组下标从 0 开始）的排名记为 1 ，然后遍历剩余个体。如果当前个体的分数等于上一个体的分数，那么当前个体的排名等于上一个个体的排名；否则个体的排名等于数组下标加 1 。代码如下：

stu[0].rank = 1;
for (i = 1; i < n; i++){
	if (stu[i].score == stu[i - 1].score)  
		stu[i].rank = stu[i - 1].rank;
	else
		stu[i].rank = i + 1;
}

(2) 方法 2

有些题目中不一定需要真的把排名记录下来，而是直接输出即可，那么也可以用这样的方法：

令 int 变量 rank 的初值为 1 ，然后遍历所有个体；如果当前个体不是第一个个体且当前个体的分数不等于上一个个体的分数，那么令 r 等于数组下标加 1，这时 r 就是当前个体的排名，直接输出即可。这种做法适用于需要输出的信息过多，防止代码冗长的情况。

r = 1;
for (i = 0; i < n; i++){
    // 若需要更新，则rank = i + 1 ;否则rank不变
	if (i > 0 && stu[i].score != stu[i - 1].score)
		r = i + 1;
	printf("%d", r);
}

​

参考

• 算法笔记