一.排序算法
1.排序
从今天开始我们就要开始学习排序算法啦！
排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。为了查找方便,通常希望计算机中的表是按关键字有序的。
2.稳定性
除了我们之前了解的时间复杂度和空间复杂度来判断一个算法的好坏之外，在排序算法这里我们引入一个新的判断标准——稳定性。
算法的稳定性。若待排序表中有两个元素R;和R，其对应的关键字相同即key~i~= key~j~,且在排序前R~i~在R~j~的前面， 若使用某一排序算法排序后，R~i~仍然在R~j~的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。需要注意的是，算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要。
3.算法分类
这里需要注意的是我们上一篇博客在图的应用中的拓扑排序他并不是我们这里严格意义上的排序算法。
二.直接插入排序
1.操作步骤
要将元素L(i)插入已有序的子序列[1……i-1]，需要执行以下操作(为避免混淆，下面用L[ ]表示一个表，而用L()表示一个元素):
- 1)查找出L(i)在L[...i-1]中的插入位置k。
- 2)将L[.1i-1]中的所有元素依次后移-一个位置。
- 3)将L(i)复制到L(k)。
为了实现对L1..n]的排序,可以将L(2) ~L (n)依次插入前面已排好序的子序列，初始L[1]可以视为是一个已排好序的子序列。上述操作执行n- 1次就能得到一个有序的表。插入排序在实现上通常采用就地排序(空间复杂度为0(1))，因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。
2.举例演示
假定初始序列为49, 38, 65, 97 ,76, 13, 27,49，初始时49可以视为一个已排好序的子序列，按照上述算法进行直接插入排序的过程如图所示，括号内是已排好序的子序列。
3.性能分析
空间效率:仅使用了常数个辅助单元，因而空间复杂度为0(1)。
时间效率:在排序过程中，向有序子表中逐个地插入元素的操作进行了n-1趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。在最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一一次而不用移动元素，因而时间复杂度为0(n)。在最坏情况下，表中元素顺序刚好与排序结果中的元素顺序相反(逆序)， 总的比较次数达到最大，总的移动次数也达到最大，总的时间复杂度为0(2)。平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为n^2^ /4。
4.代码实现
//直接插入排序
void InsertSort1(SqList &L){
Elemtype temp;
int i,j;
for(i=1;i<L.length;i++){
if(L.data[i].grade<L.data[i-1].grade){
temp=L.data[i];
for(j=i-1;j>=0 && temp.grade<L.data[j].grade;--j) //从后往前查找待插入的位置
L.data[j+1]=L.data[j]; //向后挪位
L.data[j+1]=temp;
}
}
}
三.折半插入排序
1.操作步骤
这里简要描述，详细请查看折半查找的博客线性表查找算法
从直接插入排序算法中，不难看出每趟插入的过程中都进行了两项工作:①从前面的有序子表中查找出待插入元素应该被插入的位置;②给插入位置腾出空间，将待插入元素复制到表中的插入位置。注意到在该算法中，总是边比较边移动元素。下面将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。当排序表为顺序表时,可以对直接插入排序算法做如下改进:由于是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可统一-地向后移动元素。
2.性能分析
从上述算法中，不难看出折半插入排序仅减少了比较元素的次数，约为O(nlog2n)，该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数n;而元素的移动次数并未改变，它依赖于待排序表的初始状态。因此，折半插入排序的时间复杂度仍为O(n2)， 但对于数据量不很大的排序表，折半插入排序往往能表现出很好的性能。折半插入排序是一种稳定的排序方法。
3.代码实现
//折半插入排序
void InsertSort2(SqList &L){
Elemtype temp;
int i, j, low, high, mid;
for(i=1; i<L.length; i++){
temp = L.data[i];
low = 0; high = i-1;
while(low <= high){
//折半查找
mid = (low + high) / 2; //取中间点
if(L.data[mid].grade > temp.grade)
high = mid - 1;
else
low = mid + 1;
}
for(j=i-1; j>=high+1; --j){
L.data[j+1] = L.data[j];
}
L.data[high+1] = temp;
}
}
四.希尔排序
1.排序过程
希尔排序的过程如下:先取一个小于n的步长d,把表中的全部记录分成d组，所有距离为d1的倍数的记录放在同一组，在各组内进行直接插入排序;然后取第二个步长d2<d，重复上述过程，直到所取到的d~t~ = 1,即所有记录已放在同一-组中， 再进行直接插入排序，由于此时已经具有较好的局部有序性，故可以很快得到最终结果。到目前为止，尚未求得一个最好的增量序列。
提出这个算法的本人提倡使用d=n/2
2.举例演示
3.性能分析
空间效率:仅使用了常数个辅助单元，因而空间复杂度为0(1)。
时间效率:由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当n在某个特定范围时，希尔排序的时间复杂度约为0(n^l.3^ )。在最坏情况下希尔排序的时间复杂度为0(n^2^ )。
稳定性:当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
4.代码实现
//希尔排序
void ShellSort(SqList &L){
int dk,i,j;
Elemtype temp;
for(dk=L.length/2;dk>=1;dk=dk/2){
for(i=dk;i<L.length;++i){
if(L.data[i].grade<L.data[i-dk].grade){
temp=L.data[i];
for(j=i-dk;j>=0 && temp.grade<L.data[j].grade;j-=dk)
L.data[j+dk]=L.data[j];
L.data[j+dk];
}
}
}
}
五.C语言演示代码
/*我们今天的主角插入排序是基于查找算法来的，所以我们还是利用线性表来进行模拟*/
/*为了便于我们后面演示希尔排序，所以我们采用顺序存储结构*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MaxSize 50 //这里只是演示，我们假设这里最多存五十个学生信息
//定义学生结构
typedef struct {
char name[200]; //姓名
int grade; //分数，这个是排序关键字
} Elemtype;
//声明使用顺序表
typedef struct {
/*这里给数据分配内存，可以有静态和动态两种方式，这里采用动态分配*/
Elemtype *data; //存放线性表中的元素是Elemtype所指代的学生结构体
int length; //存放线性表的长度
} SqList; //给这个顺序表起个名字，接下来给这个结构体定义方法
//初始化线性表
void InitList(SqList &L){
/*动态分配内存的初始化*/
L.data = (Elemtype*)malloc(MaxSize * sizeof(Elemtype)); //为顺序表分配空间
L.length = 0; //初始化长度为0
}
//求表长函数
int Length(SqList &L){
return L.length;
}
//求某个数据元素值
bool GetElem(SqList &L, int i, Elemtype &e) {
if (i < 1 || i > L.length)
return false; //参数i错误时，返回false
e = L.data[i - 1]; //取元素值
return true;
}
//输出线性表
void DispList(SqList &L) {
if (L.length == 0)
printf("线性表为空");
//扫描顺序表，输出各元素
for (int i = 0; i < L.length; i++) {
printf("%s %d", L.data[i].name, L.data[i].grade);
printf("\n");
}
printf("\n");
}
//插入数据元素
bool ListInsert(SqList &L, int i, Elemtype e) {
/*在顺序表L的第i个位置上插入新元素e*/
int j;
//参数i不正确时，返回false
if (i < 1 || i > L.length + 1 || L.length == MaxSize)
return false;
i--; //将顺序表逻辑序号转化为物理序号
//参数i正确时，将data[i]及后面的元素后移一个位置
for (j = L.length; j > i; j--) {
L.data[j] = L.data[j - 1];
}
L.data[i] = e; //插入元素e
L.length++; //顺序表长度加1
return true;
/*平均时间复杂度为O(n)*/
}
//直接插入排序
void InsertSort1(SqList &L){
Elemtype temp;
int i,j;
for(i=1;i<L.length;i++){
if(L.data[i].grade<L.data[i-1].grade){
temp=L.data[i];
for(j=i-1;j>=0 && temp.grade<L.data[j].grade;--j) //从后往前查找待插入的位置
L.data[j+1]=L.data[j]; //向后挪位
L.data[j+1]=temp;
}
}
}
/*还记得我们之前学的查找算法吗，其实就是线性查找和折半查找到需要插入元素的位置*/
//折半插入排序
void InsertSort2(SqList &L){
Elemtype temp;
int i, j, low, high, mid;
for(i=1; i<L.length; i++){
temp = L.data[i];
low = 0; high = i-1;
while(low <= high){
//折半查找
mid = (low + high) / 2; //取中间点
if(L.data[mid].grade > temp.grade)
high = mid - 1;
else
low = mid + 1;
}
for(j=i-1; j>=high+1; --j){
L.data[j+1] = L.data[j];
}
L.data[high+1] = temp;
}
}
//希尔排序
void ShellSort(SqList &L){
int dk,i,j;
Elemtype temp;
for(dk=L.length/2;dk>=1;dk=dk/2){
for(i=dk;i<L.length;++i){
if(L.data[i].grade<L.data[i-dk].grade){
temp=L.data[i];
for(j=i-dk;j>=0 && temp.grade<L.data[j].grade;j-=dk)
L.data[j+dk]=L.data[j];
L.data[j+dk]=temp;
}
}
}
}
int main(){
SqList L;
Elemtype stuents[10]={
{
"张三",649},{
"李四",638},{
"王五",665},{
"赵六",697},{
"冯七",676},
{
"读者",713},{
"阿强",627},{
"杨曦",649},{
"老六",655},{
"阿黄",604}};
//这一部分忘了的请回顾我的相关博客
printf("初始化顺序表并插入开始元素：\n");
InitList(L); //这时是一个空表，接下来通过插入元素函数完成初始化
for (int i = 0; i < 10; i++)
ListInsert(L, i + 1, stuents[i]);
DispList(L);
printf("根据分数进行直接插入排序后：\n");
InsertSort1(L);
DispList(L);
/*
printf("根据分数进行折半插入排序后：\n");
InsertSort2(L);
DispList(L);
printf("根据分数进行希尔排序后：\n");
ShellSort(L);
DispList(L);
*/
//请确保这里在进行一次排序后，不要在用其他方法排序，没有意义，可以重新初始化线性表，再换一种方法排序
}
这里请注意，设计线性表的相关问题，请看顺序表算法练习
六.运行结果
1.直接插入排序
2.折半插入排序
3.希尔排序
