第八章 排序
一、内容小结
1.排序：按关键字的非递减或非递增顺序对一组记录重新进行排列的操作。
2.内部排序和外部排序：
前者指的是待排序记录全部存放在计算机内存中进行排序的过程；
后者指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
3.内存排序方法中序列中分为两个区域：有序序列区和无序序列区
4.待排序记录的存储方式可分为三种：①顺序表；②链表；③本身存在的连续存储单元。
1 #define MAXSIZE 20//顺序表的最大长度 2 typedef int KeyType; 3 typedef struct{ 4 KeyType key;//关键字 5 InfoType otherinfo;//其他数据项 6 }RedType; 7 typedef struct{ 8 RedType r[MAXSIZE + 1];//r[0]闲置或用作哨兵单元 int length; }SqList; //顺序表类型
5.排序算法效率的评价指标为：①执行时间:关键在于比较次数和移动次数；②辅助空间：理想的空间复杂度是O(1)；
二、排序方法合集及其实践代码
1.直接插入排序：将一条记录插入到已排好序的有序表中。
2.折半插入排序：其实这个算法跟二分查找有一些相似:
1 void BInsertSort(SqList &L) 2 {//折半查找排序 3 for(i = 2; i < L.length; i++) 4 { 5 L.r[0] = L.r[i];//监视哨兵 6 low = 1; high = i-1; 7 while(low <= high) 8 { 9 m = (low + high)/2;//折半查找 10 if(L.r[0].key<L.r[m].key) high = m-1; 11 else low = m+1; 12 } 13 for(j=i-1;j>=high+1;--j) L.r[j+1] = L.r[j];//记录后移 14 L.r[high+1] = L.r[0]; 15 16 } 17 }
3.希尔排序：分组分别进行直接插入排序，是一种不稳定的排序算法。
4.冒泡排序：是稍微熟悉一点的排序方法，而且对过程的分析比较清晰具体一些。一趟下来一边比较大小一边交换。
最好情况只需一趟，最坏情况时间平均度O(n²);
算法特点为：①稳定性好；②适用于链式存储结构；③移动记录次数较多，算法平均时间性能比直接插入排序差。
（p.s 初始无序，或n较大时，不适用冒泡排序）
5.快速排序：一次交换可能消除多个逆序。（p.s.递归进行）
6.选择排序（稳定的）：每一趟选择将待排序的序列中最小的关键字，时间复杂度O(n²)。
7.堆排序（树形选择排序）：在当前无序序列中选择最大（小）的记录。将较小（大）的关键字逐层筛选下去。（筛选法）
(a)为大根堆 （b）为小根堆
8.归并排序：将两个或两个以上有序表合并成一个有序表的过程。
三、上周实现情况及最后一周目标
上周说的好好听课做课堂笔记有在实现中，虽然一堂课满满当当地认真听完有一些困难，但是课后也会找时间将不懂的点复看一遍，所以对概念的选择题和判断题上比较有感觉，就是这周因为各门考试和ddl没有抽太多时间敲代码，所以下周的复习周会开始发愤图强，努力将本学期的知识点过一遍脑子~~加油吧！