c++基础排序

排序算法
输入一个数组A,整理其中元素的相对顺序返回数组B,满足B[i]<=B[i+1]
例如 {5,1,3,4}--->{1,3,4,5}
如果使用暴力算法
n个元素排列,开空间为n的数组,n!种相对顺序,则时间复杂度为O(n!*n),显然时间复杂度太大,就凸显出排序算法的必要性;
那么如何降低其时间复杂度呢?
一.空间复杂度为 O(n^2)
1.插入排序
情景:想想你在打牌时抓牌,为了方便打牌,每一次抓牌时就放到合适的位置,最终便是有序的;
小学生排队,每个人走到应该站的位置;
思想:读入一个元素,在序列中搜寻其合适位置,再放入元素;
问题:插入元素时,后边的元素,向后移动一位;
例如:输入元素 5,1,3,4
0. [5] 1 3 4
1. [1 5] 3 4
2. [1 3 5] 4
3. [1 3 4 5]

#include<iostream>
using namespace std;
const int MAXN=1001;//宏定义MAXN=1001 
int main()
{
int n,i,j,k;
float temp,a[MAXN];
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;//找到比a[i]小的位置，退出，插入其后 
if(j!=i-1)
{
temp=a[i];
for(k=i-1;k>j;k--)
a[k+1]=a[k];//空出空位，让给a[i] 
a[k+1]=temp;
} 
}
for(i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}

优点:支持插入元素,每插入一个元素,可在O(n)的时间里,找到其位置,返回数组;
2. 选择排序
情景:老师帮小学生排队,每次挑一个最矮的站在开头;
思想:每一趟从序列中选出最小(或最大)的数放到待排序的序列最前,直到全部排完;
例如: 输入元素 5,1,3,4
1. 1 [3 5 4]
2. 1 3[4 5]
3. 1 3 4 [5]
4. 1 3 4 5

#include<iostream>
using namespace std;
const int MAXN=1001;//宏定义MAXN=1001 
int main()
{
int n,i,j,k;
float temp,a[MAXN];
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)//在无序区找最小值 
{
k=i;
for(j=i+1;j<n;j++)
if(a[j]<a[k]) k=j;
if(k!=i)
{
temp=a[i];a[i]=a[k];a[k]=temp;//最小值交换到a[i ]
}
}
for(i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}

优点:只要维护最小值,易于优化(堆排序) 

3.冒泡排序
思想:使数组满足b[i]<=b[i+1],扫一遍数组B,若发现逆序对(b[i]>b[i+1]),则交换;
例如:输入元素 5,1,4,3
1. 1 5 4 3
2. 1 4 5 3
3. 1 4 3 5
4. 1 3 4 5

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1001;//宏定义MAXN=1001 
int main()
{
int n,i,j,k;
float temp,a[MAXN];
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n-1;i++)
{
for(int j=1;j<=n-i;j++)
{
if(a[j]>a[j+1])//后一个比她小就交换 
swap(a[j],a[j+1]);
}

}
for(i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}

每一次把最大的数“冒 ”到最上面 最坏n次结束 

交换次数等于逆序对个数 

优点: 代码短
4.桶排序
思想:设一个数组,作为一个有序桶,桶号为对应值,将等于K的值放入第K个桶中,个数加一,输出时,按桶号由小到大, 如果桶中有数,桶中个数减一,输出桶号;

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
int b[101],n,i,j,k,m=-100;
memset(b,0,sizeof(b));//初始化
cin>>n;
for(i=1;i<=n;i++)
{
cin>>k;b[k]++;m=max(m,k);
}
for(i=0;i<=m;i++) 
while(b[i]>0)
{
cout<<i<<" ";b[i]--; 
}
cout<<endl;
}

优点:容易理解,最简单排序

二、空间复杂度为O(nlogn)//推荐使用
1.归并排序
算法:分治,选择排序,递归,二分
思想:将已有序的子序列合并,得到完全有序的序列;
步骤:分解,合并;
例如:把5 3 2 4 6排序
1. 5 3 2 | 4 6
2. 5 3 | 2 4 | 6
3. 5|3 2 4 6
4. 3 5 | 2 4 6
5. 2 3 5 | 4 6
6. 2 3 5 4 6
首先不断分解数组,直到数组有序(内有一个元素)(二分),按数组下标分治,将两个有序的数组归并成一个有序数组;

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
int b[101],n,i,j,k,m=-100;
memset(b,0,sizeof(b));//初始化
cin>>n;
for(i=1;i<=n;i++)
{
cin>>k;b[k]++;m=max(m,k);
}
for(i=0;i<=m;i++) 
while(b[i]>0)
{
cout<<i<<" ";b[i]--; 
}
cout<<endl;
}

应用:给出一个长度为n的数组,求数组中逆序对个数(n<=10^5)
不能用n^2
分治 总的逆序对个数=左半部分逆序对个数+右半部分逆序对个数+左边的数大于右边的数的个数
归并时可顺带求出

#include<iostream> 
#include<cstdio> 
#include<algorithm>
using namespace std;
int r[10010],a[10010];int n,i,ans=0;
void msort(int s,int t)
{
if(s==t) return;
int mid=(s+t)/2;
msort(s,mid);
msort(mid+1,t);
int i=s,j=mid+1,k=s;
while(i<=mid&&j<=t)
{
if(a[i]<=a[j])
{
r[k]=a[i];k++;i++;
}
else
{
r[k]=a[j];k++;j++;
ans+=mid-i+1;//统计 
}
}
while(i<=mid)
{
r[k]=a[i];k++;i++;
}
while(j<=t)
{
r[k]=a[j];k++;j++;
}
for(int i=s;i<=t;i++) a[i]=r[i];

}
int main()
{
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
msort(1,n);
for(i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<endl;
cout<<ans; 
return 0;
}

2.快速排序
快速排序是对冒泡排序的一种改进,不稳定的排序
思想:从序列中确定驱轴(阈值,基准数),重新排列,把比她小的放左边,大的放右边,再从左(右)边的子序列中在确定驱轴,最后便有序
按值分治

#include<iostream>
#include<cstdio>
using namespace std;
int a[10001];
void qsort(int l,int r)
{
int i,j,mid,p;
i=l;j=r;
mid=a[(l+r)/2];
do
{
while(a[i]<mid)i++;
while(a[j]>mid)j--;
if(i<=j)
{
p=a[i];a[i]=a[j];a[j]=p;
i++;j--;
}
}while(i<=j);
if(l<j) qsort(l,j);
if(i<r) qsort(i,r);
}
int main()
{
int n,i;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]; 
qsort(1,n);
for(i=1;i<=n;i++)
cout<<a[i]<<" ";

return 0;
}

ps:由于数据可能有特殊性,会卡快排,但可能性很小,最好把阈值随机,
一旦被数据卡住,时间复杂度可能会上升,但总的来说, 快排还是挺香的.
小应用:
给出一个数组,长度为n,和整数K,求数组第k大的数(只允许O(n))
类似快速排序，我们先随机找到一个值，然后扫一遍整个序列，这样可以统计出比他大的数的个数X和比他小的数的个数Y，以及跟他相等的个数Z，并按照YZX的顺序重新排列分为三部分
如果K<=Y,那我们不用管后部分，第K小元素一定在这些数当中，递归即可
如果Y<k<=Y+Z,那这个元素就是第K小
如果Y+Z<k，那我们不用管前部分，第K小元素一定在后面的那些数中，我们要找那X个数中的第K-(Y+Z)个元素
由于值是随机选取的，我们可以认为他把原数列分成差不多相等的两部分
所以T(N)=O(N)+T(N/2)，算法是O(N)的

#include<cstdio>
#include<iostream>
#include<algorithm> 
using namespace std;
int a[20001],i,n,k;
int cal(int l,int r,int s)
{
int i=l,j=r,tmp=a[(l+r)/2];
while(i<=j)
{
while(a[i]<tmp) i++;
while(a[j]>tmp) j--;
if(i<=j)
{
swap(a[i],a[j]);
i++;
j--;
}
}
if(s<=j-l+1) return cal(l,j,s);
else if(s>i-l) return cal(i,r,s-i+l);
else if(s==i-l) return a[j+1];
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
cout<<cal(1,n,k); 
}

3.堆排序
堆排序基于堆这个数据结构,堆是一个完全二叉树,分为大(小)根堆,性质是父节点比子节点大(小),根节点最大 (小)
思想:每次从根节点取出最大(小),再将二叉树调整为堆,继续用堆的性质

#include<cstdio>
#include<iostream>
#include<algorithm> 
using namespace std;
int a[20001],i,n,k;
int cal(int l,int r,int s)
{
int i=l,j=r,tmp=a[(l+r)/2];
while(i<=j)
{
while(a[i]<tmp) i++;
while(a[j]>tmp) j--;
if(i<=j)
{
swap(a[i],a[j]);
i++;
j--;
}
}
if(s<=j-l+1) return cal(l,j,s);
else if(s>i-l) return cal(i,r,s-i+l);
else if(s==i-l) return a[j+1];
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
cout<<cal(1,n,k); 
}

4.sort排序
O(nlogn)排序好难写呀,当然,懒自有办法
善用std::sort()
对于A数组区间l,r排序,std::sort(A+l,A+r+1)
对于一些特殊排序需求,可以写一个函数compare(a,b)作为比较依据,如果a在b前返回1否则0,
相同的数要返回0 std::sort(A+l,a+r+1,compare)