算法:C++ 实现选择排序、冒泡排序、选择排序、桶排序

x33g5p2x  于2022-04-10 转载在 其他  
字(4.1k)|赞(0)|评价(0)|浏览(332)

1、选择排序

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

原始序列:45 32 65 98 5 42 11 61
1)从序列中取出最小的元素5,将5同序列第一个元素交换,此时产生仅含一个元素的有序序列,序列减一;

结果:5 [11 32 42 45 65 98]

2)从序列中取出最小的元素11,将11同序列第一个元素交换,此时产生仅两个元素的有序序列,序列减一;

结果: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]
最后一个元素肯定是最大元素,排序直接生产一个有序的序列;
结果:13、27、38、49、49、65、76、97

#include <iostream>
#include <cstdio>
using namespace std;
const int Max = 100; //定义数组长度 
int main(){
	int n,k;
	int a[Max];	 //定义
	cout<<"请输入n个数:";
	cin>>n;
	cout<<"输入数据,以空格隔开:"<<endl; 
	for(int i=0;i<n;++i)
		cin>>a[i];
		
	for(int i=0;i<n;++i){
		k=i;	//先默认a[i]为最小值 
		for(int j=i+1;j<n;++j){
			if(a[k]>a[j]) k=j; //判断最小值的位置,赋给k,那k就是最小值的位置 
		}
		int temp;
		if(k!=i){ //k的位置不是i,那么就交换数值;交换后,最小值就是在a[i]的位置 
			temp=a[i];
			a[i]=a[k];
			a[k]=temp;	
		}
	}
	cout<<"选择排序后输出:"<<endl;
	for(int i=0;i<n;++i)
		cout<<a[i]<<" ";
}

  1. 稳定性:在选择排序中,每趟都会选出最大元素与最小元素,然后与两端元素交换,此时,待排序序列中如果存在与原来两端元素相等的元素,稳定性就可能被破坏。如[5,7,5,21,10],在array[0]与array[3]元素交换时,序列的稳定性就被破坏了,所以选择排序是一种不稳定的排序算法。
  2. 时间复杂度:选择排序的时间复杂度为O(n2)。
  3. 适用场景:待排序序列中,元素个数较少时。

2、冒泡排序

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

  1. 读入数据放在数组a中。
  2. 比较相邻的两个元素,如果第一个比第二个大,就将两个数据交换。
  3. 从数组的第0个数据到n-1个数据进行一次遍历,重复2的操作,这样最大的数就“冒”到数组最后一个位置了。
  4. 最后一个已经排好,所以n=n-1,赋值后的n不为0,就重复上面2,3。
#include <iostream>
#include <cstdio>
using namespace std;
const int Max = 100; //定义数组长度 
int main(){
	int n,k;
	int a[Max];	 //定义
	cout<<"请输入n个数:";
	cin>>n;
	cout<<"输入数据,以空格隔开:"<<endl; 
	for(int i=0;i<n;++i) //第1步 
		cin>>a[i];
		
	for(int i=n-1;i>0;--i){ //第4步 
		for(int j=0;j<i;++j){ //第3步 
			int temp;
			if(a[j]>a[j+1]) { //第2步 
			temp=a[j+1];
			a[j+1]=a[j];
			a[j]=temp;	
			}
		}
	}
	cout<<"冒泡排序后输出:"<<endl;
	for(int i=0;i<n;++i)
		cout<<a[i]<<" ";
		
	cout<<endl<<"从大到小:"<<endl;	
	for(int i=n-1;i>=0;--i)
		cout<<a[i]<<" ";
}

  1. 稳定性:在冒泡排序中,遇到相等的值,是不进行交换的,只有遇到不相等的值才进行交换,所以是稳定的排序方式。
  2. 时间复杂度:如果待排序序列的初始状态恰好是我们希望的排序结果(如升序或降序),一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值;冒泡排序最好的时间复杂度为O(n),冒泡排序的最坏时间复杂度为O(n^2)。综上,冒泡排序总的平均时间复杂度为O(n ^2)。

  1. 适用场景:冒泡排序适用于数据量很小的排序场景,因为冒泡的实现方式较为简单。

3、选择排序

基本思想:将初始数据分为有序部分和无序部分,每一步将一个无序部分的数据插入到前面已经排好序的有序部分中,直到插完所有元素为止。
步骤如下:每次从无序部分中取出一个元素,与有序部分中的元素从后向前依次进行比较,并找到合适的位置,将该元素插到有序组当中。

假如有[5,2,3,9,4,7]六个元素,下面就以排序过程中的一个步骤(此时有序部分为[2,3,5,9],无序部分为[4,7],接下来要把无序部分的“4”元素插入到有序部分),来展示一下插入排序的运行过程。

  1. 首先,原始的数组元素是这样的。

其中,浅绿色代表有序部分,黄色代表无序部分。

  1. 在无序部分中挑出要插入到有序部分中的元素。

  1. 将要插入的元素与左边最近的有序部分的元素进行比较。由于4 < 9,所以9向后移,4向前移。
          

  2. 继续将要插入的元素与左边最近的有序部分的元素进行比较。由于4 < 5,所以5向后移,4继续向前移。

  3. 继续将4与3比较。由于4 > 3,所以不再向前比较,插入到当前位置。

  4. 此时有序部分,由[2,3,5,9]变成[2,3,4,5,9]。

#include <iostream>
#include <cstdio>
using namespace std;
const int Max = 100; //定义数组长度 
int main(){
	int n,k,i,j,temp;
	int a[Max];	 //定义
	cout<<"请输入n个数:";
	cin>>n;
	cout<<"输入数据,以空格隔开:"<<endl; 
	for(int i=0;i<n;++i) 
		cin>>a[i];
		
	for(i=1;i<n;++i)
	{
		temp=a[i];
		for(j=i-1;j>=0 &&a[j]>temp ;--j){ //满足条件执行,不满足就跳过 
			a[j+1]=a[j]; //当a[j]>temp,把元素后移一位,直到--j=-1 
		}	
		a[j+1]=temp; //--j=-1后再+1,把temp的值赋给a[--j+1]
	}
	cout<<"插入排序后输出:"<<endl;
	for(int i=0;i<n;++i)
		cout<<a[i]<<" ";
	return 0; 
}

  1. 稳定性:在使用插入排序时,元素从无序部分移动到有序部分时,必须是不相等(大于或小于)时才会移动,相等时不处理,所以直接插入排序是稳定的。
  2. 时间复杂度:在插入排序中,当待排序序列是有序时,是最优的情况,只需当前数跟前一个数比较一下就可以了,这时一共需要比较n- 1次,时间复杂度为O(n)。最坏的情况是待排序数组是逆序的,此时需要比较次数最多,总次数记为:1+2+3+…+N-1,所以,插入排序最坏情况下的时间复杂度为O(n2)。平均来说,array[1…j-1]中的一半元素小于array[j],一半元素大于array[j]。插入排序在平均情况运行时间与最坏情况运行时间一样,是O(n2)。
  3. 适用场景:待排序序列的元素个数不多(<=50),且元素基本有序。

4、桶排序

将待排序的数值k,装入第k个桶,桶号就是待排序的数值,顺序输出各桶的值,得到有序的序列。
步骤:

  1. 先创建数组并初始化值为0。
  2. 把k值装入第k个桶(cin>>k,a[k]),把值+1,同一个桶每装一个就+1。(a[k]++)。
  3. 当a[i]>0,代表第i个桶是有值的,输出i的序号(也就是i值),桶就少了一个值(a[i]–)。

例如:输入n个0-99的整数值,从小到大排序输出。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int Max = 100; //定义数组长度 
int main(){
	int n,k,i,j,temp;
	int a[Max];	 //定义
	memset(a,0,sizeof(a)); //初始化数组值0 
	cout<<"请输入n个数:";
	cin>>n;
	for(i=1;i<=n;++i){
		cin>>k; //输入数值 
		a[k]++; //桶号个数+1 
	}
	
	for(i=0;i<100;i++){ //从小到大输出 
		while(a[i]>0) //判断有桶号 
		{
			cout<<i<<" ";  //输出桶号=桶存的数值 
			a[i]--;  //桶号个数-1,直到没有个数 
		}
	}
	cout<<endl;
	return 0; 
}

**参考文章:**插入排序部分

相关文章

微信公众号

最新文章

更多