归并排序 解 POJ 2299 Quick-Sort

Description

In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence 9 1 0 5 4 ,

Ultra-QuickSort produces the output 0 1 4 5 9 . Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.

题目链接 http://poj.org/problem?id=2299

Input

The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 — the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.

Output

For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.

Sample Input

5

9 1 0 5 4

3

1 2 3

0

Sample Output

6

0

思路

题目是“快排”，但我忘记快排是什么样的了，但归并排序与题目所描述契合，归并排序就是：比较相邻元素，进行数字移动，达到排序目的。我们只需要将中间“移动步数”这个量（我用tem表示的）累加起来即为答案

Code of this problem(过程详解版)

中间输出了过程模拟，便于理解

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 500005;

int s[N];
int ans[N];
long long sum;

///合并两个排好序的序列
void my_merge(int * s, int start, int mid, int over)
{
    cout << "本次排序开始" << '\n' << '\n';
    cout << "本次参与排序的数" << '\n';
    for(int t = start; t <= over; ++t)
        cout << s[t] << ' ';
    cout << '\n';
    ///两个序列中的数相互比较，将较小的数先插入新的序列中
    int i = start, j = mid + 1, k = start;
    while(i <= mid && j <= over)
    {
        cout << i << ' ' << s[i] << ' ' << j << ' ' << s[j] << '\n';
        if(s[i] > s[j])
        {
            int tem = j - k;///此值记录了排序过程中移动数字的步数
            cout << "tem的值 " << tem << '\n';
            sum += tem;
            ans[k++] = s[j++];
        }
        else
            ans[k++] = s[i++];
    }

    ///剩余元素合并
    while(i <= mid)
        ans[k++] = s[i++];
    while(j <= over)
        ans[k++] = s[j++];

    for(i = start; i <= over; ++i)
        s[i] = ans[i];
    cout << "本次排序结果：" << '\n';
    for(i = start; i <= over; ++i)
        cout << s[i] << ' ';
    cout << '\n' << "本次排序结束" << '\n' << '\n';
}

void merge_sort(int * s, int start, int over)
{
    if(start < over)
    {
        int mid = (start + over) / 2;
        merge_sort(s, start, mid);
        merge_sort(s, mid + 1, over);
        my_merge(s, start, mid, over);
    }
}

int main()
{
    int n;
    while(~scanf("%d", &n) && n)
    {
        sum = 0;
        memset(s, 0, sizeof(s));
        memset(ans, 0, sizeof(ans));
        for(int i = 0; i < n; ++i)
            scanf("%d", &s[i]);
        merge_sort(s, 0, n - 1);
        cout << sum << '\n';
    }
    return 0;
}