7つのよくある並べ替えアルゴリズムのまとめ
30664 ワード
文書のバージョン
開発ツール
テストプラットフォーム
プロジェクト名
日付
作者
コメント
V 1.0
2016.04.06
lutianfei
none
V 1.1
2016.07.16
lutianfei
正規並べ替えの説明を追加しました.
V 2.0
2016.07.19
lutianfei
順序付けアルゴリズムのまとめを改善しました.並べ替えの別の方法 外部並べ替え:内部と外部の間でデータを何回も交換する必要があります. を行うことができます.内の並べ替え: クラスの並べ替えを挿入します. 直接並べ替え を挿入します.ヒル順序 クラスの並べ替えを選択します. 簡単な選択順序 ヒープ並べ替え 交換クラスの順序付け 発泡体並べ替え 快速並べ替え 正規並べ替え 正規並べ替え ソート方法
平均して
ベスト?コンディション
最悪の場合
補助スペース
安定性
泡の並べ替え
O(n^2)
O(n)
O(n^2)
O(1)
安定している
並べ替えを簡単に選択
O(n^2)
O(n^2)
O(n^2)
O(1)
安定している
並べ替えの直接挿入
O(n^2)
O(n)
O(n^2)
O(1)
安定している
ヒルの並べ替え
O(nlogn)~O(n^2)
O(n^1.3)
O(n^2)
O(1)
不安定です
積み上げ順序
O(nlogn)
O(nlogn)
O(nlogn)
O(1)
不安定です
並べ替え
O(nlogn)
O(nlogn)
O(nlogn)
O(n)
安定している
クイックソート
O(nlogn)
O(nlogn)
O(n^2)
O(logn)~O(n)
不安定です試験工程説明 以下は以下のテストケースで試験を行います.
発泡アルゴリズム基本的な考え方:2つは隣接記録のキーワードを比較し、逆順序であれば、逆順序の記録がなくなるまで交換する. 初級発泡アルゴリズム
上記の最適化泡並べ替えアルゴリズムの問題は、データが途中で並べ替えられたら、後続の比較作業が継続され、時間の無駄が生じることである.さらに最適化することは、フラグを追加することです.比較を続ける必要がありますか?の最良の場合:配列自体が秩序化しており、n-1の比較だけが必要であり、交換は不要であり、時間の複雑さはO(n) である.最悪の場合:配列が逆順である場合は、n*(n-1)/2を比較し、等桁の記録移動が必要であり、時間複雑度はO(n^2) である.
クラスの並べ替えを選択基本的な考え方:n−i＋1(i＝1,2,…,n−1)個の記録の中でキーワードの最小記録を選択し、順序付けシーケンスのi番目の記録として を記録する.
並べ替えを簡単に選択は、 簡単な並べ替えの最大の特徴:移動データの交換回数はかなり少ないです.できれば0回交換して、最悪の場合はn-1回交換してください.配列の数は多くないが、各配列要素が大きい場合に適用されます. 時間の複雑さ:最悪の場合も、比較回数は同じです.n(n-1)/2、合計時間複雑度O(n^2) 簡単な選択順序付け性能は、発泡体の順序付けよりやや優れている. クラスの並べ替えを挿入
並べ替えアルゴリズムを直接挿入は、順序付けされた順序テーブルに記録を挿入することにより、新たな記録数増1の順序テーブルを得る. の最良の場合:自己秩序の場合、n−1回と比較し、移動記録がなく、時間複雑度はO(n)となる. 最悪の場合:逆順の場合はn(n−1)／2回比較し、移動回数はn＋2(n−2)／2回となる. は移動回数を平均的に比較します.n^2/4ですので、直接並べ替えを挿入する時間の複雑さはO(n^2)です. 直接挿入ソート法は発泡体と簡単な選択順序付けの性能より優れています. ソートアルゴリズムを改良
クラスの並べ替えを挿入
ヒルの並べ替えアルゴリズム基本的な順序:小さなキーワードは基本的に前にあり、大きなキーワードは基本的に後ろにあり、ほぼ中央にある. ホッピング分割戦略:ある「増分」から離れた記録をサブシーケンスに構成することで、サブシーケンス内で直接挿入順序付けを行った後に得られた結果は、局所秩序ではなく基本秩序であることが保証される. ヒルの並べ替えの鍵は、むやみにグループ化した後に各自が並べ替えるのではなく、ある増分の配列を隔ててサブシーケンスを構成し、ジャンプ式の移動を実現することである. インクリメンタルの選択実験は、インクリメンタルシーケンスがdelt[k]=(t-k＋1)-1(0<=k<=t==log 2(n＋1)である場合には効果が良いことを証明していますが、最後の増分値は1に等しい必要があります. この時時間の複雑さはO(n^1.5) です.ヒル順序はホッピング記録であるため、安定した順序付けアルゴリズムではない. クラスの並べ替えを選択
積み上げ順序簡単に並べ替えを選択する問題:各比較結果を保存していません.次の比較では、前の便でやったことが多いです. ステップを実行配列長がnであると仮定し、0~n-1 をラベリングする.は、まず、 以下の2ステップはn-1回循環した後、並べ替えが完了します. は、大屋根の は、残りのn−1個の要素を大一番上の山に再構成する. 注:山の頂の完全な二叉の木の数学の定義 K[i]=K[2 i＋1],i=0…n-1 K[i]=K[2 i+2],i=0…n-1 山の頂を構築する時間の複雑さはO(n) である.第iのヒープトップ記録の再構築にはO(logi)時間が必要であり、n-1回を取るため、ヒープの再構築時間の複雑さはO(nlogn) である.最高でも最悪でも、平均時間複雑度はO(nlogn) である.空間複雑度は、一時預かりユニット だけが必要です.は、記録の比較と交換がホッピングで行われるため、不安定な順序付け方法 である.は、最初のビルドに必要な比較回数が多いため、バンド順序付けシーケンスの個数が少ない場合には適していない. 並べ替え原理:最初のシーケンスがn個の記録を含むと仮定すると、n個の秩序化されたサブシーケンスと見なされ、各サブシーケンスの長さは1であり、その後、両方がまとめられ、_;n/2┒(┒xはx以下の最小整数)個の長さが2または1の秩序化されたサブシーケンスが得られる.このように繰り返して、長さnの秩序化シーケンスが得られるまで、この順序付け方法を2つの正規化順序と呼ぶ. 再帰的に並べ替えを実現する再帰的でない反復方法は、再帰時の深さがlog 2^nのスタック空間であることを回避し、必要な空間は、帰納申請用の一時的なtR配列だけを使用するので、空間複雑度はO(n)であり、再帰性も時間性能に一定の向上があることを回避する. 最高、最悪、平均的に全体的な時間複雑度はO(nlogn) である.は、再帰的帰納のために、元の記録シーケンスと同じ数の記憶空間を必要としているので、帰納結果および再帰時のlognの深さのスタック空間を保存し、空間複雑度O(n＋logn) 非再帰的方式の規格化順序:空間複雑度はO(n) である.は、規則化された順序付けアルゴリズムとして正規化されている. クイックソートアルゴリズム基本思想:順序付けによって順序付け記録を独立した2つの部分に分割し、そのうちの一部の記録のキーワードは、他の部分の記録のキーワードよりも小さい場合、それらの2つの部分の記録を連続的に並べ替えて、シーケンス全体の順序付けを達成することができる. 最適度O(nlogn) 最悪時間複雑度O(n^2) 空間複雑度O(logn) 快速並べ替えは、不安定な並べ替え方法 である.
開発ツール
テストプラットフォーム
プロジェクト名
日付
作者
コメント
V 1.0
2016.04.06
lutianfei
none
V 1.1
2016.07.16
lutianfei
正規並べ替えの説明を追加しました.
V 2.0
2016.07.19
lutianfei
順序付けアルゴリズムのまとめを改善しました.
平均して
ベスト?コンディション
最悪の場合
補助スペース
安定性
泡の並べ替え
O(n^2)
O(n)
O(n^2)
O(1)
安定している
並べ替えを簡単に選択
O(n^2)
O(n^2)
O(n^2)
O(1)
安定している
並べ替えの直接挿入
O(n^2)
O(n)
O(n^2)
O(1)
安定している
ヒルの並べ替え
O(nlogn)~O(n^2)
O(n^1.3)
O(n^2)
O(1)
不安定です
積み上げ順序
O(nlogn)
O(nlogn)
O(nlogn)
O(1)
不安定です
並べ替え
O(nlogn)
O(nlogn)
O(nlogn)
O(n)
安定している
クイックソート
O(nlogn)
O(nlogn)
O(n^2)
O(logn)~O(n)
不安定です
public static void main(String[] args) {
int[] A = new int[] { 11, 2, 3, 22, 4, 1, 11, 10, 6, 5, 22, 13, 21 };
int n = A.length;
int[] A_sort = new int[n];
System.out.println(" ：");
arrayPrint(A);
System.out.println(" ：");
mSort(A,A_sort,0, n-1);
// System.out.println(A);
arrayPrint(A_sort);
System.out.println(" ");
Arrays.sort(A);
arrayPrint(A);
}
/**
*
* @MethodName : arrayPrint
* @Description:
* @date : 2016-7-6 , 4:51:43
* @param : @param A
* @Version : v1.0
*/
public static void arrayPrint(int[] A) {
System.out.print("[ ");
for (int i = 0; i < A.length; i++) {
System.out.print(A[i] + " ");
}
System.out.println("]");
System.out.println();
}発泡アルゴリズム
/**
*
* @MethodName : bubbleSort0
* @Description:
* @date : 2016 7 19 , 10:10:53
* @param : @param A
* @Version : vx.x
*/
public static void bubbleSort0(int[] A){
for(int i=0;i < A.length-1;i++){
for(int j=i+1;jif(A[i] > A[j]){
swap(A,i,j);
}
}
}
} /**
*
* @MethodName : buubleSort1
* @Description:
* @date : 2016 7 19 , 10:57:17
* @param : @param A
* @Version : vx.x
*/
public static void bubbleSort1(int[] A){
for(int i = 0;ifor(int j=A.length-1;j>i;j--){ //j
if(A[j-1] > A[j]){ //
swap(A,j-1,j);
}
}
}
} 上記の最適化泡並べ替えアルゴリズムの問題は、データが途中で並べ替えられたら、後続の比較作業が継続され、時間の無駄が生じることである.さらに最適化することは、フラグを追加することです.比較を続ける必要がありますか?
/**
*
* @MethodName : bubbleSort2
* @Description:
* @date : 2016 7 19 , 11:26:36
* @param : @param A
* @Version : vx.x
*/
public static void bubbleSort2(int [] A){
boolean flag = true;
for(int i=0; ifalse;
for(int j=A.length-1;j>i;j--){
if(A[j-1] > A[j]){
swap(A,j-1,j);
flag = true;
}
}
}
} クラスの並べ替えを選択
並べ替えを簡単に選択
n-i回のキーワード間の比較により、n−i＋1個のレコードからキーワードの最小の記録を選出し、i番目(1<=i<=n)のレコードと交換する./**
*
* @MethodName : selectSort
* @Description:
* @date : 2016 7 19 , 11:48:40
* @param : @param A
* @Version : vx.x
*/
public static void selectSort(int[] A){
for(int i=0;i1;i++){
int min = i;
for(int j=i+1;jif(A[min] > A[j]){
min = j;
}
}
if(i != min){
swap(A,i,min);
}
}
} 並べ替えアルゴリズムを直接挿入
/**
*
* @MethodName : insertSort
* @Description:
* @date : 2016 7 19 , 3:05:31
* @param : @param A
* @Version : vx.x
*/
public static void insertSort(int[] A){
for(int i=1;i// 1 ： A[0] , 。
if(A[i] < A[i-1]){ // A[i]
int tmp = A[i];// A[i]
int j;
for(j=i-1; j>=0 && A[j] > tmp; j--){ // A[i], j-- ， A[j+1]
A[j+1] = A[j];
}
A[j+1] = tmp;
}
}
} クラスの並べ替えを挿入
ヒルの並べ替えアルゴリズム
/**
*
* @MethodName : shellSort
* @Description:
* @date : 2016 7 19 , 4:06:41
* @param : @param A
* @Version : vx.x
*/
public static void shellSort(int[] A){
int inc = A.length; // inc inc
//
do{
inc = inc/4 + 1;
for(int i=inc;iif(A[i] < A[i-inc]){
int tmp = A[i];
int j=0;
for(j=i-inc;j>=0 && tmp < A[j]; j-=inc){
A[j+inc] = A[j];
}
A[j+inc] = tmp;
}
}
}
while(inc>1);
} 積み上げ順序
フォーマットの に従って配列を並べ替える. を と位置を交換する./**
*
* @MethodName : heapSort
* @Description:
* @date : 2016 7 19 , 5:29:24
* @param : @param A
* @param : @param n
* @Version : vx.x
*/
public static void heapSort(int[] A,int n){
for(int i=(n-1)/2 ;i>=0;i--){
// （A[(n-1)/2]） ， ， ， 。
// 0 0， 。
heapAdjust(A,i,n-1);
}
for(int i=n-1;i>0;i--){
// n-1 ， A[0]， A[i-1]
// 1 ， A[0]，A[1]
swap(A,0,i);
heapAdjust(A,0,i-1);
}
}
/**
*
* @MethodName : heapAdjust
* @Description:
* @date : 2016 7 19 , 5:37:06
* @param : @param A
* @param : @param s
* @param : @param m
* @Version : vx.x
*/
public static void heapAdjust(int[] A, int s, int m){
int tmp = A[s];
for(int j=2*s+1;j<=m;j=j*2+1){
if(j1]){ // ， ; j
j++;
}
if(tmp > A[j]){ // A[s] ， true ， for
break;
}
else{ // ， s j， ，
A[s] = A[j];
s=j;
}
}
A[s] = tmp;// ， ， 。
} /**
*
* @MethodName : mSort
* @Description:
* @date : 2016-7-6 , 4:27:19
* @param : @param sR ：
* @param : @param tR1 ：
* @param : @param s ：
* @param : @param t ：
* @Version : v1.0
*/
static void mSort(int[] sR,int[] tR1, int s , int t){
int m; //
int[] tR2 = new int[sR.length]; //
if(s==t){
tR1[s]=sR[s];
}
else {
m=(s+t)/2; // sR[s..t] sR[s..m] sR[m+1..t]
mSort(sR, tR2, s, m); // sR[s..m] tR2[s..m]
mSort(sR, tR2, m+1, t); // sR[m+1,t] tR2[m+1..t]
merge(tR2,tR1,s,m,t); // tR2[s..m] tR2[m+1,t] tR1[s..t]
}
}
/**
*
* @MethodName : merge
* @Description:
* @date : 2016-7-6 , 4:40:33
* @param : @param sR ：
* @param : @param tR ：
* @param : @param i ：
* @param : @param m ：
* @param : @param n ：
* @Version : vx.x
*/
static void merge(int sR[],int tR[] ,int i ,int m ,int n){
int j,k,l;
for(j=m+1,k=i;i<=m && j<=n;k++){
if(sR[i] < sR[j]){
tR[k] = sR[i++];
}else {
tR[k] = sR[j++];
}
}
if(i<=m){
for(l=0;l<=m-i;l++){
tR[k+l]=sR[i+l];
}
}
if(j<=n){
for(l=0;l<=n-j;l++){
tR[k+l]=sR[j+l];
}
}
}/**
*
* @MethodName : mergeSort
* @Description:
* @param : @param sR
* @date : 2016-7-6 , 9:15:30
* @Version : v1.0
*/
static int[] mergeSort(int[] sR){
int m; //
int[] tR = new int[sR.length]; //
int k=1; //
while(k < sR.length){
MergePass(sR,tR,k,sR.length-1);
k=k*2;
MergePass(tR,sR,k,sR.length-1);
k=k*2;
}
return sR;
}
/**
*
* @MethodName : MergePass
* @Description: sR s tR
* @date : 2016-7-6 , 9:20:15
* @param : @param sR ：
* @param : @param tR ：
* @param : @param s ：
* @param : @param n ：
* @Version : v1.0
*/
static void MergePass(int sR[] , int tR[], int s , int n){
int i = 0;
while(i <= n-2*s+1){ // 2s ：
merge(sR, tR, i, i+s-1, i+2*s-1);
i=i+2*s;
}
if(i1){// 2s
merge(sR, tR, i, i+s-1, n);
}
else{
for(int j=i;j<=n;j++){
tR[j] = sR[j];
}
}
}
/**
*
* @MethodName : merge
* @Description:
* @date : 2016-7-6 , 4:40:33
* @param : @param sR ：
* @param : @param tR ：
* @param : @param i ：
* @param : @param m ：
* @param : @param n ：
* @Version : vx.x
*/
static void merge(int sR[],int tR[] ,int i ,int m ,int n){
int j,k,l;
for(j=m+1,k=i;i<=m && j<=n;k++){
if(sR[i] < sR[j]){
tR[k] = sR[i++];
}else {
tR[k] = sR[j++];
}
}
if(i<=m){
for(l=0;l<=m-i;l++){
tR[k+l]=sR[i+l];
}
}
if(j<=n){
for(l=0;l<=n-j;l++){
tR[k+l]=sR[j+l];
}
}
}
/**
*
* @MethodName : quickSort
* @Description:
* @date : 2016 7 18 , 7:19:20
* @param : @param A
* @return
* @Version : vx.x
*/
public static void quickSort(int[] A,int startIdx,int endIdx){
int pivot;
if(startIdx < endIdx){
pivot = partition(A,startIdx,endIdx); // ， pivot
quickSort(A,startIdx,pivot-1); //
quickSort(A,pivot+1,endIdx); //
}
}
/**
*
* @MethodName : partition
* @Description:
* @date : 2016 7 18 , 11:18:15
* @param : @param A
* @param : @param startIdx
* @param : @param endIdx
* @param : @return
* @Version : vx.x
*/
public static int partition(int[] A,int startIdx,int endIdx){
int pivotkey;
pivotkey = A[startIdx]; //
while(startIdx < endIdx){
while(startIdx < endIdx && A[endIdx] >= pivotkey){ // pivotkey=A[startIdx]
endIdx--;
}
swap(A,startIdx,endIdx);
//pivotkey = A[endIdx]
while(startIdx < endIdx && A[startIdx] <= pivotkey){
startIdx++;
}
swap(A,startIdx,endIdx); //pivotkey=A[startIdx]
}
return startIdx;
}
/**
*
* @MethodName : swap
* @Description: a,b
* @date : 2016 7 18 , 11:37:53
* @param : @param A
* @param : @param a
* @param : @param b
* @Version : vx.x
*/
static void swap(int[] A , int a, int b){
int temp = A[a];
A[a] = A[b];
A[b] = temp;
}