古典(java版)ソートアルゴリズムの分析と実現の3つの簡単な選択ソート
ソートの選択――ソート選択ソートを簡単に選択する基本的な考え方は、ソートされるレコードの中からキーワードの最小のレコードを選択し、すべてのレコードがソートされるまで、ソートされたサブシリーズの最後に順番に置くことです.単純選択ソートは、直接選択ソートとも呼ばれます.基本アルゴリズム:与えられたソート対象シーケンスA[0.....n]を、A[0]~A[n-1]から1回目に最小値を選択する、A[0]と交換し、2回目にA[1]~A[n-1]から最小値を選択し、A[1]と交換する、...,第i回A[i-1]~A[n-1]から最小値を選択し、A[i-1]と交換するn−1回目はA[n−2]~A[n−1]から最小値を選択し、A[n−2]と交換し、合計n−1回で、ソートコードによって小さいから大きいまで配列された秩序配列を得た.
直接選択ソートは、直接挿入ソートと同様に、データを秩序領域と無秩序領域に分けます.異なるのは、直接挿入ソートは、無秩序領域の最初の要素を秩序領域に直接挿入してより大きな秩序領域を形成し、直接選択ソートは、無秩序領域から最小の要素を選択して秩序領域の最後に直接配置します.
簡単なソート例:
ソート対象配列A[0…5]={2,7,6,3,1,5}が与えられたとする
1回目:i=0,無秩序領域A[0…5]ではindex=4,要素最小a[0]とa[4]を交換する.得られたシーケンス:{1,7,6,3,2,5}
2回目:i=1,無秩序領域A[1・・・5]ではindex=4,要素最小a[1]とa[4]が交換される.得られたシーケンス:{1,2,6,3,7,5}
3回目:i=2,無秩序領域A[2・・・5]ではindex=3,要素最小a[2]とa[3]を交換する.得られたシーケンス:{1,2,3,6,7,5}
4回目:i=3,無秩序領域A[3・・・5]ではindex=5,要素最小a[3]とa[5]を交換する.得られたシーケンス:{1,2,3,5,7,6}
5回目:i=4、無秩序領域A[4・・・5]ではindex=5、要素最小a[4]とa[5]が交換される.得られたシーケンス:{1,2,3,5,6,7}
6回目:i=5、無秩序領域A[5......5]では、最後の要素は交換しないでください.配列:{1,2,3,5,6,7}
選択したソート・アルゴリズムに従います.
アルゴリズム複雑度
1時間複雑度O(n^2)
ソートに時間がかかるアクションを選択します:比較+交換位置.時間の複雑さは次のとおりです.
比較回数はキーワードの初期状態に関係なく,総比較回数N=(n−1)+(n−2)+…+1=n*(n−1)/2であり,最も好ましくも最悪の場合もO(n^2)である.
2空間の複雑さ
要素ビットを交換するために一時変数が必要であるため,必要に応じて開く補助空間は入力配列規模とは無関係であるため,空間複雑度はO(1)である.
3安定性
選択ソートは、各位置に現在の要素の最小を選択します.例えば、最初の位置に最小を選択し、残りの要素の中で2番目の要素に2番目の小を選択し、n-1番目の要素まで順に類推します.n番目の要素は選択する必要はありません.最大の要素が1つしか残っていないからです.では、1つの選択では、1つの要素が現在の要素よりも小さく、その小さな要素が現在の要素と等しい要素の後ろに現れると、交換後の安定性が破壊されます.拗ねて、例を挙げると、シーケンス5 8 8 5 2 9は、第1の要素5を選択すると2と交換されることを知っているので、元のシーケンスの2つの5の相対的な前後の順序が破壊されるので、選択ソートは不安定なソートアルゴリズムである.
直接選択ソートは、直接挿入ソートと同様に、データを秩序領域と無秩序領域に分けます.異なるのは、直接挿入ソートは、無秩序領域の最初の要素を秩序領域に直接挿入してより大きな秩序領域を形成し、直接選択ソートは、無秩序領域から最小の要素を選択して秩序領域の最後に直接配置します.
簡単なソート例:
ソート対象配列A[0…5]={2,7,6,3,1,5}が与えられたとする
1回目:i=0,無秩序領域A[0…5]ではindex=4,要素最小a[0]とa[4]を交換する.得られたシーケンス:{1,7,6,3,2,5}
2回目:i=1,無秩序領域A[1・・・5]ではindex=4,要素最小a[1]とa[4]が交換される.得られたシーケンス:{1,2,6,3,7,5}
3回目:i=2,無秩序領域A[2・・・5]ではindex=3,要素最小a[2]とa[3]を交換する.得られたシーケンス:{1,2,3,6,7,5}
4回目:i=3,無秩序領域A[3・・・5]ではindex=5,要素最小a[3]とa[5]を交換する.得られたシーケンス:{1,2,3,5,7,6}
5回目:i=4、無秩序領域A[4・・・5]ではindex=5、要素最小a[4]とa[5]が交換される.得られたシーケンス:{1,2,3,5,6,7}
6回目:i=5、無秩序領域A[5......5]では、最後の要素は交換しないでください.配列:{1,2,3,5,6,7}
選択したソート・アルゴリズムに従います.
public static void selectSort(int [] arr){
int len = arr.length;
for(int i=0;i<len-1;i++){
int min = i;
for(int j = i+1;j<len;j++){
if(arr[j]<arr[min]){
min =j;
}
}
if(min != i){
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}アルゴリズム複雑度
1時間複雑度O(n^2)
ソートに時間がかかるアクションを選択します:比較+交換位置.時間の複雑さは次のとおりです.
比較回数はキーワードの初期状態に関係なく,総比較回数N=(n−1)+(n−2)+…+1=n*(n−1)/2であり,最も好ましくも最悪の場合もO(n^2)である.
2空間の複雑さ
要素ビットを交換するために一時変数が必要であるため,必要に応じて開く補助空間は入力配列規模とは無関係であるため,空間複雑度はO(1)である.
3安定性
選択ソートは、各位置に現在の要素の最小を選択します.例えば、最初の位置に最小を選択し、残りの要素の中で2番目の要素に2番目の小を選択し、n-1番目の要素まで順に類推します.n番目の要素は選択する必要はありません.最大の要素が1つしか残っていないからです.では、1つの選択では、1つの要素が現在の要素よりも小さく、その小さな要素が現在の要素と等しい要素の後ろに現れると、交換後の安定性が破壊されます.拗ねて、例を挙げると、シーケンス5 8 8 5 2 9は、第1の要素5を選択すると2と交換されることを知っているので、元のシーケンスの2つの5の相対的な前後の順序が破壊されるので、選択ソートは不安定なソートアルゴリズムである.