排序算法大合集

课后习题正好可以直接测试一遍各个排序算法，以前写代码只会熟练的写冒泡排序，经常在OJ上过不了说是时间复杂度太大，今天趁这个题，练练手，可能还有待优化的代码，望多多指教呀~

1.冒泡排序

**经典的教科书算法，时间复杂度 空间复杂度O(1)**

#include <iostream>
using namespace std;
int main()
{
    int num;

    while(cin>>num)
    {
        int *p=new int [num];
        int i,flag;
        for(i=0;i<num;i++)
            cin>>p[i];
        cin>>flag;
        for(i=0;i<num;i++)
        {
            for(int j=i;j<num;j++)
            {
                int temp;
                if(flag==1 && p[i]<p[j])
                {
                    temp=p[i];
                    p[i]=p[j];
                    p[j]=temp;
                }
                if(flag==0 && p[i]>p[j])
                {
                    temp=p[i];
                    p[i]=p[j];
                    p[j]=temp;
                }
            }
        }
        for(i=0;i<num;i++)
            cout<<p[i]<<' ';
        cout<<endl;
    }
}

选择排序

时间复杂度O(n^2) 空间复杂度O(1)
从小到大。

#include "iostream"
using namespace std;
int main()
{
    int n,i=0;
    cin >> n;
    int *p=new int[n];
    for (i = 0; i < n; i++)
        cin >> p[i];
    for (i=0; i < n; i++)
    {
        int minindex = i;
        for (int j = i; j < n; j++)
        {
            if (p[j] < p[minindex])
            {
                minindex = j;
            }
        }
        int tep = p[minindex];
        p[minindex] = p[i];
        p[i] = tep;
    }
    for (i = 0; i < n; i++)
        cout << p[i] << "  ";

    delete[]p;
    return 0;
}

归并排序：

#include <iostream>
using namespace std;
void merge(int *p,int left,int mid,int right);
void process(int *p,int left,int right);

int main()
{
    int num;
    while(cin>>num)
    {
        int *p=new int [num];
        int i,flag;
        for(i=0;i<num;i++)
            cin>>p[i];
        cin>>flag;
        //mergeSort过程
        process(p,0,num-1);
        //按照flag进行输出：
        if(flag==0)
        {
            for(i=0;i<num;i++)
                cout<<p[i]<<' ';
        }
        if(flag==1)
        {
            for(i=num-1;i>=0;i--)
                cout<<p[i]<<' ';
        }
        cout<<endl;
    }
}
void merge(int *p,int left,int mid,int right)
{
    int w1=left,w2=mid+1,i=0;
    int *help=new int[right-left+1];
    while(w1<=mid && w2<=right) //按照从小到大进行merge
    {
        if(p[w1]<=p[w2])
        {
            help[i]=p[w1];
            i++;
        }
        else
        {
            help[i]=p[2];
            i++;
        }
    }
    while(w1<=mid)
    {
        help[i]=p[w1];
            i++;
    }
    while(w2<=right)
    {
        help[i]=p[w1];
            i++;
    }
    for(i=0;i<right-left;i++)
    {
        p[i]=help[i];
    }
}
void process(int *p,int left,int right)
{
    if(left==right)
    {
        return;
    }
    int mid=left+(left+right)/2;
    process(p,left,mid);
    process(p,mid+1,right);
    merge(p,left,mid,right);
}