排序算法

冒泡排序

$\tt a[1],a[2],a[3],...,a[n]$

依次比较相邻两个数，如果$\tt a[i]>a[i+1]$,那么交换两个数的值。$\tt i:1\to n-1$我们要执行以上操作$\tt n-1$次,第$\tt j$次确定是$\tt a[n-j+1]$的值。

for (int i = 1; i <= n - 1; i ++ )
   if (a[i]>a[i+1] swap(a[i],a[i+1]);

上述代码在最坏的情况下要被执行$\tt n-1$次:

for (int i = 1; i < n ; i ++ ) {  
     for (int j = 1; j < n ; j ++ )
        if (a[j]>a[j+1]) swap(a[j],a[j+1])
}

逆序对

逆序对是一个二元组$\tt (i,j),i<j,且a[i]>a[j]$.

逆序对暴力做法：

int ans = 0;
for (int i = 1 ; i < n ; i ++ ）
    for (int j = i + 1; j <= n ; j ++ )
       if (a[i]>a[j]) ans++；

对于降序数据来说逆序对数等于:$\tt C_n^2=\frac{n(n-1)}{2}$.

我们冒泡排序中相邻两个数,每交换一次，逆序对总数-1.所以逆序对数=交换次数。

冒泡排序的优化：

for (int i = 1; i < n ; i ++ ) {  
   bool flag=true;
  for (int j = 1; j < n ; j ++ )
        if (a[j]>a[j+1]) swap(a[j],a[j+1]),flag=false;  
   if (flag) break;
}

插入排序

思想:每次将$\tt a[i]$插入到$\tt a[1]..a[i-1]$这个有序的数组里。从$\tt i$开始每次比较前一个数，如果比前一个数小，那么交换两个数，将i-1.否则它本身就是一个有序的数组了。

for (int i = 2; i <= n ; i ++ ) {
   for (int j = i ; j > 1; j --)
     if (a[j]<a[j+1]) swap(a[j],a[j+1]); 
     else break;
}

例题：合并果子

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1E4 + 10;
int a[maxn];
int n;

bool cmp(int a,int b) {
	return a>b;
}
int main() {
	cin>>n;
	for (int i = 1; i <= n ; i ++ ) cin>>a[i];
	sort(a+1,a+n+1,cmp);
	int ans = 0;	
	for (int d = 1; d < n ; d ++ ) {
		int w = n - d + 1;
		a[w-1]+=a[w];
		ans+=a[w-1];
		for (int j = w-1; j >= 2; j -- )
		   if (a[j]>a[j-1]) swap(a[j],a[j-1]);
		   else break;
	}
	cout<<ans<<endl;
	return 0;
}

例题：P7910 插入排序

选择排序

依次确定$\tt a[1],a[2],...,a[n]$

$\tt a[1]$是$\tt a[1]..a[n]$中最小的数

$\tt a[2]$是$\tt a[2]..a[n]$中最小的数.

for (int i = 1; i < n ; i ++ ) {
    int k = i; 
    for (int j = i ; j <= n ; j ++ )
       if (a[j]<a[k]) k = j;
    swap(a[k],a[i]);
}

桶排序

桶排序必须满足$\tt 0\le a[i]\le 10^6$.

开一个数组$\tt b[i]$表示$\tt i$这个数字出现了多少次。

我只要依次枚举$0\to 10^6$就可以排好序。

$\tt a[]={1,3,3,4,5,2,7,9}$

$\tt b[1]=1,b[2]=1,b[3]=2,b[4]=1,b[5]=1,b[7]=1,b[9]=1$

for (int i = 1; i <= n ; i ++ )  b[a[i]]++;
for (int i = 1; i <= 1000000;i ++ ) 
{
    if (b[i]==0) continue; 
    int j = b[i];
    while (j--) cout<<i<<'  ';
}

基数排序

#include<bits/stdc++.h>
using namespace std;

int n,w;
int a[100010];
vector<int> v[10];
int main() {
	cin>>n;
	int mx = 0;
	for (int i = 1; i <= n ; i ++) {
		cin>>a[i];
		mx = max(a[i],mx);
	}
	for(int p=1;mx/p!=0;p*=10) {
		for (int i = 1; i <= n ; i ++ )
		   v[a[i]/p%10].push_back(a[i]);
		int cnt = 0;
		for (int i = 0 ; i < 9 ; i ++ ) {
			for (int j = 0; j < v[i].size();j ++) 
			    a[++cnt]=v[i][j];
			v[i].clear();//清空 
		}
	} 
	for (int i = 1; i <= n ; i ++ ) {
		cout<<a[i]<<' ';
	} 
	return 0;
}