归并排序 && 快速排序

归并排序：

时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。空间复杂度为 O(n)

归并排序比较占用内存，但却是一种效率高且稳定的算法。

速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

具体思路是，在归并的过程中计算每个小区间的逆序对数，进而计算出大区间的逆序对数。

归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.

#include <cstdio>
int cnt=0;
int x1[50010],x2[50010];
void Merge(int a[],int b[],int left,int middle,int right)
{
    int i=left,j=middle+1,k=left;
    while(i!=middle+1&&j!=right+1)
    {
        if(a[i]<=a[j])
        {
            b[k++]=a[i++];
        }
        else
        {
            cnt+=middle-i+1;  //归并排序求逆序数  
            b[k++]=a[j++];
        }
       // printf("%d
",cnt);
    }
    while(i!=middle+1)
    {
        b[k++]=a[i++];
    }
    while(j!=right+1)
    {
        b[k++]=a[j++];
    }
    for(int i=left;i<=right;i++)
    {
        a[i]=b[i];
        //printf("%d ",a[i]);
    }
    //printf("
");
}

void Merge_sort(int a[],int b[],int left,int right)
{
    int middle;
    if(left<right)
    {
        middle=(left+right)/2;
        //printf("%d %d %d
",left,right,middle);
        Merge_sort(a,b,left,middle);
        Merge_sort(a,b,middle+1,right);
        Merge(a,b,left,middle,right);
    }
    return;
}

int main()
{
   // freopen("a.txt","r",stdin);
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&x1[i]);
    }
    Merge_sort(x1,x2,0,n-1);
    printf("%d
",cnt);
    return 0;
}

快速排序：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

#include <cstdio>

void qsort(int a[],int left,int right)
{
    if(left>=right)  //完成一次 排序
    {
        return;
    }
    int key=a[left],i=left,j=right;
    while(i<j)
    {
        while(i<j&&key<=a[j])
        {   //从后往前查找 比key小的数丢到前面去
            j--;
        }
        a[i]=a[j];
        while(i<j&&key>=a[i])
        {   //从前往后查找 比key大的数丢到后面去
            i++;
        }
        a[j]=a[i];
    }
    a[i]=key;  //在key左边的都比key小，右边的都比key大
    qsort(a,left,i-1); //继续递归 直到 剩下一个数
    qsort(a,i+1,right);
}
int main()
{
    int a[8]={23,10,34,5,9,39,84,77};
    qsort(a,0,7);
    for(int i=0;i<8;i++)
        printf("%d
",a[i]);
    return 0;
}