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

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