大家好，今天给各位分享C++ 选择排序、冒泡排序、插入排序和计数排序的一些知识，其中也会对进行解释，文章篇幅可能偏长，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在就马上开始吧！

排序算法稳定性

假设待排序的记录序列中有多个关键字相同的记录。如果排序后这些记录的相对顺序保持不变，那么这种排序算法称为稳定的；否则称为不稳定。稳定的。

稳定排序可以利用上次排序的结果来服务本次排序。

判断方法：排序时是否只交换相邻元素。如果是，则排序算法稳定；如果不是，则排序算法不稳定。

例题：朴素排序模版

选择排序

选择排序：每遍从待排序的数据元素中选择最小（或最大）的元素，并将其放在待排序数组的前面。

时间复杂度：O(n^2)，辅助空间复杂度：O(1)，不稳定。

#include iostream 使用命名空间std; int n;int a[110];int main(){cin n; for(int i=1; i=n; i++) cin a[i]; //n – 1 轮循环for(int i=1; i n; i++){ int idx=-1, minv=1e9; for(int j=i + 1; j=n; j++){ if(a[j] a[i] a[ j] minv){ minv=a[j]; } idx=j； if(idx !=-1) 交换(a[i], a[idx]); } for(int i=1; i=n ; i++) cout a[i] ‘ ‘;return 0;}

冒泡排序

冒泡排序：按顺序比较两个相邻元素，如果顺序错误则交换它们。每次冒泡时，最大（最小）的元素都会通过交换“漂浮”到序列的顶部。多次冒泡后即可完成排序。

时间复杂度：O(n^2)，辅助空间复杂度：O(1)，稳定。

冒泡排序—— 普通版

#include iostream 使用命名空间std; int n;int a[110];int main(){cin n; for(int i=1; i=n; i++) cin a[i]; for(int i=1; i n; i++){for(int j=1; j n; j++){ if(a[j] a[j + 1]) 交换(a[j], a[j + 1] ）； } } for(int i=1; i=n; i++) cout a[i] ‘ ‘;return 0;}

冒泡排序优化——提前跳出

如果序列已经有序，则无需执行后续循环。

#include iostream 使用命名空间std; int n;int a[110];int main(){cin n; for(int i=1; i=n; i++) cin a[i]; for(int i=1; i n; i++){ bool flag=true;for(int j=1; j=n – i; j++){ if(a[j] a[j + 1]){ 交换(a [j], a[j + 1]);标志=假； if(flag) 中断； } for(int i=1; i=n; i++) cout a[i] ‘ ‘;return 0;}

插入排序

插入排序：假设前面的n-1 个数字已经有序。现在将第n个数插入到先前已排序的序列中，使得插入后序列仍然是有序的。

时间复杂度：O(n^2)，辅助空间复杂度：O(1)，稳定。

选项1：

#include iostreamusing namespace std;int n;int a[110];int main() {cin n;for (int i=1; i=n; i++) cin a[i];//插入排序for (int i=2; i=n; i++) {int t=a[i];int k=1;while (a[k]=t k i) k++;for (int j=i; j k; j–) a[j ]=a[j – 1];a[k]=t;}for (int i=1; i=n; i++) cout a[i] ‘ ‘;return 0;}选项2:

#include iostreamusing namespace std;int n;int a[110];int main() {cin n;for (int i=1; i=n; i++) cin a[i];//插入排序for (int i=2; i=n; i++) {int j=i; while(j a[j] a[j – 1]){ 交换(a[j], a[j – 1]); j——； }} for (int i=1; i=n; i++) cout a[i] ‘ ‘;return 0;}

桶排序

桶排序：将数据分成有限个有序的桶，对每个桶分别进行排序，最后合并各个桶中的数据。

数据分布到桶中：哈希过程

计数排序

计数排序：是一种特殊的桶排序。桶的数量是可能的数据类型的数量。

计数数组：数组下标是桶号，通常是一个数据值，

数组的值代表数据的数量。

适用条件：待排序的数据为整数且数据范围有限。

设数据个数为n，数据范围为k。

时间复杂度：O(n+k)，附加空间复杂度：O(k)，稳定。

构造计数数组

最终数组：

至此排序已经完成，但是还不稳定。

构造prefix 和cnts 数组：

结果数组为results: results[–cnts[a[i]]]=a[i];

#include iostreamusing 命名空间std;const int N=1010;int n;int a[N], cnts[N], results[N];int main() { cin n;for (int i=0; i n; i++) {cin a[i];cnts[a[i]]++;}for (int i=0; i N; i++)cnts[i+1] +=cnts[i];//为了稳定排序，从后向和前向遍历for (int i=n – 1; i=0; i–) {results[–cnts[a[i]]]=a[i];}for (int i=0 ; i++)计算结果[i] ‘ ‘; return 0;}