JAVA簡単選択並べ替えアルゴリズムの原理と実現
4783 ワード
単純選択ソート:(最小値を選択して、第1位に置いて、それから第1位を後ろに移動して、このように循環します)第1位と後ろの各位を1つずつ比較して、毎回最小のトップを置いて、第1位を後ろに推進します(つまり、選択したばかりの第1位は最小値で、比較に参加しないで、比較回数は1を減らします)
複雑度:記録移動を行う操作回数は0-3(n-1)より少なく、記録の初期配列にかかわらず、必要なキーワード間の比較回数は同じで、いずれもn(n-1)/2であり、総時間複雑度はO(n 2)である.空間複雑度O(1)
アルゴリズムの改善:比較するたびに、最小の値を第1位に置くため、最後まで比べることができて、最小の値を探し出して、直接第1位に置いて、無意味な交換移動操作を省くことができます.方向を変えて、最後のビットを前の各ビットと比較して、最大値を沈下するたびに、最後のビットを前進させることもできます.
JAVAソース:
単純選択ソート(Simple Selection Sort):単純選択ソートはバブルソート(Bubble Sort)に似ており、そのたびに残りの要素セットから現在の位置に最も値を入力するように選択されます.唯一の違いは、バブルソートが発見されるたびに前の値よりも小さいことです.(またはそれ以上)の場合は、要素の位置が交換されますが、単純なソートは、残りの要素のうちの最値と現在の位置を選択してデータを交換します.たとえば、要素の集合R={37,40,38,42,461,5,7,9,12}については、1回目のソートで37と直接5とが交換され、新しいシーケンスR 1={5,40,38,42461,37,7,9,12}が形成されます.2番目のソートでは、40が直接7と交換され、新しいシーケンスR 2={5,7,38,42461,37,40,9,12}が形成され、最後の要素まで(2番目のソートでは38が42より小さいが、データを交換していないことに注意).以下は、ソートを簡単に選択するJava実装バージョンである.
ツリー選択ソート(Tree Selection Sort)ツリー選択ソートアルゴリズムは、単純選択ソートに対して、典型的には空間的に時間を入れ替えるアルゴリズムである.ソートされたN個の要素に対して、比較的小さい(n+1)/2個の数を作り、その後、比較的小さい[n+1]1つの要素しかないまで、4つの数です.完全な二叉木に構成されています.ソートすると、その要素が最小になります.最小要素を取り出し、その要素を「最大値」に置き換え、完全なツリーを調整します.次に、ツリー選択ソートのJava実装版を示します.
完全二叉木を構築するにはN個の要素の集合に対して2*N−1個の補助空間が必要である.コード:
再帰的な構造の新しいセットの最小値が実現されます.
複雑度:記録移動を行う操作回数は0-3(n-1)より少なく、記録の初期配列にかかわらず、必要なキーワード間の比較回数は同じで、いずれもn(n-1)/2であり、総時間複雑度はO(n 2)である.空間複雑度O(1)
アルゴリズムの改善:比較するたびに、最小の値を第1位に置くため、最後まで比べることができて、最小の値を探し出して、直接第1位に置いて、無意味な交換移動操作を省くことができます.方向を変えて、最後のビットを前の各ビットと比較して、最大値を沈下するたびに、最後のビットを前進させることもできます.
JAVAソース:
public static void selectSort(Date[] days) {
int min;
Date temp;
for (int i = 0; i < days.length; i++) {
min = i;
for (int j = min + 1; j < days.length; j++) {
if (days[min].compare(days[j]) > 0) {
min = j;
}
}
if (min != i) {
temp = days[i];
days[i] = days[min];
days[min] = temp;
}
}
}
class Date {
int year, month, day;
Date(int y, int m, int d) {
year = y;
month = m;
day = d;
}
public int compare(Date date) {
return year > date.year ? 1 : year < date.year ? -1
: month > date.month ? 1 : month < date.month ? -1
: day > date.day ? 1 : day < date.day ? -1 : 0;
}
public void print() {
System.out.println(year + " " + month + " " + day);
}
}
単純選択ソート(Simple Selection Sort):単純選択ソートはバブルソート(Bubble Sort)に似ており、そのたびに残りの要素セットから現在の位置に最も値を入力するように選択されます.唯一の違いは、バブルソートが発見されるたびに前の値よりも小さいことです.(またはそれ以上)の場合は、要素の位置が交換されますが、単純なソートは、残りの要素のうちの最値と現在の位置を選択してデータを交換します.たとえば、要素の集合R={37,40,38,42,461,5,7,9,12}については、1回目のソートで37と直接5とが交換され、新しいシーケンスR 1={5,40,38,42461,37,7,9,12}が形成されます.2番目のソートでは、40が直接7と交換され、新しいシーケンスR 2={5,7,38,42461,37,40,9,12}が形成され、最後の要素まで(2番目のソートでは38が42より小さいが、データを交換していないことに注意).以下は、ソートを簡単に選択するJava実装バージョンである.
public static void selectionSort（int[] data） {
if （data == null || data.length <= 1）
return;
int i, j, value, minPos, len = data.length;
int outer = len - 1, tmp;
for （i = 0; i < outer; i++） {
value = data[i];
minPos = -1;
for （j = i + 1; j < len; j++） {
if （data[j] < value） {
minPos = j;
value = data[j];
}
}
if （minPos != -1） {
tmp = data[i];
data[i] = value;
data[minPos] = tmp;
}
// for （int k = 0; k < len; k++） {
// System.out.print（data[k] + " , "）；
// }
// System.out.println（）；
}
}
public static void main（String[] args） {
int[] coll = {
37, 40, 38, 42, 461, 5, 7, 9, 12
};
selectionSort（coll）；
for （int i = 0; i < coll.length; i++） {
System.out.print（coll[i] + " , "）；
}
}
ツリー選択ソート(Tree Selection Sort)ツリー選択ソートアルゴリズムは、単純選択ソートに対して、典型的には空間的に時間を入れ替えるアルゴリズムである.ソートされたN個の要素に対して、比較的小さい(n+1)/2個の数を作り、その後、比較的小さい[n+1]1つの要素しかないまで、4つの数です.完全な二叉木に構成されています.ソートすると、その要素が最小になります.最小要素を取り出し、その要素を「最大値」に置き換え、完全なツリーを調整します.次に、ツリー選択ソートのJava実装版を示します.
public static void treeSelectionSort（int[] data） {
if （data == null || data.length <= 1）
return;
int len = data.length , low = 0 , i , j;
// add Auxiliary Space
int[] tmp = new int[2*len -1];
int tSize = tmp.length;
//construct a tree
for（i =len-1 , j=tmp.length-1;i >=0 ;i--,j--）{
tmp[j]=data[i];
}
for（i = tSize -1 ; i > 0 ; i-=2）{
tmp[（i-1）/2] = tmp[i] > tmp[i-1]? tmp[i-1]:tmp[i];
}
//end
//remove the minimum node.
while（low < len）{
data[low++] = tmp[0];
for（j=tSize-1;tmp[j]!=tmp[0];j--）；
tmp[j] = Integer.MAX_VALUE;
while（j > 0）{
if（j%2 == 0）{ //
tmp[（j-1）/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
j = （j-1）/2;
}else{ //
tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
j = j/2;
}
}
}
}
完全二叉木を構築するにはN個の要素の集合に対して2*N−1個の補助空間が必要である.コード:
while（j > 0）{
if（j%2 == 0）{ //
tmp[（j-1）/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
j = （j-1）/2;
}else{ //
tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
j = j/2;
}
}
再帰的な構造の新しいセットの最小値が実現されます.