単純ソートたんじゅん:バブルソート、選択ソート、挿入ソートバブルソート

5003 ワード

二分法は秩序配列で行う必要があると述べたが,配列並べ替えの3つの簡単な方法を見てみよう.
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つの文字列が他の文字列の一部と完全に同じである場合、長い文字列の多い文字の数だけを計算します.
以上は,配列ソートで遭遇する簡単なソート方法である.配列は,データ数が増えると検索,並べ替え,削除などの面で効率が悪く,データが確立されると勝手にサイズを変更できないためである.配列に加えて、他のデータ構造もあり、より柔軟で実用的です.