1.快速排序 quick_sort

#include<iostream>
using namespace std;
const int N=1010;
int a[N];
void quick(int *a,int l,int r)
{
    if(l>=r) return;
    int l1=l-1,r1=r+1;
    int x=a[(l+r)>>1];
    while(l1<r1)
    {
        do l1++;while(a[l1]<x);
        do r1--;while(a[r1]>x);
        if(l1<r1) swap(a[l1],a[r1]);
    }
    quick(a,l,r1),quick(a,r1+1,r);
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=0;i<n;i++) cin>>a[i];
    quick(a,l,r);
    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    return 0;
}

2.希尔排序 shell_sort

#include<iostream>
using namespace std;
const int N=1010;
int a[N];
void shell(int *a,int l,int r)
{
    int step=1;
    if(step<(r-l+1)/3) step=3*(r-l+1)+1;
    while(step>=1)
    {
        for(int i=l+step;i<=r;i++)
        {
            for (int ii = i; ii - step >= l && a[ii-step]>a[ii]; ii -= step)
                swap(a[ii-step],a[ii]);
        }
        step/=2;
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=0;i<n;i++) cin>>a[i];
    quick(a,l,r);
    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    return 0;
}

3.冒泡排序(未优化版) bubble_sort

#include<iostream>
using namespace std;
const int N=1010;
int a[N];
void bubble(int *a,int l,int r)
{
    for(int i=0;i<r;i++)//第i+1轮
        for(int j=l;j<r-i;j++)
            if(a[j]>a[j+1]) swap(a[j],a[j+1]);
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=0;i<n;i++) cin>>a[i];
    bubble(a,l,r);
    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    return 0;
}

4.冒泡排序(优化版) bubble_sort

#include<iostream>
using namespace std;
const int N=1010;
int a[N];
void bubble(int *a,int l,int r)
{
    bool is_order=true;
    for(int i=0;i<r;i++)//第i+1轮
    {
        for(int j=l;j<r-i;j++)
            if(a[j]>a[j+1]) swap(a[j],a[j+1]),is_order=false;
        if(is_order) break;//数组有序,不需要再排
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=0;i<n;i++) cin>>a[i];
    bubble(a,l,r);
    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    return 0;
}

5.选择排序 select_sort

#include<iostream>
using namespace std;
const int N=1010;
int a[N];
void select(int *a,int l,int r)
{
  for(int i=l;i<r;i++) 
  {
      int min=i;
      for(int j=i+1;j<=r;j++)
      {
          if(a[j]<a[min]) min=j;
      }
      if(min!=i) swap(a[min],a[i]);
   }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=0;i<n;i++) cin>>a[i];
    select(a,l,r);
    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    return 0;
}

6.插入排序 insert_sort

#include<iostream>
using namespace std;
const int N=1010;
int a[N];
void insert(int *a,int l,int r)
{
    for(int i=l+1;i<=r;i++)
    {
        for(int j=i;j-1>=l && a[j-1]>a[j];j--)
            swap(a[j-1],a[j]);
    }
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=0;i<n;i++) cin>>a[i];
    insert(a,l,r);
    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    return 0;
}

7.归并排序 merge_sort

#include<iostream>
using namespace std;
const int N=1010;
int a[N],temp[N];
void merge(int a[], int l, int r)
{
    if (l >= r) return ;
    int mid = l+r>>1;
    int t = 0, l1 = l, r1 = mid + 1;
    merge(a, l, mid), merge(a, mid + 1, r);
    while (l1 <= mid && r1 <= r)
        if (a[l1]<a[r1]) temp[t++] = a[l1++];
        else temp[t++] = a[r1++];
    while (l1 <= mid)  temp[t++] = a[l1++];
    while (r1 <= r) temp[t++]=a[r1++];
    for(int i=l,j=0;i<=r;i++,j++) a[i]=temp[j];
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,l,r;
    cin>>n>>l>>r;
    for(int i=0;i<n;i++) cin>>a[i];
    merge(a,l,r);
    for(int i=0;i<n;i++) cout<<a[i]<<' ';
    return 0;
}