排序的时间复杂度
快速排序
第一种以左右边界为key的写法
void q_sort(long long l,long long r)
{
if(l>=r) return ;
long long i=l,j=r;
long long t=a[l];//t=a[r];
while(i<j)
{
while(a[j]>=t&&i<j) j--; //两个交换
a[i]=a[j];
while(a[i]<=t&&i<j) i++;
a[j]=a[i];
}
a[i]=t;
q_sort(l,i-1);
q_sort(i+1,r);
}
第二种以中间值为key
void q_sort(long long l,long long r)
{
long long i=l,j=r;
long long t=a[(l+r)/2];
while(i<=j)
{
while(a[j]>t) j--;
while(a[i]<t) i++;
if(i<=j)
{
swap(a[i],a[j]);
i++,j--;
}
}
if(l<j) q_sort(l,j);
if(i<r) q_sort(i,r);
}
第k个数字
通过二分的想法
void q_sort(long long l,long long r,long long key)
{
long long i=l,j=r;
long long t=a[l];
while(i<j)
{
while(a[j]>=t&&i<j) j--;
a[i]=a[j];
while(a[i]<=t&&i<j) i++;
a[j]=a[i];
}
a[i]=t;
if(key<i) q_sort(l,i-1,key);
else if(key>i) q_sort(i+1,r,key);
else cout<<a[i];
}
归并排序
思想:通过树的后序遍历来进行操作
教学视频 https://www.bilibili.com/video/BV1ea4y1J7Q4
void msort( int l,int r)
{
if(l==r) return ;
int mid=(l+r)/2;
msort(l,mid);
msort(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
{
if(a[i]<=a[j])
{
b[k++]=a[i++];
}
else
{
b[k++]=a[j++];
sum+=mid-i+1;//统计逆序对
}
while(i<=mid) b[k++]=a[i++];
while(j<=r) b[k++]=a[j++];
for(int i=l;i<=r;i++)
a[i]=b[i];
}
}
冒泡排序
void mbsort( )
{
for(int i=0;i<m-1;i++)
{
for(int j=0;j=m-i-1;j++)
{
if(a[j]>a[j+1])
{
swap(a[j],a[j+1]);
}
}
}
}
选择排序
void xzsort( )
{
for(int i=0;i<m;i++)
{
int k=i;
for(int j=i+1;j<m;j++)
{
if(a[j]<a[k]) k=j;
if(k!=i)
{
swap(a[i],a[k]);
}
}
}
}
桶排序
基数排序
桶排序的进化版
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int m=10;//个位0-9
const int n=8;//所有数字
int b[m][n+1];//桶的个数
int a[n];//数组
int main( )
{
int w=3;//最高位数
for(int i=1;i<=n;i++)
cin>>a[i];
int d=1;
for(int i=1;i<=w;i++)
{
memset(b,0,sizeof(b));
for(int j=1;j<=n;j++)
{
int x=a[j]/d%10;//取某位数字的位数
b[x][++b[x][0]]=a[j];//b[x][0]代表这一位有多少个
}
int num=1;
for(int j=0;j<m;j++)
{
for(int k=1;k<=b[j][0];k++)
a[num++]=b[j][k];//添加
}
d*=10;//下一位
}
for(int i=1;i<=n;i++)
cout<<a[i]<<' ';
}