排序算法

快速排序

快速排序是以分治(分而治之)为基本思想。分治就是把一个大问题分成多个子问题逐个解决并最终合并。

1.从所有元素中选出任意一个数字作为基准数。

2.找出所有小于基准数的元素并将其放到左边,找出所有大于基准数的元素放到右边。(这个过程中将基准元素也随之位移)。

3.将左半部分与右半部分分别重复上述操作。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int n;
void quick_sort(int l,int r){
    if(l>=r){
        return ;
    }
    int ll=l,rr=r;
    int mid=a[(l+r)/2];//定义基准数,这里为了方便用中间数
    while(ll<rr){
//从左开始找到比基准数大的第一个数
        while(a[ll]<mid){
            ll++;
        }
//从右开始找到比基准数小的第一个数
        while(a[rr]>mid){
            rr--;
        }
//将这两个数互换,记得ll++并且rr--否则会死循环
        if(ll<=rr){
            swap(a[ll],a[rr]);
            ll++;
            rr--;
        }
    }
//将左右两个部分分别进行下一轮排序
    quick_sort(l,rr);//由于在这里rr一定小于ll,所以是l~rr以及ll~r
    quick_sort(ll,r);
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    quick_sort(0,n-1);
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

归并排序

归并排序是以二分为基本思想的算法。

归并排序可以将两个有序序列合并并排序,也可以用它直接排序一个无序序列。

这里讲用归并排序排序一个无序序列(当然,这两个是相通的)算法复杂度为O(nlogn)。

设从小到大排序
1.将这个序列分成2个子序列,将2个子序列分为4个孙子序列,将4个孙子序列分成8个曾孙子(好吧,我这里不知道写啥)序列……以此类推。

2.当分到只剩下一个元素的时候就不分了,将这个元素和它的父序列的另一个子序列排序。这里的排序过程分为

1)新建一个数组存放排序后的序列(设这个序列为tmp)

2)由于当前序列一定是排序好的序列,所以子序列最左边的元素必定最小,于是将头指针都指向第一个。

3)将指针处的两个元素比较,将小的那个先放入tmp。然后将小的那个的序列的头指针向后延续一个。

4)将余下为存放的元素放进去(x,y两序列。a=1 2 4 5,b=2 3 6 7。这时a指针出已经没有元素,而b还剩6、7。最后将所剩的6、7放进去)。

5)用tmp更新a。

3.这样一个一个回溯好就可以得到排序后的序列了。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int tmp[100005];
void merge_sort(int l,int r){
    if(l==r){
        return ;
    }
    int first,second,mid;
    int arr=l;//arr记录tmp用到哪里了
    mid=(l+r)/2;
    first=l,second=mid+1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
//
    while(first<=mid&&second<=r){
        if(a[first]<=a[second]){
            tmp[arr]=a[first];
            first++,arr++;
        }else{
            tmp[arr]=a[second];
            second++,arr++;
        }
    }
    //将剩下的全部直接放入tmp数组中
    while(first<=mid){
        tmp[arr]=a[first];
        first++,arr++;
    }
    while(second<=r){
        tmp[arr]=a[second];
        second++,arr++;
    }
//更新a
    for(int i=l;i<=r;i++){
        a[i]=tmp[i];
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    merge_sort(0,n-1);
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

计数排序

计数排序顾名思义就是把每个数字出现次数用cnt[]数组记录下来,然后再从cnt[0]开始找到cnt[maxnum]。

从上面就可以得知这是一种非常耗空间复杂度的算法,只能在最小和最大数接近时才能用。

不过这个算法的好处是速度特别快,只有O(n+w)左右。

20170718171603_423.gif

#include<bits/stdc++.h>
using namespace std;
int cnt[1000005];
int a[1000005],b[1000005];
int main(){
    int n,w;
    cin>>n>>w;
    for(int i=0;i<n;i++){
        cin>>a[i];
        cnt[a[i]]++;
    }
    int pos=0;
    for(int i=0;i<=w;i++){
        while(cnt[i]!=0){
            b[pos++]=i;
            cnt[i]--;
        }
    }
    for(int i=0;i<n;i++){
        cout<<b[i]<<" ";
    }
    return 0;
}

本文链接:http://kaispace.com.cn/index.php/archives/557/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者