排序算法
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.选择排序算法
#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;
} 
- 稳定性：待排序序列中如果存在与原来两端元素相等的元素，稳定性就可能被破坏。如[2,4,2,1,3]，在排序完后，[1,2,2,3,4] 的a[2]与原来的a[2] 不一致，稳定性就被破坏了，所以选择排序是一种不稳定的排序算法。
- 时间复杂度：选择排序的时间复杂度为O(
)。
- 适用场景：待排序序列中，元素个数较少时。
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个依次到最后1个，这一趟就排序完成。
- 重复②③步骤；直到比较没有再改变数值，就循环结束。
- 最后输出结果。
//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;
}
- 稳定性：在冒泡排序中，遇到相等的值，是不进行交换的，只有遇到不相等的值才进行交换，所以是稳定的排序方式。
- 时间复杂度：选择排序的时间复杂度为O(
- 适用场景：冒泡排序适用于数据量很小的排序场景，因为冒泡的实现方式较为简单。
