王道408考研数据结构-排序-第八章
8.1 排序的基本概念
8.1.1 排序的定义
排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。
算法的稳定性。若待排序表中有两个元素R1和R2其对应的关键字相同，即 key,= key,且在排序前 R1在 R2的前面，若使用某一排序算法排序后，R1仍然在 R2的前面，则称这个排序算法是稳定的，否则称这个排序算法是不稳定的。
在排序过程中，根据数据元素是否完全存放在内存中，可将排序算法分为两类：①内部排序，是指在排序期间元素全部存放在内存中的排序；②外部排序，是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序。
8.2 插入排序
插入排序是一种简单直观的排序算法，其基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法：直接插入排序、折半插入排序和希尔排序。
8.2.1 直接插入排序
插入排序在实现上通常采用原地排序(空间复杂度为 O(1)),因而在从后往前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。下面是直接插入排序的代码，其中再次用到了前面提到的“哨兵”(作用相同)。
void InsertSort(ElemType A[],int n){
int i,j;
for(i=2;i<=n;i++) //依次将A[2]～A[n]插入前面已排序序列
if(A[i]<A[i-1]){ //若A[i]关键码小于其前驱，将A[i]插入有序表
A[0]=A[i]; /复制为哨兵，A[0]不存放元素
for(j=i-1;A[0]<A[j];--j)//从后往前查找待插入位置
A[j+1]=A[j];//向后挪位
A[j+1]=A[0]; //复制到插入位置
}
}假定初始序列为49,38,65,97,76,13,27,49,初始时 49可以视为一个已排好序的子序列，按照上述算法进行直接插入排序的过程如图8.1所示，括号内是已排好序的子序列。
空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)。
时间效率：直接插入排序算法的时间复杂度为0(n^2)。
8.2.2 折半插入排序
从直接插入排序算法中，不难看出每趟插入的过程中都进行了两项工作：①从前面的有序子表中查找出待插入元素应该被插入的位置；②给插入位置腾出空间，将待插入元素复制到表中的插入位置。注意到在该算法中，总是边比较边移动元素。下面将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。当排序表为顺序表时，可以对直接插入排序算法做如下改进：因为是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可统一地向后移动元素。算法代码如下：
void InsertSort(ElemType A[],int n){
int i,j,low,high,mid;
for(i=2;i<=n;i++){ //依次将A[2]～A[n]插入前面的已排序序列
A[0]=A[1];//将A[i]暂存到A[0]
low=1;high=i-1;//设置折半查找的范围
while(low<=high){//折半查找(默认递增有序)
mid=(low+high)/2;//取中间点
if(A[mid]>A[0]) high=mid-1;//查找左半子表
else low=mid+1; //查找右半子表
}
for(j=i-1;j>=high+1;--j)
A[j+1]=A[j]; //统一后移元素，空出插入位置
A[high+1]=A[0]; //插入操作
}
}折半插入排序的时间复杂度仍为 0(n^2),但对于数据量不很大的排序表，折半插入排序往往能表现出很好的性能。折半插入排序是一种稳定的排序算法。
8.2.3 希尔排序
希尔排序的过程如下：先取一个小于n的增量d1,把表中的全部记录分成d1组，所有距离为d1的倍数的记录放在同一组，在各组内进行直接插入排序；然后取第二个增量d2<d1,重复上述过程，直到所取到的dt=1,即所有记录已放在同一组中，再进行直接插入排序，由于此时已经具有较好的局部有序性，因此可以很快得到最终结果。到目前为止，尚未求得一个最好的增量序列。仍以 8.2.1 节的关键字为例，假定第一趟取增量d1=5,将该序列分成5个子序列，即图中第2行至第6行，分 别对各子序列进行直接插入排序，结果如第7行所示；假定第二趟取增量d2=3,分别对三个子序列 进行直接插入排序，结果如第 11 行所示；最后对整个序列进行一趟直接插入排序，整个排序过 程如图 8.2 所示。
希尔排序算法的代码如下：
void ShellSort(ElemType A[],int n){
//A[0]只是暂存单元，不是哨兵，当 j<=0 时，插入位置已到
int dk,i,j;
for(dk=n/2;dk>=1;dk=dk/2){
for(i=dk+1;i<=n;++i)
if(A[i]<A[i-dk]){
A[0]=A[i];
for(j=i-dk;j>0ssA[0]<A[j];j-=dk){
A[j+dk]=A[j];
A[j+dk]=A[0];
}
)]}空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)。
时间效率：因为希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当n在某个特定范围时，希尔排序的时间复杂度约为O(n^1.3)。在最坏情况下希尔排序的时间复杂度为O(n^2)。
稳定性：当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因 此希尔排序是一种不稳定的排序算法
8.3 交换排序
所谓交换，是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。基于交换的排序算法很多，本书主要介绍冒泡排序和快速排序，其中冒泡排序算法比较简单，一般很少直接考查，通常会重点考查快速排序算法的相关内容。
8.3.1冒泡排序
冒泡排序的基本思想是：从后往前(或从前往后)两两比较相邻元素的值，若为逆序(即A[i-1]>A[i]),则交换它们，直到序列比较完。我们称它为第一趟冒泡，结果是将最小的元素交换到待排序列的第一个位置(或将最大的元素交换到待排序列的最后一个位置),关键字最小的元素如气泡一般逐渐往上“漂浮”至“水面”(或关键字最大的元素如石头一般下沉至水底)。下一趟冒泡时，前一趟确定的最小元素不再参与比较，每趟冒泡的结果是把序列中的最小元素(或最大元素)放到了序列的最终位置……这样最多做n-1趟冒泡就能把所有元素排好序。
冒泡排序算法的代码如下：
void BubbleSort(ElemType A[],int n)(
for(int i=0;i<n-1;i++)(
bool flag=false;//表示本趟冒泡是否发生交换的标志
for(int j=n-1;j>i;j--) //一趟冒泡过程
if(A[j-1]>A[j]){ //若为逆序
swap(A[j-1],A[j]);//使用封装的 swap函数交换
flag = true;
}
if(flag==false)
return; //本越遍历后没有发生交换，说明表已经有序
}
}空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1)。
时间效率：均时间复杂度为O(n^2)。
稳定性：由于i>j且A[i]=A[j]时，不会发生交换，因此冒泡排序是一种稳定的排序算法。
8.3.2 快速排序
快速排序(以下有时简称快排)的基本思想是基于分治法的：在待排序表L[1…n]中任取一个元素 pivot 作为枢轴(或称基准，通常取首元素),通过一趟排序将待排序表划分为独立的两部分L[1…k-1]和L[k+1…n],使得L[1…k-1]中的所有元素小于pivot,L[k+1…n]中的所有元素大于或等于pivot,则pivot放在了其最终位置L(k)上，这个过程称为一次划分。然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或为空为止，即所有元素放在了其最终位置上。
一趟快速排序的过程是一个交替搜索和交换的过程，下面通过实例来介绍，附设两个指针i和j,初值分别为low和high,取第一个元素49为枢轴赋值到变量pivot。
指针j从high往前搜索找到第一个小于枢轴的元素27,将27交换到i所指位置。
此时，指针i(==j)之前的元素均小于49,指针i之后的元素均大于或等于49,将49放在i所指位置即其最终位置，经过第一趟排序后，将原序列分割成了前后两个子序列。
假设划分算法已知，记为Partition(),返回的是上述的k,则L(k)已放在其最终位置。因此可以先对表进行划分，然后对两个子表递归地调用快速排序算法进行排序。代码如下：
void QuickSort(ElemType A[],int low,int high){
if(low<high){
int pivotpog=Partition(A,low,high);//划分
QuickSort(A,low,pivotpos-1);1/依次对两个子表进行递归排序
QuickSort(A,pivotpos+1,high);
}
}快速排序算法的性能主要取决于划分操作的好坏。考研所考查的快速排序的划分操作通常总以表中第一个元素作为枢轴来对表进行划分，则将表中比枢轴大的元素向右移动，将比枢轴小的元素向左移动，使得一趟Partition()操作后，表中的元素被枢轴一分为二。代码如下：
int Partition(ElemType A[],int low,int high){ //一趟划分
ElemType pivot=A[low];//将当前表中第一个元素设为枢轴，对表进行划分
while(low<high){ //循环跳出条件
while(low<high&&A[high]>=pivot)--high;
A[low]=A[high];//将比枢轴小的元素移动到左端
while(low<high&&A[low]<=pivot)++low;
A[high]=A[low];//将比枢轴大的元素移动到右端
}
A[low]=pivot; //枢轴元素存放到最终位置
return low; //返回存放枢轴的最终位置
)空间效率：由于快速排序是递归的，因此需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量与递归调用的最大层数一致。最好情况下为 O(logn)；最坏情况下，要进行 n-1次递归调用，因此栈的深度为O(n)；平均情况下，栈的深度为O(logn)。
时间效率：时间复杂度为O(nlogn)。快速排序是所有内部排序算法中平均性能最优的排序算法。
稳定性：在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序算法。
8.4 选择排序
选择排序的基本思想是：每一趟(如第i趟)在后面n-i+1(i=1,2,…,n-1)个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟做完，待排序元素只剩下1个，就不用再选。选择排序中的堆排序是历年统考考查的重点。
8.4.1简单选择排序
根据上面选择排序的思想，可以很直观地得出简单选择排序算法的思想：假设排序表为L[1.n],第i趟排序即从L[i…n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可使得整个排序表有序。
简单选择排序算法的代码如下：
void SelectSort(ElemType A[],int n){
for(int i=0;i<n-1;i++){ //一共进行n-1趟
int min=i;//记录最小元素位置
for(int j=i+1;j<n;j++)//在A[i…n-1]中选择最小的元素
if(A[j]<A[min]) min=j;//更新最小元素位置
if(min!=i) swap(A[i],A[min]);//封装的 swap()函数共移动元素3次
}
}空间效率：仅使用常数个辅助单元，所以空间效率为O(1)。
时间效率：时间复杂度始终是 O(n^2)。
稳定性：简单选择排序是一种不稳定的排序算法。
8.4.2 堆排序
可以将堆视为一棵完全二叉树，满足条件①的堆称为大根堆(大顶堆),大根堆的最大元素存放在根结点，且其任意一个非根结点的值小于或等于其双亲结点值。满足条件②的堆称为小根堆(小顶堆),小根堆的定义刚好相反，根结点是最小元素。图8.5所示为一个大根堆。
堆排序的思路很简单：首先将存放在L[1-n]中的n个元素建成初始堆，因为堆本身的特点(以大顶堆为例),所以堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。
空间效率：仅使用了常数个辅助单元，所以空间复杂度为 O(1)。
时间效率：堆排序的时间复杂度为O(nlogn)。
稳定性：堆排序算法是一种不稳定的排序算法
8.5 归并排序、基数排序
8.5.1归并排序
空间效率：Merge()操作中，辅助空间刚好为n个单元，因此算法的空间复杂度为O(n)。
时间效率：算法的时间复杂度为 O(nlogn):
稳定性：由于 Merge()操作不会改变相同关键字记录的相对次序，因此二路归并排序算法是一种稳定的排序算法。
8.5.2 基数排序
空间效率：一趟排序需要的辅助存储空间为r(r个队列：r个队头指针和r个队尾指针),但以后的排序中会重复使用这些队列，所以基数排序的空间复杂度为O(r)。
时间效率：基数排序需要进行d趟“分配”和”收集”操作。一趟分配需要遍历所有关键字，时间复杂度为O(n);一趟收集需要合并r个队列，时间复杂度为O(r)。因此基数排序的时间复杂度为O(d(n+r)),它与序列的初始状态无关。
稳定性：每一趟分配和收集都是从前往后进行的，不会交换相同关键字的相对位置，因此基数排序是一种稳定的排序算法。
8.6 各种内部排序算法的比较
原文地址：https://blog.csdn.net/qq_55882840/article/details/142729858
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！