集計ソート-逆シーケンスアルゴリズムを求める
まとめて並べ替えてずっと比較的に簡単だと思って、特に重視しないで、今日書いてみて、とても気まずくて、何度も失敗しました.最後にやはり博の記録を書くことにしました.くだらない話は多く言わないで、直接本題に入ります.
アルゴリズム:集計ソートは分割法(分割して治める)の典型的な応用であり、再帰的な考え方を適用し、上から下へ考える:まずMergeSort()が1つの乱順の配列を並べ替えることができると仮定し、そのため「分割」(1つの配列を平均して2つの部分に分ける)を開始し、さらに「治」(それぞれ前後の部分に対してMergeSort()を呼び出して秩序化する)を開始することができる.最后にもう1つの合并子関数Merge()を书いて、それは2つの秩序ある配列を合并することができて、Merge()は実现しやすいです.ただ2つのポインタを管理して、それぞれ2つのサブ配列の初めを指して、新しいメモリを开いて中间の结果を保存して、2つの配列を遍歴して完成することができて、时间はΘ(n).
n個の要素の配列がMergeSort()を呼び出すのに時間T(n)がかかるとする.従って、T(n)=2 T(n/2)+Θ(n).主定理から分かる:T(n)=Θ(nlogn).集計ソートアルゴリズムの時間的複雑さはΘ(nlogn)、空間複雑度はΘ(n).
集計ソートにより拡張する逆シーケンス数を求めることができる.
逆シーケンス数の定義:iA[j]の場合.A[i]とA[j]は逆序数対である.逆序数対の個数を逆序数と呼ぶ.従って逆序数を求めるには2つのポインタ,2回の走査配列,蛮力法により求めることができ,明らかに時間的複雑度はΘ(n^2).では、もっと早い方法はありますか?答えは肯定的で、集計ソート法を利用して、少し改善すればよい.Merge()では、2つの整列した配列Aを合併するが、B.はA.Bが整列しているため、A,Bのそれぞれの逆シーケンス数は0であるため、ABの逆シーケンス数はA,Bの間の逆シーケンス数に等しい.
例えば、A=1,4,6,7,9 B=2,3,5,10,13,21.Mergeでは現在のi号元素の4が2より大きいことが発見する、4の逆序数は+1を必要とし、また6,7,9が4の後ろに並んでいるため、6,7,9の逆序数も+1すべきであるため、全体の逆序数にlast-i+1を加えるべきである.(i号元素がB[j]よりも小さい(例えば4対5より小さい)場合、逆序数の変化を特定することができず、何の変更もしない).
コード:
アルゴリズム:集計ソートは分割法(分割して治める)の典型的な応用であり、再帰的な考え方を適用し、上から下へ考える:まずMergeSort()が1つの乱順の配列を並べ替えることができると仮定し、そのため「分割」(1つの配列を平均して2つの部分に分ける)を開始し、さらに「治」(それぞれ前後の部分に対してMergeSort()を呼び出して秩序化する)を開始することができる.最后にもう1つの合并子関数Merge()を书いて、それは2つの秩序ある配列を合并することができて、Merge()は実现しやすいです.ただ2つのポインタを管理して、それぞれ2つのサブ配列の初めを指して、新しいメモリを开いて中间の结果を保存して、2つの配列を遍歴して完成することができて、时间はΘ(n).
n個の要素の配列がMergeSort()を呼び出すのに時間T(n)がかかるとする.従って、T(n)=2 T(n/2)+Θ(n).主定理から分かる:T(n)=Θ(nlogn).集計ソートアルゴリズムの時間的複雑さはΘ(nlogn)、空間複雑度はΘ(n).
集計ソートにより拡張する逆シーケンス数を求めることができる.
逆シーケンス数の定義:i
例えば、A=1,4,6,7,9 B=2,3,5,10,13,21.Mergeでは現在のi号元素の4が2より大きいことが発見する、4の逆序数は+1を必要とし、また6,7,9が4の後ろに並んでいるため、6,7,9の逆序数も+1すべきであるため、全体の逆序数にlast-i+1を加えるべきである.(i号元素がB[j]よりも小さい(例えば4対5より小さい)場合、逆序数の変化を特定することができず、何の変更もしない).
コード:
#include<iostream>
using namespace std;
int count=0;//
void Merge(int* A,int left,int mid,int right,int* C)
{ //Merge , :o(n)
int i=left;
int j=mid+1;
int k=left;
while(i <= mid && j <= right)
{
if(A[i] <= A[j])
C[k++]=A[i++];
else
{
C[k++]=A[j++];
count += mid-i+1;//
}
}
while(i <= mid)
C[k++]=A[i++];
while(j <= right)
C[k++]=A[j++];
//C[] ， C[] A[]
for(int i=left;i <= right;++i)
A[i]=C[i];
}
void MergeSort(int* A,int left,int right,int* C)// MergeSort A ．
{
if(left < right)
{
int mid=(left+right)/2;
MergeSort(A,left,mid,C);// 1
MergeSort(A,mid+1,right,C);// 2
Merge(A,left,mid,right,C); //
}
}
void main()
{
int A[]={2,1,3,6,4,0,11,3,5};
int len=sizeof(A)/sizeof(A[0]);
int *C=new int[len];
MergeSort(A,0,len-1,C);
for(int i=0;i<len;++i)
cout<<A[i]<<' ';
cout<<endl;
cout<<count<<endl;
delete[] C;
}