排序的基本概念
排序的定义
- 排序：给定一组记录（数据元素、结点、顶点）的集合{r1, r2, …, rn}，其相应的关键码分别为{k1, k2, …, kn}，将这些记录排列为{rs1, rs2, …, rsn}的序列，使得相应的关键码满足ks1≤ks2≤…≤ksn（升序（非降序））（或ks1≥ks2≥…≥ksn）（降序（非升序））。
- 排序码：排序的依据，简单起见，也称关键码。
- 排序的数据模型是什么？
排序是对线性结构的一种操作
- 不失一般性，做如下约定：
(1)进行升序排序
(2)记录只有排序码一个数据项
(3)采用顺序存储，且下标从1开始 -
正序：待排序序列中的记录已按关键码排好序。
逆序（反序）：待排序序列中记录的顺序与排好序的顺序相反。
趟：在排序过程中，将待排序的记录序列扫描一遍称为一趟。
深刻理解趟的含义能够更好地掌握排序方法的思想和过程 - 基本操作
比较、交换
算法的稳定性
排序算法的稳定性：假定在待排序的记录序列中存在多个具有相同关键码的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法稳定，否则称为不稳定。
排序算法的稳定性只是算法的一种属性，且由具体算法决定
排序的分类
-
根据排序过程中所有记录是否全部放在内存中，排序方法分为：
（1）内排序：在排序的整个过程中，待排序的所有记录全部放在内存中
（2）外排序：待排序的记录个数较多，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果 -
根据排序方法是否建立在关键码比较的基础上，排序方法分为：
（1）基于比较：主要通过关键码之间的比较和记录的移动实现- ① 插入排序；
直接插入排序
希尔排序 - ② 交换排序；
起泡排序
快速排序 - ③ 选择排序；
简单选择排序
堆排序 - ④ 归并排序
二路归并递归算法
二路归并非递归算法 - ⑤分配排序
（2）不基于比较：根据待排序数据的特点所采取的其他方法
稳定排序、不稳定排序 - ① 插入排序；
排序算法的性能
如何衡量排序算法的性能呢？
- （1）时间性能：排序算法在**各种情况（最好、最坏、平均）**下的时间复杂度。
例如，基于比较的内排序在排序过程中的基本操作：
① 比较：关键码之间的比较；
② 移动：记录从一个位置移动到另一个位置。 - （2）空间性能：排序过程中占用的辅助存储空间。
辅助存储空间是除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。
class Sort
{
public:
Sort(int r[ ], int n);
~Sort( );
void InsertSort( );
void ShellSort( );
void BubbleSort( );
void QuickSort(int first, int last);
void SelectSort( );
void HeapSort( );
void MergeSort1(int first, int last);
void MergeSort2( );
void Print( );
private:
int Partition(int first, int last);
void Sift(int k, int last);
void Merge(int first1, int last1, int last2);
void MergePass(int h);
int *data;
int length;
Sort :: Sort(int r[ ], int n)
{
data = new int[n];
for (int i = 0; i < n; i++)
data[i] = r[i];
length = n;
}
Sort :: ~Sort( )
{
delete[ ] data;
}
void Sort :: Print( )
{
for (int i = 0; i < length; i++)
{
cout << data[i] << "\t";
}
cout << endl;
}
插入排序
直接插入排序
基本思想
直接插入排序的基本思想：依次将待排序序列中的每一个记录插入到已排好序的序列中，直到全部记录都排好序。
在插入第 i（i＞1）个记录时，前面的 i-1个记录已经排好序
基本步骤
1找到插入位置
2将插入位置及其后的元素后移一位
3插入
算法描述
- 如何构造初始的有序序列？
将第 1 个记录看成是初始有序序列，
然后从第 2 个记录起依次插入到有序序列中，直至将第 n 个记录插入。 - 算法描述：
for (i = 1; i < length; i++)
{
插入第 i 个记录，即第 i 趟直接插入排序；
}
- 如何将第 i 个记录插入到有序序列中的合适位置？
在有序序列中进行顺序查找，查找下标初始化为多少？j = i - 1;
在有序序列中进行顺序查找，循环条件是什么？
退出循环，记录r[i]的最终位置是哪里？
void Sort :: InsertSort( )
{
int i, j, temp;
for (i = 1; i < length; i++)
{
temp = data[i];
data[0] = temp
j = i - 1;
while (j >= 0 && temp < data[j])/或(因为有哨兵)/(temp < data[j])
{
data[j + 1] = data[j];
j--;
}
data[j + 1] = temp;
}
}
时间性能
- 最好情况：正序O(n)
比较次数：n-1次
移动次数：2(n-1)次 - 最坏情况：逆序((n2)
- 平均情况：随机排列，O(n2)
空间性能
- r[0]作用是什么？
暂存单元、监视哨 - 空间性能：O(1)〉
- 稳定性：稳定
希尔排序
改进的着眼点
- 在待排序序列正序时，直接插入排序的时间性能是O(n)。
- 当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。
- 改进的着眼点：
（1）若待排序记录按关键码基本有序，直接插入排序的效率较高；
（2）若待排序记录数量 n 较小，直接插入排序的效率也很高。 - 待排序记录数量 n 较大、并不是按关键码基本有序，怎么办？
基本思想
-
希尔排序的基本思想：将待排序序列分割成若干个子序列，在子序列内分别进行直接插入排序，待序列基本有序时，对全体记录进行直接插入排序。
-
基本有序：接近正序，例如{1, 2, 8, 4, 5, 6, 7, 3, 9}。
-
{5, 6, 7, 8, 9, 1, 2, 3, 4}是基本有序吗？
**局部有序（部分有序）**不能提高直接插入排序算法的时间性能。 -
如何分割待排序序列，才能使整个序列逐步向基本有序发展？
不能是逐段分割，而是将相距某个增量的记录组成一个子序列 -
如何分割待排序序列，才能使整个序列逐步向基本有序发展？
（1）希尔排序的时间性能取决于增量序列，复杂的数学问题。
（2）希尔排序是平均时间性能好于O(n2)的第一批算法之一（1959年）
（3）希尔最早提出的方法是
，且增量序列互质。
显然最后一个增量必须等于 1——缩小增量排序
一般会给定增量序列，主要是学习改进算法的思想
算法描述：
void Sort :: ShellSort( )
{
int d, i, j, temp;
for (d = length/2; d >= 1; d = d/2) //增量为d进行直接插入排序
{
for (i = d; i < length; i++) //进行一趟希尔排序
{
temp = data[i]; //暂存待插入记录
for (j = i - d; j >= 0 && temp < data[j]; j = j - d)//从后往前，如果大于后一个，就往后移d位。
data[j + d] = data[j]; //记录后移d个位置
data[j + d] = temp;
}
}
}
时间性能
-
时间性能：O(n2) ~ O(nlog2n)
（1）希尔排序算法的时间性能是所取增量的函数；
（2）研究表明，希尔排序的时间性能在O(n2)和O(nlog2n)之间；
（3）如果选定合适的增量序列，希尔排序的时间性能可以达到O(n1.3) 。- 增量每次除以2递减的方法：0(n2)
- Hibbard提出的增量序列：[2k-1,2k-1-1,…,7,3,1]:0(n1.5)
- 增量每次除以3的递减的方法：0(n1.5)
-
空间性能：O(1)——暂存单元
稳定性：不稳定
交换排序
起泡排序
基本思想
- 起泡排序的基本思想：两两比较相邻记录，如果反序则交换，直到没有反序的记录为止。
一趟起泡排序没有记录交换，则结束排序过程
一趟起泡排序可以确定多个记录的最终位置 - 如果有多个记录位于最终位置，如何不参加下一趟排序？
设置变量exchange记载交换的位置，一趟排序后exchange记载的就是最后交换的位置，从exchange之后的记录不参加下一趟排序。 - 下一趟排序的范围是多少？
设置变量bound表示一趟起泡排序的范围[1, bound]，并且bound与上一趟起泡排序的最后交换的位置exchange之间的关系是bound = exchange。
bound = exchange; exchange = 0;
for (j = 0; j < bound; j++)
if (data[j] > data[j+1]){
temp = r[j]; r[j] = r[j+1]; r[j+1] = temp;
exchange = j;
}
- 一趟排序没有交换，则表明整个序列已经有序。
while (exchange != 0)
{
执行一趟起泡排序；
}
void Sort :: BubbleSort( )
{
int j, exchange, bound, temp;
exchange = length - 1; //第一趟起泡排序的区间是[0~length-1]
while (exchange != 0)
{
bound = exchange; exchange = 0；
for (j = 0; j < bound; j++) //一趟起泡排序的区间是[0~bound]
if (data[j] > data[j+1]) { #比较语句？执行次数？
temp = data[j]; data[j] = data[j+1]; data[j+1] = temp; #移动语句？执行次数？
exchange = j； //记载每一趟的最后一次交换的位置
}
}
}
时间性能
- 最好情况：正序O(n)
比较次数：n-1次
移动次数：0次 - 最坏情况：逆序O(n2)
- 平均情况：随机排列，O(n2)
稳定性：稳定
快速排序（划分交换排序）
改进的着眼点
改进冒泡排序中一次交换只能消除一个逆序的缺点，即实现一次交换消除多个逆序。
问题：记录的比较在相邻单元中进行、每次交换只能右移一个单元、总的比较次数和移动次数较多
改进：较大记录从前面直接移到后面，较小记录从后面直接移到前面？
基本思想
快速排序的基本思想：
选一个轴值，将待排序记录划分成两部分，
左侧记录均小于或等于轴值，
右侧记录均大于或等于轴值，
即一次划分：以轴值为基准将无序序列划分为两部分，
之后分别对分割所得两个子序列“递归”进行快速排序，直到整个序列有序。
显然，快速排序是一个递归的过程
关键问题
- 如何选择轴值——比较的基准？
（1）第一个记录；
（2）随机选取；
（3）比较三个记录取值居中者；
简单起见，取第一个记录作为轴值 - 选取不同轴值有什么后果?
决定两个子序列的长度
决定排序的时间性能 - 如何实现一次划分——较大的记录移到后面，较小记录移到前面？
记录的比较和移动从两端向中间进行
较小的记录一次就能从后面移到前面（较大的记录？）
从而减少了总的比较次数和移动次数 - 如何处理一次划分得到的两个待排序子序列？
递归执行快速排序
void Sort :: QuickSort (int first, int last )
{
int pivot = Partition (first, last);
QuickSort (first, pivot-1);
QuickSort (pivot+1, last );
}
- 递归执行快速排序递归何时结束？
若待排序序列只有一个记录，即待划分区间长度为 1if (first == last) return;
运行过程
示例一
将第一个记录元素放在r[0]上；
low、high指向第一个和最后一个元素
先比较high->98和枢轴值48，大于则跳过，小于则赋值给low
再比较low和枢轴值48,小于则跳过，大于则赋值给high
示例二
算法描述
示例一
int QKpass (RecordType r[]int low,int high)
{
r[0] = r[low];
while (low<high)
{
while(low<high&&r[high].key>=r[0].key)
--high;
r[low] = r[high];
while (low<high &r[low].key<=r[0].key)
++low;
r[high] = r[low];
}
r[low] = r[0]; return low;
}
void QKSort(RecordType r[],int low,int high)
{
r[0]=r[low];
if(low<high)
{
pos=QKpass(r,low,high);
QKSort(r,low,pos-1);
QkSort(r,pos+1,high);
}
}
示例二
int Sort :: Partition(int first, int last)
{
int i = first, j = last, temp;
while (i < j)
{
while (i < j && data[i] <= data[j]) j--； /*右侧扫描*/
if (i < j) {
temp = data[i]; data[i] = data[j]; data[j] = temp; i++;
}
while (i < j && data[i] <= data[j]) i++； /*左侧扫描*/
if (i < j) {
temp = data[i]; data[i] = data[j]; data[j] = temp; j--;
}
}
retutn i; /*i为轴值记录的最终位置*/
}
void Sort :: QuickSort(int first, int last)
{
if (first == last) return; /*区间长度为1，递归结束*/
else {
int pivot = Partition(first, last);
QuickSort(first, pivot-1);
QuickSort(pivot+1, last);
}
}
时间性能
- 最好情况：每次划分的轴值均是中值O(nlog2n)
排序趟数：log2n
一趟排序：O(n) - 最坏情况：正序、逆序O(n2)
排序趟数：n-1
一趟排序：O(n) - 平均情况：O(nlog2n)
空间性能
- 空间性能：O(log2n)~O(n)
一次划分：O(1)
递归深度：O(log2n)~O(n) - 稳定性：不稳定
选择排序
选择类排序算法的基本思想
选择类排序算法的基本思想是从个元素中选出一个最大（小）元素，把它调到序列末（前）端，
简单选择排序
基本思想
简单选择排序的基本思想：第 i 趟（1≤i≤n-1）排序在待排序序列r[i]～r[n] 中选取最小记录，并和第 i 个记录交换。
关键问题
- 简单选择排序进行多少趟？n-1趟
for (i = 0; i < length-1; i++)
{
第 i 趟简单选择排序；
}
- 第 i 趟简单选择排序完成什么工作？
（1）在r[i]~r[n]中找最小值
（2）将最小记录与r[i]交换
index = i;
for (j = i + 1; j < length; j++)
if (data[j] < data[index]) index = j;
if (index != i) {
交换data[i]和data[index];
}
算法描述
void Sort :: SelectSort( )
{
int i, j, index, temp;
for (i = 0; i < length; i++)
{
index = i;
for (j = i + 1; j < length-1; j++)
if (data[j] < data[index]) index = j;
if (index != i) {
temp = data[i]; data[i] = data[index]; data[index] = temp;
}
}
}
时间性能
简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排序情况无关。
- 比较次数：O(n2)
- 移动次数：
最好情况是记录正序，无需交换，0次
最坏情况是记录逆序，需要n-1次交换。 - 最好、最坏、平均情况：O(n2)
简单选择排序和冒泡排序一样，时间复杂度都是0(n2)
空间性能
空间性能：
-
需要2个辅助存储空间
记录最小位置
数据交换缓存O(1) -
稳定性：记录交换是跳跃式进行的，因此简单选择排序是不稳定
树型选择排序（竞标赛排序）
基本思想
-
是一种按锦标赛的思想进行排序的方法。基本思想与体育比赛时的淘汰赛类似：
首先将n个对象的排序码进行两两比较，得到ceil(n/2)个比较的优胜者(较小)，作为第一步比较的结果保留下来；
然后对这ceil(n/2)个对象再进行排序码的两两比较，…，如此重复，直到选出一个排序码最小的对象为止。 -
一颗包含n个结点的完全二叉树，当二叉树不满时，用关键字为∞的结点填满，选出的最小关键字就是这颗树的根结点。在输出了最小关键字之后，为了选择次小关键字，将最小关键字记录所对应的叶子结点的关键字置为∞。
叶子结点和其兄弟结点的关键字比较，修改从该叶子结点到根结点上各结点的止，则根结点的值被修改为次小的关键字。直到左右的结点输出为止。
运行过程
二叉树的深度是1og2n +1
叶子结点数目为n
第一轮比较次数为n-1
将最小的数对应的叶子结点改为∞，其路径的结点再进行比较
性能分析
树形选择排序构成是一颗完全二叉树。
其深度为log2n + 1,其中n为待排序元素个数。
- 比较分析
第一轮n-1次
其他轮次log2n次 - 时间复杂度为：O(nlog2n)。
- 空间复杂度：增加了n-1结点存放中间比较结果。
堆排序
堆的定义
- 堆是每个非叶子结点值都大于或等于其儿子值的完全二叉树。
- 堆是借助于完全二叉树提出的一种新的数据结构，堆是满足下列特性的完全二叉树，当一个数列满足下列性质时，我们称它为小顶堆或者大顶堆。
小根堆：每个结点的值都小于等于其左右孩子结点的完全二叉树。
大根堆：每个结点的值都大于等于其左右孩子结点的完全二叉树。
小根堆和大根堆统称为堆。
堆的特点
- 大根堆有什么特点呢？
（1）根结点（称为堆顶）的值是所有结点的最大值；
（2）较大值的结点靠近根结点，但不绝对。 - 将堆按层序编号，有什么特点？
ki大(小)于两个孩子结点k2ik2i+1
堆与序列的关系
- 堆采用顺序存储，则对应一个（无序）序列
顺序存储，以编号作为下标
堆调整
-
堆调整：在一棵完全二叉树中，根结点的左右子树均是堆，调整根结点使整个完全二叉树成为一个堆的过程。
-
如何设计函数接口？
由于初始建堆和重建堆均调用此函数，因此，设置形参 k 和 last
void Sort :: Sift(int k, int last)
{
int i, j, temp;
i = k; j =2 * i + 1; // i是被调整结点，j是i的左孩子
while (j <= last) //还没有进行到叶子
{
if (j < last && data[j] < data[j+1]) j++; // j指向左右孩子的较大者
if (data[i] > data[j]) break; //已经是堆
else {
temp = data[i]; data[i] = data[j]; data[j] = temp;
i = j; j = 2 * i + 1; //被调整结点位于结点j的位置
}
}
}
堆排序
改进的着眼点
-
缺点：简单选择排序的时间主要耗费在哪了呢？
对无序序列扫描一趟（n-1 次比较）只做了一件事——找最小值
优点：移动次数较少，最坏情况O(n) - 改进的着眼点：利用简单选择排序的思想，同时减少比较次数
利用每趟比较后的结果，查找最小值的同时找出并保存较小值，减少后面选择所用的比较次数，提高整个排序的效率
基本思想
堆排序的基本思想：首先将待排序序列构造成一个大根堆，即选出了堆中所有记录的最大者，将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小的记录，以此类推，直到堆中只有一个记录。
第 i 趟堆排序将 r1 ~ ri 调整成大根堆，再将堆顶与 ri 交换
初始建堆
- 堆调整
- 如何将一个无序序列建成一个大根堆——初始建堆？
从编号最大的分支结点到根结点进行调整
从底向上，从右向左进行调整
关键问题
- 如何处理堆顶——无序区中的最大值？
交换data[0]与 data[length-i]; - 如何将无序区重新调整成为大根堆？无序区最后一个结点的编号？
根结点的编号为 k，最后一个结点的编号为 last - 算法描述：
for (i = ceil(length/2) - 1; i >= 0; i--)
Sift(i, length-1); //调整结点 i
void Sort :: Sift (int k, int last) //根结点的编号为 k，最后一个结点的编号为 last
- 堆排序要进行多少趟？
n-1趟
进行排序
=》
=》
void Sort :: HeapSort( )
{
int i, temp;
for (i = ceil(length/2) - 1; i >= 0; i--) //从最后一个分支结点至根结点
Sift(i, length-1) ;
for (i = 1; i < length; i++)
{
temp = data[0]; data[0] = data[length-i]; data[length-i] = temp;
Sift(0, length-i-1); //重建堆
}
}
时间性能
初始建堆：O(nlog2n)
重建堆次数：n-1
重建堆：O（log2i）
最好、最坏、平均情况：O(nlog2n)
空间性能
空间性能：O(1)
稳定性：不稳定
归并排序
二路归并排序的递归实现
基本思想
二路归并排序的基本思想：将待排序序列划分为两个长度相等的子序列，分别对这两个子序列进行排序，得到两个有序子序列，再将这两个有序子序列合并成一个有序序列。
关键问题
- 某个子序列比较完毕，做什么？
一次合并：合并两个相邻的有序子序列的过程。
void Sort :: Merge(int first1, int last1, int last2)
{
int *temp = new int[length];
int i = first1, j = last1 + 1, k = first1;
while (i <= last1 && j <= last2)
{
if (data[i] <= data[j]) temp[k++] = data[i++];
else temp[k++] = data[j++];
}
while (i <= last1)
temp[k++] = data[i++];
while (j <= last2)
temp[k++] = data[j++];
for (i = first1; i <= last2; i++)
data[i] = temp[i];
delete[ ] temp;
}
void Sort :: MergeSort1(int first, int last)
{
if (first == last) return;
else {
int mid = (first + last)/2;
MergeSort1(first, mid);
MergeSort1(mid+1, last);
Merge(first, mid, last);
}
}
二路归并排序的非递归实现
- 子序列长度有什么规律？在一趟归并中有几种情况？
设 i 指向待归并序列的第一个记录，归并的步长是2h
情况 1：i+2h ≤ n，则相邻两个有序子序列的长度均为 h
while (i + 2 * h <= length)
{
Merge(i, i+h-1, i+2*h-1);
i = i + 2 * h;
}
情况 2：i+h＜n，则相邻有序子序列一个长度为 h，另一个长度小于 h
if (i + h < length)
Merge(i, i+h-1, length-1);
情况 3：i +h ≥ n，则表明只剩下一个有序子序列
void Sort :: MergePass(int h)
{
int i = 0;
while (i + 2 * h <= length) //有两个长度为h的子序列
{
Merge(i, i+h-1, i+2*h-1);
i = i + 2 * h;
}
if (i + h < length) //两个子序列一个长度小于h
Merge(i, i+h-1, length-1);
}
- 如何控制二路归并的结束？子序列长度有什么规律？
void Sort :: MergeSort2( )
{
int h = 1; //初始时子序列长度为1
while (h < length)
{
MergePass(h); //一趟归并排序
h = 2 * h;
}
}
- 二路归并执行多少趟？每一趟的时间性能是多少？
各种排序方法的比较
时间性能
- 从平均情况看
（1）直接插入排序、简单选择排序和起泡排序属于一类，时间复杂度为O(n2)；
（2）堆排序、快速排序和归并排序属于一类，时间复杂度为O(nlog2n)；
（3）希尔排序的时间性能取决于增量序列，介于O(n2)和O(nlog2n)之间 。
快速排序是目前最快的一种排序方法
在待排序记录个数较多的情况下，归并排序比堆排序更快 - 从最好情况看
（1）直接插入排序和起泡排序最好，O(n)；
（2）其他排序算法的最好情况与平均情况相同。
如果待排序序列接近正序，首选起泡排序和直接插入排序 - 从最坏情况看
（1）快速排序的时间复杂度为O(n2)；
（2）直接插入排序和起泡排序虽然与平均情况相同，但系数大约增加一倍，所以运行速度将降低一半；
（3）最坏情况对简单选择排序、堆排序和归并排序影响不大。
如果待排序序列接近正序或逆序，不使用快速排序
空间性能
从空间性能看
（1）归并排序的空间复杂度为O(n)；
（2）快速排序的空间复杂度为O(log2n)~O(n)；
（3）其它排序方法的空间复杂度为O(1)。文章来源：https://www.toymoban.com/news/detail-786204.html
稳定性及简单性
- 从稳定性看
（1）稳定：包括直接插入排序、起泡排序和归并排序；
（2）不稳定：包括希尔排序、简单选择排序、快速排序和堆排序。 - 从算法简单性看
（1）简单算法：包括直接插入排序、简单选择排序和起泡排序，
（2）改进算法，较复杂：包括希尔排序、堆排序、快速排序和归并排序。
记录本身的信息量
从记录本身信息量的大小看
记录本身信息量越大，占用的存储空间就越多，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。
记录本身信息量的大小对改进算法的影响不大。
记录个数不多且记录本身的信息量较大时，首选简单选择排序算法文章来源地址https://www.toymoban.com/news/detail-786204.html
关键码的分布情况
- 从关键码的分布看
（1）当待排序记录按关键码有序时，插入排序和起泡排序能达到O(n)的时间复杂度；对于快速排序而言，这是最坏情况，时间性能蜕化为O(n2)；
（2）简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键码的分布而改变。
各种排序算法各有优缺点，
应该根据实际情况选择合适的排序算法
到了这里，关于数据结构与算法-第八章 排序技术的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
