排序算法练习（二）

分治算法_求逆序对

AYYZOJ p1434

【问题描述】
　　给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。
【输入格式】
　　第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。
【输出格式】
　　所有逆序对总数。
【输入样例】
　　4
　　3
　　2
　　3
　　2
【输出样例】
　　3
【数据范围】
　　N<=10^5，Ai<=10^5。

思路：与归并排序联系起来。

分析：

    归并排序是将序列a[1,H]分成两部分——a[1,mid]和a[mid+1,H]分别进行归并排序，然后将这两部分合并起来。

    在合并的过程中（设1<=i<=mid,mid+1<=j<=H）,

          当a[i]<=a[j]时，并不产生逆序对；

          当a[i]>a[j]时，在前半部分a[1,mid]中，比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid-i+1.（i..mid 共有mid-i+1个数）

            
                 1
                var
                 2   a,r:array[1..100000] of longint;
 3  i,n:longint;ans:int64;
 4procedure mergesort(s,t:longint);
 5var 6    m,i,j,k:longint;
 7begin 8if s=t then exit;
 9     m:=(s+t) div2;
10    mergesort(s,m);
11     mergesort(m+1,t);
12     i:=s;
13     j:=m+1;
14     k:=s;
15while (i<=m) and (j<=t) do16if a[i]<=a[j] then17begin r[k]:=a[i];inc(i);inc(k);end18else19beginans:=ans+m-i+1; r[k]:=a[j]; inc(j); inc(k);end;
20while i<=m dobegin r[k]:=a[i]; inc(i); inc(k);end;
21while j<=t dobegin r[k]:=a[j]; inc(j); inc(k);end;
22for i:=s to t do a[i]:=r[i];
23end;
24begin25  readln(n);
26for i:=1to n do readln(a[i]);
27   mergesort(1,n);
28  writeln(ans);
29end.
        

排序算法_车厢重组

AYYZOJ p1437

这题的描述让人一眼觉得就是冒泡排序，老师说正解应该是归并，可是数据太弱，冒泡就水过了。

                 1
                program
                 p1437;

                 2
                var
                 3
                 n,i,j,t,k:longint;

                 4  a:array[1..10000] of longint;
 5 flag:boolean;
 6begin 7 readln(n);
 8for i:=1to n do read(a[i]);
 9for j:=1to n-1do10begin11     flag:=true;
12for i:=1to n-j do13if a[i]>a[i+1] thenbegin14        t:=a[i];a[i]:=a[i+1];a[i+1]:=t; inc(k);
15         flag:=false; end;
16if flag then break;
17end;
18 write(k);
19end.

冒泡排序

原文：http://www.cnblogs.com/vacation/p/5180634.html