基础算法——排序

1   快速排序
    void quicksort(int a[], int l, int r)
    {
        if(l>=r)return;
        int x = a[l+r>>1], i = l-1, j = r+1;//每次交换后会往中间进一位
        while (i < j)
        {
            do i++;
                while (a[i] < x);
            do j--;
                while (a[j] > x);
            if (i<j)swap(a[i], a[j]);
        }
        quicksort(a, l, j);               //x有+1的时候为i-1,i 没有为j,j+1
        quicksort(a, j+1, r);
    }

2   归并排序

    void merge(int a[],int l,int r)
    {
        if(l>=r)
            return ;

        int mid=(l+r)>>1;、

        merge(a,l,mid);
        merge(a,mid+1,r);

        int i=l,j=mid+1;

        for(int k=l;k<=r;k++)
        {
            if(j>r||i<=mid&&a[i]<=a[j])
                b[k]=a[i++];
            else
                b[k]=a[j++];
        }

        for(int k=l;k<=r;k++)
            a[k]=b[k];
    }

3   离散化
    当数组下标过大或蕴含负数，而我们只需使用其中有限个的信息时

    vector<int> vi;
    void lisan()
    {
        sort( vi.begin(), vi.end() );
        erase( unique( vi.begin(), vi.end() ), vi.end() );
    }

    int find(int x)
    {
        return lower_bound( vi.begin(), vi.end(), x ) - vi.begin();
    }

4   第k大的数
    快排的每一趟，基准左边 <= x ,右边 >= x 
    左边元素的个数 s1 = j - l + 1, 如果k <= s1 ，
    下次递归的区间就是左边，否则右边


5   逆序对
    归并排序中是比较a[i]和a[j]的大小,小的放在前面,
    如果a[j]比a[i]小，则a[i]中mid+1-i个都可与a[j]构成逆序对