排序

[guanpengchn]

int partition(vector<int> &vi, int low, int up)
{
    int pivot = vi[up];
    int i = low-1;
    for (int j = low; j < up; j++)
    {
        if(vi[j] <= pivot)
        {
            i++;
            swap(vi[i], vi[j]);
        }
    }
    swap(vi[i+1], vi[up]);
    return i+1;
}
//C++'s array range should be [low, up], the same as [low, up+1)
void quickSort(vector<int> &vi, int low, int up)
{
    if(low < up)
    {
        int mid = partition(vi, low, up);
        //Watch out! The mid position is on the place, so we don't need to consider it again.
        //That's why below is mid-1, not mid! Otherwise it will occur overflow error!!!
        quickSort(vi, low, mid-1);
        quickSort(vi, mid+1, up);
    }
}

归并排序

void Merge(int a[],int left,int mid,int right)
{
    //两段区间的长度
    int length1 = mid-left+1;
    int length2 = right-mid;

    //分配两段新的内存空间存储原内容
    int *l1 = new int[length1];
    int *l2 = new int[length2];

    for (int i = 0; i < length1; ++i)
    {
        l1[i] = a[left+i];
    }
    for (int j = 0; j < length2; ++j)
    {
        l2[j] = a[j+mid+1];
    }

    //存入原内容之后，比较两个序列
    int i = 0,j = 0;
    int k = length1;
    //比较两个序列的重合部分，进行排序
    while (i<length1 && j<length2)
    {
        if (l1[i] < l2[j])
        {
            a[left++] = l1[i++];
        }
        else
        {
            a[left++] = l2[j++];
            //因为l2[j]大于l1[i],所以l2[j]肯定大于[0,length-1]之中[0,i]之间的所有数，产生逆序对
            if (l2[j] > l1[i])
            {
                _count +=  length1-i+1;
            }       
        }
    }
    //两序列的剩余部分分别放于结尾
    while (i<length1)
    {
        a[left++] = l1[i++];
    }

    while (j<length2)
    {
        a[left++] = l2[j++];
    }

    //分配的内存需要释放掉
    delete []l1;
    delete []l2;
}
void Merge_sort(int a[],int left,int right)
{
    if (left < right)
    {
        int mid = (left+right)/2;//首先进行分区，然后递归操作
        Merge_sort(a,left,mid);
        Merge_sort(a,mid+1,right);//第一次将其分为两个区间，进行合并操作
        Merge(a,left,mid,right);
    }
}