【基础算法】排序
Kreedy_Ke
·
2022-09-04 19:30:20
·
个人记录
引子
生活中常能看见排序的身影：一次考试的排名，一个班级的队伍，一本字典的排版，都需要按照某种依据来排序。有可能是分数的高低，有可能是身高的参差，有可能是字母的顺序。排序很有用，在信息学竞赛中也不例外。
概述
排序算法（英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法。 ——OI wiki
排序作为一种十分常用的算法，自然是每个信息学竞赛选手都必须牢牢掌握的。而排序的方法多种多样，不同方法有不同的优劣，可以视情况而选择。
当我们在讨论一种排序的算法时，有几样东西是必须注意的：
时间复杂度
不用说，我们肯定都希望时间复杂度越少越好，但有时也并非如此。
空间复杂度
同样也是判断算法优劣的一个参数，一般也是越少越好。
稳定性
一种排序算法是否具有稳定性取决于相等的元素在排序之后的相对位置是否会发生改变。
打个比方，在一个无序序列中有两个相等的元素 a 和 b，且 a 在 b 的前面。在经过具有稳定性的排序算法排序后，a 仍旧在 b 的前面，但在经过不具有稳定性的排序算法排序后，a 不一定在 b 的前面。
基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序。
选择排序、堆排序、快速排序不是稳定排序。
接下来将按照 OI wiki 上的顺序介绍几个常用的排序算法。所有算法的代码都是按从小到大的方式排序，且数组下标从 1 开始。
选择排序
不稳定，时间复杂度 O(n^2)
选择排序是一种非常直观易懂的排序算法，但代价就是复杂度太高了。
选择排序的基本思路是：每次遍历一遍序列，找到第 i 小的元素，并将其与第 i 位上的元素交换。这就像是将一个班的人按身高从矮到高排队，现让最矮的人出列站在第一位，再让次矮的人出列站在第二位……以此类推，直到所有人都出列。
以下为伪代码：
void Selection_sort ( int a[] , int len )
{
for ( int i=1 ; i { int pos=i; //记录第i小的数的下标 for ( int j=i+1 ; j<=len ; j++ ) //因为之前的数肯定都排好了，所以从第i+1位开始枚举 if ( a[j] swap(a[i],a[pos]); //将第i小值与第i位上的数交换 } } 冒泡排序 稳定，时间复杂度 O(n^2) 冒泡排序的思路也非常简单，并且相较于选择排序，其具有稳定性。但平均时间复杂度仍然比较庞大，在数据规模较小时再用吧。 冒泡排序的基本思路是：不断遍历序列，如果相邻两个元素不符合需要的排序顺序的话，则将两个元素交换。直到没有元素可以交换时，排序完毕。 如：将序列按从小到大的顺序排序，当遍历到第 i 个元素时，发现第 i+1 个元素小于它，则将两个元素交换。可以发现，当序列越趋近于有序时，所需的交换次数越少，当序列有序时，有最优时间复杂度 O(n)。 以下为伪代码： void Bubble_sort ( int a[] , int len ) { bool wy=1; //看是否结束排序 while ( wy ) //只要还有可以交换的一对元素，就不断循环 { wy=0; //一开始相信没有可以交换的了 for ( int i=1 ; i if ( a[i]>a[i+1] ) //遇见可以换的就换 wy=1,swap(a[i],a[i+1]); } } 碎碎念：关于为什么冒泡排序叫冒泡排序，OI wiki 上是这么说的： 由于在算法的执行过程中，较小的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。 咱也不知道咋就像了，咱也不敢问 插入排序 稳定，时间复杂度 O(n^2) 插入排序的思路很常见，并且在序列几乎有序时效率很高，但就是算如此其仍有 O(n^2) 的最坏时间复杂度和平均时间复杂度。 插入排序的基本思路是：将整个序列分为“未排序”和“已排序”两个部分，每次从“未排序”的部分中选取一个元素，按照排序要求插入到“已排序”的正确位置上。 与其相似的操作就是整理扑克牌了，每次从桌上选取一张牌按大小顺序插入到自己的手牌中。 以下为伪代码： void Insertion_sort ( int a[] , int len ) { for ( int i=2 ; i<=len ; i++ ) //将第一个元素视作已排序部分 for ( int j=i ; j>1 ; j-- ) //在已排序部分中搜索合适的位置 if ( a[j] swap(a[j],a[j-1]); //就交换二者位置，直至遇见第一个小于等于新插入元素的元素 } 计数排序 稳定，时间复杂度 O(n+w)，其中 w 为序列中元素取值范围的上界 计数排序的时间复杂度是线性的，但其特殊的性质导致其只能在数据范围较小时使用，可以说有优有劣。 计数排序的基本思路是：使用另一个数组存放待排序序列中值为 i 的元素的个数，然后根据这个新的数组进行排序，主要步骤有三步： 统计每个元素出现的次数 求出出现次数的前缀和 利用前缀和排序 不过如果已知不同元素的个数也较少时也可以使用计数排序，只需要映射一下就可以了。 以下为伪代码，假设取值范围为 a_i \leq10^6： int b[N],cnt[N]; //备用数组和记录数组，记录数组 void Counting_sort ( int a[] , int len ) { for ( int i=1 ; i<=len ; i++ ) cnt[a[i]]++; //记录元素个数 for ( int i=1 ; i<=1000009 ; i++ ) cnt[i]+=cnt[i-1]; //求前缀和 for ( int i=len ; i ; i-- ) b[cnt[a[i]]--]=a[i]; //依照前缀和求排名 for ( int i=1 ; i<=len ; i++ ) a[i]=b[i]; //返回到原数组 } 基数排序 一般稳定，内部使用计数排序时的时间复杂度为 O(kn+ \sum_{i=1}^kw_i)，其中 k 为关键字个数，w_i 为第 i 个关键字的值域大小 基数排序其实不能单用，一般会与计数排序等稳定排序相结合使用，而其稳定性及时间复杂度取决于内部使用的排序方法。其空间复杂度是线性的，为 O(k+n)。一般来讲在空间足够的情况下使用基数排序会更快。 基数排序的基本思路是：将待排序的序列中的各个元素分成 k 个关键字，然后从第 k 个关键字到第 1 个关键字逐一进行一种稳定排序，直到结束时排序完成。 由于基数排序的性质，导致其可以在一些地方发挥出其他排序算法所不能做到的事，比如大整数排序等。另外其也在求后缀数组中发挥一席之地。 由于代码一般视题目情况而定，在此仅给出 OI wiki 上的一种写法，伪代码如下，假设关键字个数为 100 以下： int k,w[N]; //k为关键字个数，w数组为第i关键字的值域大小 struct node { int key[109]; //关键字数组 friend bool operator < ( node p , node q ) //为方便其它种类排序所使用的重载 { for ( int i=1 ; i<=k ; i++ ) if ( p.key[i]==q.key[i] ) continue; //就像字典序排序一样 else return p.key[i] return 0; //返回0，表示不变 } }d[N],e[N]; //使用结构体存放需要排序的元素以及备用数组 void Radix_sort ( int len ) { for ( int i=k ; i ; i-- ) //从最后一个关键字开始计数排序 { memset(cnt,0,sizeof cnt); for ( int j=1 ; j<=len ; j++ ) cnt[d[j].key[i]]++; for ( int j=1 ; j<=w[i] ; j++ ) cnt[j]+=cnt[j-1]; for ( int j=len ; j ; j-- ) e[cnt[d[j].key[i]]--]=d[j]; for ( int j=1 ; j<=len ; j++ ) d[i]=e[i]; } } 快速排序 不稳定，朴素方法最优与平均时间复杂度为 O(n\log n)，最坏时间复杂度为 O(n^2) 别看快排的最坏时间复杂度好像很悲剧，其在实战中的表现还是很突出的，具体原因可以看这篇博客。 快排的基本思路分为三步： 将序列分为两部分，并保持相对大小关系 再在两个子序列中进行快速排序 直到最后无法再分割时排序完成 过程与归并排序有相似之处，但分割之后不需要合并。且第一步中要保持相对大小关系，比如前一个序列中的所有数都小于后一个序列中的数。为保证时间复杂度，一般随机选取一个数作为分界。 分割之后，一般维护一前一后两个指针 p 与 q，用以保持相对大小关系。例如后指针 q 指向了一个小于分界值的元素，则交换 p，q 指针上的元素，且指针后移一位。直至指针相遇。 但事实上选取分解值和维护关系不一定需要这样做，具体情况具体分析。 朴素算法伪代码如下： void Quick_sort ( int a[] , int l , int r ) { int i=l,j=r,mid=a[l+r>>1]; //前后两个指针，分界值取中间数 do { while ( a[i] while ( a[j]>mid ) j--; //右区间不断找小于mid的元素 if ( i<=j ) swap(a[i++],a[j--]); //可以换就换 }while( i<=j ); //注意等于号 if ( l if ( i } 不过快速排序虽然叫做快排，但如果碰上毒瘤数据（例如已经排序好了的序列）也可能会被卡成 O(n^2)。对此，有几种优化快排的方法： 三路快速排序 三路快速排序为快排与基排的结合。 其与快排不同之处在于：当随机选择分界值时，将序列中的元素分为三个部分：小于分界值、等于分界值、大于分界值。 如此就实现了将与分界值相等的元素聚在分界值附近的效果，这导致其在处理有多个重复元素的序列的排序中效率更高，最优时间复杂度为 O(n)。 内省排序 内省排序为快排与堆排的结合。其确保最坏时间复杂度为 O(n\log n)。 其与快排不同之处在于：内省排序将快排最大递归深度限制在 \log_2n，一旦超过就使用堆排，以此来防止退化。 C++ 中 归并排序 稳定，时间复杂度 O(n\log n) 归并排序的空间复杂度一般都为 O(n)，虽然说也可以优化到 O(1)，但为了便捷还是会选择 O(n) 算法。 归并排序的基本思路是：将待排序序列均分为左右两个序列进行递归排序，结束后将两个序列合并，最后就得到了排好序的序列了。这其中最关键的部分是合并。为此，我们一般会新开一个备用数组来辅助排序。 假设已经将左右两个序列都已经有序，就在这两个序列开头设置两个指针。 由于已经排好序，那么这两个指针所指向的就分别是这两个序列的最小值。然后比较这两个指针所指的值，将其中较小值放入备用数组中，对应的指针后移一位。 重复以上操作直至一个指针指向队尾，此时退出循环，将另一个指针之后的所有元素放到备用数组之后。此时备用数组中的所有元素有序，只需要将其复制到原数组即可。 以下为伪代码： int t[N]; //备用数组 void Merge_sort ( int a[] , int l , int r ) { if ( l>=r ) return ; //区间长度小于等于1就退出 int mid=l+r>>1; //取区间中点 Merge_sort(a,l,mid); Merge_sort(a,mid+1,r); //左右区间递归 /*i,j为两个指针，k为备用数组指针，只有当左右序列都遍历完才退出*/ for ( int i=l,j=mid+1,k=l ; i<=mid || j<=r ; k++ ) /*如果右序列已经遍历完或者左序列没遍历完且左序列选择的值小于右序列选择的值*/ if ( j==r+1 || (a[i]<=a[j] && i<=mid) ) t[k]=a[i++]; //则将左序列的值放入备用数组，左序列指针右移一位 /*否则说明左序列遍历完或者左序列选择的值小于右序列选择的值*/ else t[k]=a[j++]; //则将右序列的值放入备用数组，右序列指针右移一位 for ( int i=l ; i<=r ; i++ ) a[i]=t[i]; //备用数组此时一定有序，将其复制到原数组中 } 顺便一提，求逆序对个数也可以用归并排序来做，只需要将上面代码中的 else t[k]=a[j++]; 改为 else t[k]=a[j++],cnt+=mid-i+1; 即可。 堆排序 不稳定，时间复杂度 O(n\log n)。 堆排序利用二叉堆进行排序，其本质是建立在堆上的选择排序，因此其也跟选择排序一样不稳定。 堆排序仅适用于数组，所以接下来用数组替代话中的序列。 堆排序的基本思路是：先在数组上建立一个二叉堆，然后利用二叉堆的性质进行选择排序。 以大根堆为例，每次将根取出并与第 i 个元素交换， i 表示当前取出的是第 i 大元素。 二叉堆有大根堆小根堆之分，区别就在于是让最大还是最小的元素当根。 每次取出元素也都取根，之后继续维护其性质。堆的建立是 O(n\log n) 的时间复杂度，单次维护是 O(\log n) 的时间复杂度。 由于二叉堆的性质，一个下标为 i 的节点的父节点与左右子节点下标分别为 i\div2，i\times2，i\times2+1。（下标从 1 开始） 以下为伪代码，以大根堆为例： /*OI wiki上的思路，我不是很理解，所以还是比较习惯STL里的堆*/ void Heapify ( int a[] , int l , int r ) //调整二叉堆 { int fa=l,son=l*2; //得到父节点和左子节点下标 while ( son<=r ) //只有当左子节点在范围内时才操作 { if ( son+1<=r && a[son] if ( a[fa]>=a[son] ) return ; //如果父节点已经比子节点大了，则调整完毕，直接退出 else swap(a[fa],a[son]),fa=son,son=fa*2; //否则交换子节点与父节点，继续调整 } } void Heap_sort ( int a[] , int len ) { for ( int i=len>>1 ; i ; i-- ) Heapify(a,i,len); //完成堆化 for ( int i=len ; i-1 ; i-- ) //选择排序思路 swap(a[1],a[i]),Heapify(a,1,i-1); //换完之后重新调整 } 其实 C++ 中的 小根堆为 priority_queue 比赛里也可以直接使用，用于堆排序的示例如下，以小根堆为例： /*STL写法，太简单了我太爱了*/ priority_queue void Heap_sort ( int a[] , int len ) { for ( int i=1 ; i<=len ; i++ ) q.emplace(a[i]); for ( int i=1 ; !q.empty() ; a[i++]=q.top(),q.pop() ) ; } 桶排序 一般稳定，平均时间复杂度为 O(n+\frac{n^2}{k}+k)，最坏时间复杂度为 O(n^2)。其中 k 为桶的数量。 桶排序与基数排序有些类似，毕竟它们都得靠内部排序来完成排序的操作。 桶排序适用于对于值域较大但分布较均匀的序列进行排序。但其空间复杂度较大，为 O(n\times k)。 桶排序的基本思路分为 4 步： 用一个数组当作空桶，为了方便这里用 vector 遍历一遍数组，将元素放入对应的桶中 对每个桶进行排序，一般使用插入排序 再从各个桶中将排好序的元素放回来 其实桶排序就是将序列中的各元素尽量均分成了不同“等级”，在代码中的表现就是大小区间，将处于这个区间的元素放入对应的第几个桶中，再在内部排序，就可以使整体有序了。 欸等等，刚才是不是有种排序的思路差不多？是的，计数排序。事实上你会发现，当分出来的大小区间恰好一个区间一个数值时，就是计数排序。所以现在知道了：计数排序就是桶排序的一种特殊情况。 以下为伪代码，假设值域为 a_i\leq10^6，且桶个数为 k： // 这份代码是错的！！！！！！！！！！！！！ // 不知道为什么但在本地VsCode上测试时总报错找不出错因 // 搁置在这了，也许永远也不会再动了，就当是个思路吧 // 当然你要想帮我调那更好 vector void Bucket_sort ( int a[] , int len ) { int siz=W/n+1; //定义单个桶的大小为值域大小除以桶个数 for ( int i=1 ; i<=len ; i++ ) tong[a[i]/siz].push_back(a[i]); //将元素放入对应的桶中 for ( int i=0,p=1 ; i { if ( tong[i].empty() ) continue; //空桶不用排序 for ( int j=1 ; j for ( int u=j ; u+1 ; u-- ) if ( tong[i][u] swap(tong[i][u],tong[i][u-1]); for ( int j=0 ; j a[p++]=tong[i][j]; //将排好序的桶内部元素放回到原数组 } } 常用的就是上面的这些了，接下来再简单介绍两种拓展的排序算法。 希尔排序 不稳定，最优时间复杂度 O(n)，最坏时间复杂度 O(n\log n) 希尔排序也叫缩小增量排序法，是插排的一种改进，以其发明者希尔命名。 锦标赛排序 不稳定，时间复杂度 O(n\log n) 锦标赛排序也叫树形选择排序，是选择排序的优化，堆排的变体。其名字来源于单败淘汰制的竞赛形式。 总结 排序算法千变万化，在竞赛中各算法有各自的适用范围，请自行判断并使用。并且一些排序过程中的思想也可以被用作解决其他问题，如归并排序解决逆序对问题。所以多敲几遍代码总是不会错的。 拓展 C++ 中的算法库