所谓排序，是要整理表中的记录，使之按关键字递增（或递减）的有序排列。
内排序全称为内部排序。内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
待排序的顺序表中数据元素的类型定义如下（类似于被查找的顺序表元素类型）：
typedef int KeyType; // 关键字的数据类型
typedef struct
{
KeyType key;
InfoType data; // 其他数据, 可选
} RecType;
插入排序
插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。
两种插入排序方法：
- 直接插入排序（含二分插入排序）
- 希尔排序
直接插入排序
直接插入排序方法中：每趟插入只排好一个数；$n$个数要进行$n-1$趟插入排序才能全部排好。
//对R[0..n-1]按递增有序进行直接插入排序
void insertSort(RecType R[], int n)
{
int i, j;
RecType tmp;
for (i = 1; i < n; i++)
{
tmp = R[i];
j = i - 1;
// 从右向左在有序区R[0..i-1]找R[i]的插入位置
while (j >= 0 && tmp.key < R[j].key)
{
R[j + 1] = R[j]; // 将关键字大于R[i].key的记录后移
j--;
}
R[j + 1] = tmp; // 在j+1处插入R[i]
}
}
交换排序
交换排序的基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。
两种交换排序方法:
- 冒泡排序
- 快速排序
冒泡排序
冒泡排序方法中：$n$个数要进行$n-1$趟冒泡排序才能全部排好；每趟冒泡要比较$n-j$次$(1<=j<=n-1)$，每趟只排好一个数。
// 冒泡排序
void bubbleSort(RecType R[], int n)
{
int i, j;
RecType temp;
for (i = 0; i < n - 1; i++)
{
// 比较找本趟最小关键字的记录
for (j = i; j < n - 1; j++)
{
// 递增排序(如果前者大于后者, 则交换)
if (R[j].key > R[j + 1].key)
{
temp = R[j]; //R[j]与R[j-1]进行交换
R[j] = R[j + 1];
R[j + 1] = temp;
}
}
}
}
选择排序
选择排序的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子表的最后，直到全部记录排序完毕。
两种选择排序方法：
- 简单选择排序（或称直接选择排序）
- 堆排序
简单选择排序
简单选择排序方法中：每趟选择只排好一个数；$n$个数要进行$n-1$趟选择排序才能全部排好。
// 简单选择排序
void selectSort(RecType R[], int n)
{
int i, j, k;
RecType temp;
for (i = 0; i < n - 1; i++) // 做第i趟排序
{
k = i;
// 在[i..n-1]中选key最小的R[k]
for (j = i + 1; j < n; j++)
{
// k记下的最小关键字所在的位置
if (R[j].key < R[k].key) k = j;
}
// 交换R[i]和R[k]
if (k != i)
{
temp = R[i];
R[i] = R[k];
R[k] = temp;
}
}
}
