当前位置：首页 > article >正文

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

article 2024/12/26 3:13:32

排序算法

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( $n^{2}$ )。
适用场景：待排序序列中，元素个数较少时。

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;
}