Javaデータ構造とアルゴリズム(一)---泡が立ち、選択し、ソートアルゴリズムを挿入する.
1、泡立ち順
泡の順序付けの主な法則:
1、2つの隣接する要素を比較し、1つ目が2つ目より大きい場合は、2つを交換します.
2.各対の隣接要素に対して、最初の対から最後の対まで第1のステップを行う.このステップが終わると、最後の要素は最大の数になります.
最初の泡が終わったのです
3、最後の数を除いて、すべての要素について上記の手順を行います.
4.比較が必要な要素がなくなるまで、より少ない要素に対して上記の手順を継続する.
コードは次のとおりです.
バブルソートの説明:
バブルソートは2つのforサイクルで構成され、第1のforサイクルでは変数iが何ラウンド比較が必要かを表し、第2のforサイクルでは変数jが各ラウンドが比較に関与する配列の下標として用いられる.各ラウンドは最大数が最も右側にあるため、各ラウンドの比較後に1つ減少し、jの範囲は徐々に減少する.
バブルソート性能分析:
比較に参加する要素がN個あると仮定すると、第1ラウンドはN-1回を比較する必要があり、第2ラウンドはN-2回を比較する必要がある(1ラウンドごとに1つを減らす)、このように推す(共にN-1ラウンドを行う必要がある).
(N-1)+(N-2)+(N-3)+...+2+1=N*(N-1)/2
Nの値が十分大きい場合、アルゴリズムの比較回数は約Nである²/2、マイナス1を無視します.
仮定データはランダムであり,可能な交換位置を比較するたびに,位置を交換しない可能性があり,確率が50%であると仮定すると,交換回数はNである.²/4.(最悪の場合は逆順で、比較するたびに位置を交換する必要があります)
比較と交換の回数はいずれもN²比例して定数が大きくないため,O表現では2と4を無視して,バブル秩序化運転はいずれもO(N)であった.²)時間レベル.
2、ソートの選択
ソートの主な法則を選択します.
1.並べ替えられるシーケンスの中から、最小の要素を見つける.
2、最小要素が最初の要素でない場合は、最初の要素と交換します.
3、残りのN-1要素に対して、最小の要素を探し出して、上述の操作を行って、並べ替えが終わることを知っています.
コードは次のとおりです.
ソート・パフォーマンス分析を選択します.
選択ソートとバブルソートは同じ回数の比較を行った:N*(N−1)/2であったが,交換回数では,せいぜいN回の交換のみが行われた.
Nの値が大きい場合は比較回数が主であるため,選択順位もO(N)である.²)時間レベルです.しかし、交換回数が少ないため、選択ソートはバブルソートよりも速いです.Nの値が小さい場合、交換時間が比較時間より多い場合、選択ソートはバブルソートよりも速いです.
3、ソートの挿入
挿入ソートの主な法則:
挿入ソートの基本思想は、ステップごとに1つの要素を並べられたシーケンスに挿入し、すべての要素を挿入するまで知ることです.
コードは次のとおりです.
ソート・プロファイルを挿入するには、次の手順に従います.
第1ラウンドでは、最大1回、第2ラウンドでは、最大2回、このようにして、1+2+…+(N-2)+(N-1)=N*(N-1)/2を比較する必要がある
各ラウンドに挿入点が発見される前に,平均半分のデータしか比較されず,N*(N−1)/4に相当し,大きなO表現ではO(N)が必要であると仮定した.²)時間レベル.
コピー回数は比較回数にほぼ等しいが、1回のコピーと1回の交換で消費される時間は異なり、ランダムデータに対して挿入ソートはバブルソートよりも2倍速く、選択ソートよりもやや速い.ただし、逆シーケンスを行う場合は、その都度比較と移動が必要であり、バブルソートよりも速くはない.
転送ゲート:http://www.cnblogs.com/ysocean/p/7896269.html
泡の順序付けの主な法則:
1、2つの隣接する要素を比較し、1つ目が2つ目より大きい場合は、2つを交換します.
2.各対の隣接要素に対して、最初の対から最後の対まで第1のステップを行う.このステップが終わると、最後の要素は最大の数になります.
最初の泡が終わったのです
3、最後の数を除いて、すべての要素について上記の手順を行います.
4.比較が必要な要素がなくなるまで、より少ない要素に対して上記の手順を継続する.
コードは次のとおりです.
public class BubbleSort
{
public static void main(String[] args)
{
//
int[] array = {4,2,8,9,5,7,6,1,3};
int[] result = bubble(array);
}
public static int[] bubble(int[] array){
int sum=0;
//
for(int i=1;i<=array.length;i++){
// true
boolean flag = true;
//j
for(int j= 0;jarray[j+1]){
sum=array[j];
array[j]=array[j+1];
array[j+1]=sum;
flag=false;
}
}
if(flag){
break;
}
//
System.out.println(" "+i+" ");
display(array);
}
return array;
}
public static void display(int[] array){
for(int a:array){
System.out.print(a+" ");
}
System.out.println();
}
} バブルソートの説明:
バブルソートは2つのforサイクルで構成され、第1のforサイクルでは変数iが何ラウンド比較が必要かを表し、第2のforサイクルでは変数jが各ラウンドが比較に関与する配列の下標として用いられる.各ラウンドは最大数が最も右側にあるため、各ラウンドの比較後に1つ減少し、jの範囲は徐々に減少する.
バブルソート性能分析:
比較に参加する要素がN個あると仮定すると、第1ラウンドはN-1回を比較する必要があり、第2ラウンドはN-2回を比較する必要がある(1ラウンドごとに1つを減らす)、このように推す(共にN-1ラウンドを行う必要がある).
(N-1)+(N-2)+(N-3)+...+2+1=N*(N-1)/2
Nの値が十分大きい場合、アルゴリズムの比較回数は約Nである²/2、マイナス1を無視します.
仮定データはランダムであり,可能な交換位置を比較するたびに,位置を交換しない可能性があり,確率が50%であると仮定すると,交換回数はNである.²/4.(最悪の場合は逆順で、比較するたびに位置を交換する必要があります)
比較と交換の回数はいずれもN²比例して定数が大きくないため,O表現では2と4を無視して,バブル秩序化運転はいずれもO(N)であった.²)時間レベル.
2、ソートの選択
ソートの主な法則を選択します.
1.並べ替えられるシーケンスの中から、最小の要素を見つける.
2、最小要素が最初の要素でない場合は、最初の要素と交換します.
3、残りのN-1要素に対して、最小の要素を探し出して、上述の操作を行って、並べ替えが終わることを知っています.
コードは次のとおりです.
public class ChoiceSort
{
public static void main(String[] args)
{
int[] array = {4,2,8,9,5,7,6,1,3};
choice(array);
}
public static int[] choice(int[] array){
// n-1
for(int i=0;iソート・パフォーマンス分析を選択します.
選択ソートとバブルソートは同じ回数の比較を行った:N*(N−1)/2であったが,交換回数では,せいぜいN回の交換のみが行われた.
Nの値が大きい場合は比較回数が主であるため,選択順位もO(N)である.²)時間レベルです.しかし、交換回数が少ないため、選択ソートはバブルソートよりも速いです.Nの値が小さい場合、交換時間が比較時間より多い場合、選択ソートはバブルソートよりも速いです.
3、ソートの挿入
挿入ソートの主な法則:
挿入ソートの基本思想は、ステップごとに1つの要素を並べられたシーケンスに挿入し、すべての要素を挿入するまで知ることです.
コードは次のとおりです.
public class InsertSort
{
public static void main(String[] args)
{
int[] array = {4,2,8,9,5,7,6,1,3};
insert(array);
}
public static void insert(int[] array){
int a=0;
// 1
for(int i=1;i0 && temp ソート・プロファイルを挿入するには、次の手順に従います.
第1ラウンドでは、最大1回、第2ラウンドでは、最大2回、このようにして、1+2+…+(N-2)+(N-1)=N*(N-1)/2を比較する必要がある
各ラウンドに挿入点が発見される前に,平均半分のデータしか比較されず,N*(N−1)/4に相当し,大きなO表現ではO(N)が必要であると仮定した.²)時間レベル.
コピー回数は比較回数にほぼ等しいが、1回のコピーと1回の交換で消費される時間は異なり、ランダムデータに対して挿入ソートはバブルソートよりも2倍速く、選択ソートよりもやや速い.ただし、逆シーケンスを行う場合は、その都度比較と移動が必要であり、バブルソートよりも速くはない.
転送ゲート:http://www.cnblogs.com/ysocean/p/7896269.html