sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//数组
int a[10]={1,1,2,4,2,4,7,3,2,6};
sort(a,a+10);
//等价于 sort(a,a+10,less<int>()); 从小到大

//vector
vector<int> a={1,1,2,4,2,4,7,3,2,6};
sort(a.begin(),a.end(),greater<int>());

//自定义比较
bool cmp(vector a,vector b)
{
    return a<b;
}
sort(a.begin(),a.end(),cmp);

Bubble sort

n-1趟排序，每趟遍历n个元素，把大的往后排

1
2
3
4
5
6
7
8
9
10
11
// O(n^2)
void bubblesort()
{
    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]);
        }
    }
}

Select Sort

找出第i小的元素，并将其与第i个位置交换

1
2
3
4
5
6
7
8
9
10
11
12
13
//O(n^2)
void selectsort()
{
    for(int i=1;i<=n-1;i++)
    {
        int minpos=i;
        for(int j=i+1;j<=n;j++)
        {
            if(a[j]<a[minpos])  minpos=j;
        }
        swap(a[minpos],a[i]);
    }
}

Insert Sort

从头到尾扫描，把未排序元素插入已排序元素的正确位置中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//O(n^2)
void insertsort()
{
    for(int i=2;i<=n;i++)
    {
        int tmp=a[i];
        for(int j=i-1;j>=1;j--)
        {
            if(tmp<a[j])    a[j+1]=a[j];
            else    break;
        }
        a[j+1]=tmp;
    }
}

Quick Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// O(nlog n)
int quicksort(int l,int r)
{
    if(l>=r)    return;
    int key=a[l+r>>1],i=l-1,j=r+1;
    while(i<j)
    {
        do i++; while(a[i]<key);
        do j--; while(a[j]>key);

        if(i<j) swap(a[i],a[j]);
    }
    quicksort(l,j),quicksort(j+1,r);
}

Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void mergesort(int q[],int l,int r)
{
    if(l>=r)    return;
    int mid=l+r>>1;
    mergesort(q,l,mid),mergesort(q,mid+1,r);

    int k=0,i=l,j=mid+1;
    while(i<=mid && j<=r)
    {
        if(q[i]<=q[j])  tmp[k++]=q[i++];
        else    tmp[k++]=q[j++];
    }
    while(i<=mid)   tmp[k++]=q[i++];
    while(j<=r)     tmp[k++]=q[j++];

    for(int i=l,j=0;i<=r;i++,j++)   q[i]=tmp[j];
}