poj 2299 Ultra-QuickSort(归并排序)

poj 2299 Ultra-QuickSort(归并排序)

题目：​​class="data-table" data-id="t7a7e9d1-kc9VZCh9" data-transient-attributes="class" data-width="1162px" style="width: 100%; outline: none; border-collapse: collapse;">

Time Limit: 7000MS

Memory Limit: 65536K

Total Submissions: 49165

Accepted: 17984

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.

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

60

本来想用这题来练习线段树的，结果怎么也想不到那里去。后来看别人的代码才明白每个叶子节点存储的不是依据dex存储val[i]而是依据dex在相应位置存储1，然后根据排好序的序列由val[i]追踪dex，左边的1都加起来（逆序数），然后去掉dex的1，如此反复进行就能到达目的。提交代码时我可没这么做，用归并排序累加每一次相邻的交换数就是最终的结果。（临时在百度百科上学习了归并排序||-_-）

冒泡排序的时间的复杂度是O(n^2）.

冒泡排序算法的运作如下：（从后往前）

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

并归排序的时间复杂度：O(nlogn)

设有数列{6，202，100，301，38，8，1}

初始状态：6,202,100,301,38,8，1

第一次归并后：{6,202},{100,301},{8,38},{1}，比较次数：3；

第二次归并后：{6,100,202,301}，{1,8,38}，比较次数：4；

第三次归并后：{1,6,8,38,100,202,301},比较次数：4；

总的比较次数为：3+4+4=11,；

逆序数为14；

归并排序的优势：分治法，已比较了的小部分不再比较，如：{8,38},{1}变成{1,8,38}只比较1和8后{1}的长度成为0，不再比较，直接写下{8,38}。

#include #include using namespace std;const int maxn=5e5+10;int a[maxn],b[maxn];long long sum;void Merge(int sourceArr[],int tempArr[],int startdex,int middex,int enddex){ int i = startdex,j=middex+1,k = startdex; while(i<=middex && j<=enddex) { if(sourceArr[i]>n&&n){ sum=0; for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。