C++基础算法③——排序算法(选择、冒泡附完整代码)

排序算法

1、选择排序

2、冒泡排序

---

1、选择排序

基本思想：从头至尾扫描序列，每一趟从待排序元素中找出最小(最大)的一个元素值，然后与第一个元素交换值，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。

原始序列：45 32 65 98 5 42 11 61

• ① 从序列中取出最小的元素5，将5同序列第一个元素交换，此时产生仅含一个元素的有序序列， 原序列减长度减1；
• 结果：5 [11 32 42 45 65 98]
• ② 从原序列中取出最小的元素11，将11同序列第一个元素交换，此时产生仅两个元素的有序序列，原序列减长度减1；
• 结果：5 11 [32 42 45 65 98]
• 同理重复同样的步骤：
• 结果：5 11 32 [42 45 65 98]
• 结果：5 11 32 42 [45 65 98]
• 结果：5 11 32 42 45 [65 98]
• 结果：5 11 32 42 45 65 [98]
• 最后一个元素肯定是最大元素，排序直接生产一个有序的序列；
• 最终结果：5 11 32 42 45 65 98

编程步骤：

1. 定义数组，并输入值存到数组；
2. 在原无序序列中，找到第一个最小值与该索引；
3. 然后最小值的索引与原来不一致，就交换值；
4. 重复②③步骤；
5. 最后输出结果。

//1.选择排序算法
#include<iostream>
using namespace std;
int a[1000];
int main(){int n,min,index;cin>>n;for(int i=0;i<n;i++){ //1.输入值到数组 cin>>a[i];}for(int i=0;i<n;i++){ min = a[i]; // 假设第一个为最小值 index = i; // 锁定最小值索引 for(int j=i+1;j<n;j++){ //逐个跟后面比对if(min>a[j]){ // 大于最小值，则更新值 min = a[j]; //更新值 index = j;  //更新索引 }}if(i!=index){ // 当索引不一致，代表最小值变了 swap(a[i],a[index]); //那就交换第一个值与最小值的位置。 } }for(int i=0;i<n;i++){ //输出结果。 cout<<a[i]<<" ";}return 0;
} 

1.  稳定性：待排序序列中如果存在与原来两端元素相等的元素，稳定性就可能被破坏。如[2,4,2,1,3]，在排序完后，[1,2,2,3,4] 的a[2]与原来的a[2] 不一致，稳定性就被破坏了，所以选择排序是一种不稳定的排序算法。
2. 时间复杂度：选择排序的时间复杂度为O()。
3. 适用场景：待排序序列中，元素个数较少时。
    

---

2、冒泡排序

基本思想：相邻的元素两两比较，较大的数下沉(排后面)，较小的数冒起来(排前面)，这样一趟比较下来，最大(小)值就会排列在末端。整个过程如同气泡冒起，因此被称作冒泡排序。

原始序列：45 32 65 98 5 42 11 61

• ① 从前往后比，根据相邻两个数比较，大的在后小的在前；
• 第一趟排序：32 45 65 5 42 11 61 98；可以看到最大的数冒到最后面了。
• 接着，排序比较次数可以少一次，因为有一个排好了；
• 对无序：32 45 65 5 42 11 61 进行冒泡排序；
• 第二趟排序：32 45 5 42 11 61 65 98；
• 第三趟排序：32 5 42 11 45 61 65 98；
• 第四趟排序：5 32 11 42 45 61 65 98；
• 第五趟排序：5 11 32 42 45 61 65 98；
• 第六趟排序：5 11 32 42 45 61 65 98； 
• 发现第六趟排序没有改变，就结束循环，排序结束！

编程步骤：

1. 定义数组，并输入值存到数组；
2. 比较相邻两个值，如果前比后大，就将两个值交换。
3. 从第1个依次到最后1个，这一趟就排序完成。
4. 重复②③步骤；直到比较没有再改变数值，就循环结束。
5. 最后输出结果。

//2.冒泡排序 
#include<iostream>
using namespace std;
int a[1000];
int main(){int n;cin>>n;for(int i=0;i<n;i++){ //1.输入值到数组 cin>>a[i];}for(int i=n-1;i>0;i--){bool flag = true; //假设排好 for(int j=0;j<i;j++){if(a[j]>a[j+1]){ //比较相邻的值 swap(a[j],a[j+1]); //交换 flag = false; }}if(flag==true) break; //某一轮排好,没有交换,提前终止。 }for(int i=0;i<n;i++){ //输出结果 cout<<a[i]<<" ";}return 0;
}

1. 稳定性：在冒泡排序中，遇到相等的值，是不进行交换的，只有遇到不相等的值才进行交换，所以是稳定的排序方式。
2. 时间复杂度：选择排序的时间复杂度为O()。
3. 适用场景：冒泡排序适用于数据量很小的排序场景，因为冒泡的实现方式较为简单。