単純ソートたんじゅん:バブルソート、選択ソート、挿入ソートバブルソート
5003 ワード
二分法は秩序配列で行う必要があると述べたが,配列並べ替えの3つの簡単な方法を見てみよう.
1バブルソート
泡のソートはこれが最も簡単で、最も直接的なソート方法でもあります.通常、データが少ない場合にも使用できますが、データが多い場合はバブルソート効率が低くなります.バブルソートの構想は,隣接比較のたびに最大数を配列末端(昇順)に置くことである.コードを直接見る:
バブルプログラムは主に内外の2層サイクルで実現され,比較により,前の数が後の数より大きい場合に交換される.
2ソートの選択
選択ソートはバブルソートに基づいて改良され,交換回数は減少したが,比較回数は同様であった.しかし、この結果は、スワップがメモリで頻繁に使用されるため、メモリ操作が減少するため、意味があります.
≪ソートの選択|Select Sort|emdw≫:ソートされるデータ要素の中から最小の要素を選択するたびに、ソートされるデータ要素がすべてソートされるまで、シーケンスの開始位置に格納されます.
上のコードは2層のループで、外層のループはデータ交換を制御して、内層のループはデータが1つの最小の数を見つけて更に外層のデータと交換することを制御します.これにより、選択ソートが実現される.
3ソートの挿入
挿入ソートは、ほとんどの場合に使用されるものであり、効率的なものでもあります.通常、泡のソートよりも2倍速く、選択したソートよりも速くなります.複雑ではありません.通常、複雑なソートアルゴリズムの最終段階で使用されます.
挿入ソートを理解するには、まずローカル秩序を理解します.ローカル秩序とは、配列タグデータの前に秩序化され、順序付けされていることを意味します.これがローカル秩序です.このマークの隊員を動かすと挿入ソートが実現されます.タグ付けされた配列メンバーは、左シフトで秩序化された局所配列に挿入され、局所秩序化された配列の一部の配列メンバーは、以下のdemoコードを参照して後方シフトされます.
以上のプログラムの注釈は,挿入ソートの実装過程を説明した.挿入ソートは変形せず、毎回ローカル秩序で、全体秩序まで維持されます.
3つの単純なソートの効率比較:
発泡ソート比較回数はN*(N−1)/2交換回数がN二乗に比例した.
選択ソート:交換回数O(N)という点は発泡に基づいて改善されたが,比較回数はO(N*N)であった.
挿入ソート:運転時間O(N)であり、一般的に挿入ソートは泡ソートよりも効率が高く、選択ソートよりも優れている.
JAvaオブジェクトのソート
ソートは純粋な数字だけでなく、文字列などをソートする必要がある場合があります.例えば、人名をソートすることは、単語をソートすることである可能性があります.単語のソートはjava compareTo()メソッドを使用します.
文字辞書の順序を比較した結果、数値が返されます.s1
出力結果:-132 3-1.最初の違いは辞書の減算を計算します.2つの文字列が他の文字列の一部と完全に同じである場合、長い文字列の多い文字の数だけを計算します.
以上は,配列ソートで遭遇する簡単なソート方法である.配列は,データ数が増えると検索,並べ替え,削除などの面で効率が悪く,データが確立されると勝手にサイズを変更できないためである.配列に加えて、他のデータ構造もあり、より柔軟で実用的です.
1バブルソート
泡のソートはこれが最も簡単で、最も直接的なソート方法でもあります.通常、データが少ない場合にも使用できますが、データが多い場合はバブルソート効率が低くなります.バブルソートの構想は,隣接比較のたびに最大数を配列末端(昇順)に置くことである.コードを直接見る:
public void bubbleSort()
{
int out, in;
for(out=nElems-1; out>1; out--)
for(in=0; inif( a[in] > a[in+1] )
swap(in, in+1);
}
private void swap(int one, int two)
{
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
バブルプログラムは主に内外の2層サイクルで実現され,比較により,前の数が後の数より大きい場合に交換される.
2ソートの選択
選択ソートはバブルソートに基づいて改良され,交換回数は減少したが,比較回数は同様であった.しかし、この結果は、スワップがメモリで頻繁に使用されるため、メモリ操作が減少するため、意味があります.
≪ソートの選択|Select Sort|emdw≫:ソートされるデータ要素の中から最小の要素を選択するたびに、ソートされるデータ要素がすべてソートされるまで、シーケンスの開始位置に格納されます.
void sort(int list[], int n)
{
int i, j, min, temp;
for (i = 0; i 1 ; i++){
min = i;
for (j = i + 1; j 1; j++)
if (list[j] < list[min])
min = j;
SWAP(list[i], list[min]);
}
}
上のコードは2層のループで、外層のループはデータ交換を制御して、内層のループはデータが1つの最小の数を見つけて更に外層のデータと交換することを制御します.これにより、選択ソートが実現される.
3ソートの挿入
挿入ソートは、ほとんどの場合に使用されるものであり、効率的なものでもあります.通常、泡のソートよりも2倍速く、選択したソートよりも速くなります.複雑ではありません.通常、複雑なソートアルゴリズムの最終段階で使用されます.
挿入ソートを理解するには、まずローカル秩序を理解します.ローカル秩序とは、配列タグデータの前に秩序化され、順序付けされていることを意味します.これがローカル秩序です.このマークの隊員を動かすと挿入ソートが実現されます.タグ付けされた配列メンバーは、左シフトで秩序化された局所配列に挿入され、局所秩序化された配列の一部の配列メンバーは、以下のdemoコードを参照して後方シフトされます.
public void insertSort()
{
int in,out;//
for(out=1;outout++)
{
int temp=a[out];// ( )
in=out;
while(in>0 && (a[in-1]>=temp))// ,
{
a[in]=a[in-1];
--in;
}//
a[in]=temp;//
}
}
以上のプログラムの注釈は,挿入ソートの実装過程を説明した.挿入ソートは変形せず、毎回ローカル秩序で、全体秩序まで維持されます.
3つの単純なソートの効率比較:
発泡ソート比較回数はN*(N−1)/2交換回数がN二乗に比例した.
選択ソート:交換回数O(N)という点は発泡に基づいて改善されたが,比較回数はO(N*N)であった.
挿入ソート:運転時間O(N)であり、一般的に挿入ソートは泡ソートよりも効率が高く、選択ソートよりも優れている.
JAvaオブジェクトのソート
ソートは純粋な数字だけでなく、文字列などをソートする必要がある場合があります.例えば、人名をソートすることは、単語をソートすることである可能性があります.単語のソートはjava compareTo()メソッドを使用します.
String s1,s2;
s1.compareTo(s2);
文字辞書の順序を比較した結果、数値が返されます.s1
String s1 = "abcd";
String s2 = "abce";
String s3 = "Abc";
String s4 = "abcdefg";
System.out.println(s1.compareTo(s2));
System.out.println(s1.compareTo(s3));
System.out.println(s4.compareTo(s1));
System.out.println(s4.compareTo(s2));
出力結果:-132 3-1.最初の違いは辞書の減算を計算します.2つの文字列が他の文字列の一部と完全に同じである場合、長い文字列の多い文字の数だけを計算します.
以上は,配列ソートで遭遇する簡単なソート方法である.配列は,データ数が増えると検索,並べ替え,削除などの面で効率が悪く,データが確立されると勝手にサイズを変更できないためである.配列に加えて、他のデータ構造もあり、より柔軟で実用的です.