排序算法（一）

暑假训练时复习了排序算法，重新理解了这些算法，便在暑假集训结束后写一篇总结（好像上次写博客还在上网课）。本篇主要总结插入排序，冒泡排序，桶排序**（三个稳定排序）**。

先上两张网图：

排序算法分类：

算法时空复杂度：

一.冒泡排序（感觉这是最容易理解的） 比较相邻两个数的大小，小数“上浮”，大数“下沉”，即交换两个数的位置。所以用两层循环即可。第一个for循环遍历所有元素，第二个for循环是每次遍历元素时对相邻两个元素进行一次比较，若反序则交换。因此，时间复杂度是O(n^2)。 以下为源代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,a[1000];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	} 
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
		    if(a[i]>a[j]) swap(a[i],a[j]);//逆序则交换
	    }
	}
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	} 
	return 0;
}

改进：可以设置一个布尔变量，判断是否有交换。若没有交换，说明排序已经完成，进而减少几次排序

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,a[1000];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    bool t;
    for(int i=n-2;i>=0;i--){
        t=true;       //判断是否有交换
        for(int j=0;j<=i;j++){
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
                t=false;
            }
        }
        if(t==true) break;   //没有交换就退出
    }
    for(int i=0;i<n;i++){
    	cout<<a[i]<<" ";
	} 
    return 0;
}

二.桶排序（最快最简单的排序） 百度：工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后依次把各个桶中的记录列出来记得到有序序列。 简单来说，就是把一个数字放在相应下标的数组里，再顺序或逆序输出。（简单粗暴） 代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,a[1000],m;
	memset(a,-1,sizeof(a));	
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>m;
		a[m]=m;//入桶
	}
	for(int i=0;i<=n;i++){
		if(a[i]>-1)	cout<<i<<" ";
	}
	return 0;
 } 

但有一定缺点：无法重复输出同一个数（可能是我的过）。于是就有了以下改进：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,a[1000],m;
	memset(a,0,sizeof(a));	
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>m;
		a[m]++;
	}
	for(int i=0;i<=n;i++){
		while(a[i]>0){  //多次输出同一个数
			cout<<i<<" ";
			a[i]--;
		}
	}
	return 0;
 } 

三.插入排序 插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的。 （发明者肯定特喜欢打扑克） 插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。（就是把一个数插入到一个有序数组中） 代码1：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,i,j,k,a[1000];
	double t;
	cin>>n;
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	for(i=0;i<n;i++){
		for(j=i-1;j>=0;j--) if(a[j]<a[i]) break;
		if(j!=i-1){
			t=a[i];
			for(k=i-1;k>j;k--) a[k+1]=a[k];
			a[k+1]=t;
		}
	}
	for(i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}

代码2：（其实就是改了下第二层循环）

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,a[1000];
	int sum;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int i=0;i<n;i++){
        int j=i-1;
        sum=a[i];
        while(a[j]>=sum&&j>=0){
        	a[j+1]=a[j];
        	j--;
		}
		a[j+1]=sum;
	}
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}

To be continued...