Javaソートアルゴリズムまとめの集計ソート
2073 ワード
この例では、Javaソートアルゴリズムのまとめの集計ソートについて説明します.皆さんの参考にしてください.具体的な分析は以下の通りである.
集計操作(merge)は、集計アルゴリズムとも呼ばれ、2つの並べ替えられたシーケンスを1つのシーケンスに統合する操作を指す.クイックソートと同様に、Javaでの実装をまとめてみましょう.
集計ソート(Merge)は、2つ(または2つ以上)の順序テーブルを新しい順序テーブルに結合します.すなわち、ソートされるシーケンスをいくつかのサブシーケンスに分け、各サブシーケンスが順序付けされます.次に、秩序化されたサブシーケンスを全体的な秩序化されたシーケンスにマージします.
集計ソートは、集計操作に確立された有効なソートアルゴリズムである.このアルゴリズムは分割法(Divide and Conquer)を用いた非常に典型的な応用である.既存のシーケンスのサブシーケンスを結合し、完全に秩序化されたシーケンスを得る.すなわち、各サブシーケンスを秩序化してから、サブシーケンスセグメント間を秩序化する.2つの順序テーブルを1つの順序テーブルに結合すると、2-ルーティング集計と呼ばれます.
集計ソートアルゴリズムは安定であり,配列にはO(n)の余分な空間が必要であり,チェーンテーブルにはO(log(n))の余分な空間が必要であり,時間複雑度はO(nlog(n))であり,アルゴリズムは適応的ではなく,データのランダムな読み取りを必要としない.
動作原理:
1、申請空間は、2つの並べ替えられたシーケンスの和の大きさにする.この空間は、マージされたシーケンス2を格納し、2つのポインタを設定するために使用される.最初の位置は、2つの並べ替えられたシーケンスの開始位置3であり、2つのポインタが指す要素を比較し、比較的小さい要素を選択してマージ空間に入れ、ポインタを次の位置4に移動する.あるポインタがシーケンスの最後の5に達するまで、別のシーケンスの残りのすべての要素を連結シーケンスの最後に直接コピーするには、手順3を繰り返します.
コード実装:
集計ソートは比較的安定したソートである.すなわち,等しい要素の順序は変わらない.例えば,入力レコード1(1)3(2)2(3)2(4)5(5)(括弧の中では記録のキーワード)のときに出力される1(1)2(3)2(4)3(2)5(5)の中の2と2は,入力の順序である.これは,ソートするデータに複数の情報が含まれ,そのうちのいずれかの情報でソートする.他の情報をできるだけ入力順に並べ替えることが重要である.これも高速並べ替えよりも優位である.
本稿で述べたjavaプログラムの設計に役立つことを願っています.
集計操作(merge)は、集計アルゴリズムとも呼ばれ、2つの並べ替えられたシーケンスを1つのシーケンスに統合する操作を指す.クイックソートと同様に、Javaでの実装をまとめてみましょう.
集計ソート(Merge)は、2つ(または2つ以上)の順序テーブルを新しい順序テーブルに結合します.すなわち、ソートされるシーケンスをいくつかのサブシーケンスに分け、各サブシーケンスが順序付けされます.次に、秩序化されたサブシーケンスを全体的な秩序化されたシーケンスにマージします.
集計ソートは、集計操作に確立された有効なソートアルゴリズムである.このアルゴリズムは分割法(Divide and Conquer)を用いた非常に典型的な応用である.既存のシーケンスのサブシーケンスを結合し、完全に秩序化されたシーケンスを得る.すなわち、各サブシーケンスを秩序化してから、サブシーケンスセグメント間を秩序化する.2つの順序テーブルを1つの順序テーブルに結合すると、2-ルーティング集計と呼ばれます.
集計ソートアルゴリズムは安定であり,配列にはO(n)の余分な空間が必要であり,チェーンテーブルにはO(log(n))の余分な空間が必要であり,時間複雑度はO(nlog(n))であり,アルゴリズムは適応的ではなく,データのランダムな読み取りを必要としない.
動作原理:
1、申請空間は、2つの並べ替えられたシーケンスの和の大きさにする.この空間は、マージされたシーケンス2を格納し、2つのポインタを設定するために使用される.最初の位置は、2つの並べ替えられたシーケンスの開始位置3であり、2つのポインタが指す要素を比較し、比較的小さい要素を選択してマージ空間に入れ、ポインタを次の位置4に移動する.あるポインタがシーケンスの最後の5に達するまで、別のシーケンスの残りのすべての要素を連結シーケンスの最後に直接コピーするには、手順3を繰り返します.
コード実装:
////////////////
public void mergeSort(){
long[] workSpace = new long[nElems];
recMergeSort(workSpace,0,nElems-1);
}
private void recMergeSort(long[] workSpace,int lowerBound,int upperBound){
if(lowerBound == upperBound){
return;
}
else{
int mid=(lowerBound+upperBound)/2;
recMergeSort(workSpace, lowerBound, mid);
recMergeSort(workSpace, mid+1, upperBound);
merge(workSpace, lowerBound, mid+1, upperBound);
}
}
private void merge(long[] workSpace,int lowPtr,int highPtr,int upperBound){
int j = 0;
int lowerBound = lowPtr;
int mid = highPtr - 1;
int n = upperBound-lowerBound+1;
while(lowPtr<=mid&&highPtr<=upperBound){
if(theArray[lowPtr]
集計ソートは比較的安定したソートである.すなわち,等しい要素の順序は変わらない.例えば,入力レコード1(1)3(2)2(3)2(4)5(5)(括弧の中では記録のキーワード)のときに出力される1(1)2(3)2(4)3(2)5(5)の中の2と2は,入力の順序である.これは,ソートするデータに複数の情報が含まれ,そのうちのいずれかの情報でソートする.他の情報をできるだけ入力順に並べ替えることが重要である.これも高速並べ替えよりも優位である.
本稿で述べたjavaプログラムの設計に役立つことを願っています.