安定性（安定性）
ソート アルゴリズムは安定しています。つまり、キー R と S の 2 つの等しいレコードがあり、元のリストで R が S の前に出現する場合、ソートされたリストでも R が S の前に出現します。
ソートアルゴリズムの分類
一般的なものには、挿入 (挿入ソート/ヒル ソート)、交換 (バブル ソート/クイック ソート)、選択 (選択ソート)、マージ (マージ ソート) などがあります。
1. 挿入ソート
挿入ソート (挿入ソート) は、順序付けされたシーケンスを構築することによって機能します。ソートされていないデータの場合、ソートされたシーケンス内で後ろから前にスキャンして、対応する位置を見つけて挿入します。挿入ソートの実装では、通常、インプレース ソート (つまり、O(1) 個の余分なスペースのみを使用するソート) が使用されます。そのため、後ろから前へのスキャン プロセス中に、繰り返し、徐々にシフトする必要があります。要素を後方にソートし、最新の要素の挿入スペースを提供します。
一般に、挿入ソートはインプレースを使用して配列に実装されます。具体的なアルゴリズムは次のように説明されます。
最初の要素から始めて、要素はソートされていると考えることができます。
次の要素を取得し、ソートされた一連の要素を後ろから前にスキャンします。
(ソートされた) 要素が新しい要素より大きい場合は、要素を次の位置に移動します。
並べ替えられた要素が新しい要素以下になる位置が見つかるまで、手順 3 を繰り返します。
その位置に新しい要素を挿入した後。
手順2～5を繰り返します。
次のようにコードをコピーします。
public static void insertSort(int[] data) {
for (int インデックス = 1; インデックス < data.length; インデックス++) {
int キー = データ[インデックス];
int 位置 = インデックス;
// 大きい値を右にシフト
while (位置 > 0 && データ[位置 - 1] > キー) {
データ[位置] = データ[位置 - 1];
位置 - ;
}
データ[位置] = キー;
}
}
2. 丘の選別
シェル ソートは挿入ソートの一種です。これは、直接挿入ソート アルゴリズムの改良です。この方法は、DL であるため、増分ソートの削減とも呼ばれます。シェルは 1959 年に提案されたことにちなんで名付けられました。
ヒル ソートは、挿入ソートの次の 2 つの特性に基づいて改良された方法を提案します。
挿入ソートは、ほぼソートされたデータを操作する場合に非常に効率的です。つまり、線形ソートの効率を実現できます。
ただし、挿入ソートは一度にデータを 1 ビットしか移動できないため、一般に非効率的です。
次のようにコードをコピーします。
static <E extends Comparable<? super E>> voidshellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, . ..
for (; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
3. バブルソーティング
バブル ソート (バブル ソート、台湾からの翻訳: バブル ソートまたはバブル ソート) は、単純な並べ替えアルゴリズムです。ソート対象のシーケンスを繰り返し調べて、一度に 2 つの要素を比較し、順序が間違っている場合はそれらを交換します。配列を訪問する作業は、それ以上の交換が必要なくなるまで繰り返されます。これは、配列がソートされたことを意味します。このアルゴリズムの名前は、小さい要素がスワッピングによって配列の先頭にゆっくりと「浮動」するという事実に由来しています。
バブル ソート アルゴリズムは次のように機能します。
隣接する要素を比較し、最初の要素が 2 番目の要素より大きい場合は、両方を交換します。
隣接する要素の各ペアに対して同じことを行い、最初のペアから始めて最後のペアで終了します。この時点で、最後の要素が最大の数値になります。
最後の要素を除くすべての要素に対して上記の手順を繰り返します。
比較する数値のペアがなくなるまで、要素の数を減らしながら上記の手順を繰り返します。
次のようにコードをコピーします。
public static void bubbleSort(int[] data) {
int temp = 0;
for (int i = data.length - 1; i > 0; --i) {
ブール値 isSort = false;
for (int j = 0; j < i; ++j) {
if (データ[j + 1] < データ[j]) {
temp = データ[j];
データ[j] = データ[j + 1];
データ[j + 1] = 温度;
isSort = true;
}
}
// 内部ループで交換が発生した場合は比較を続行します。内部ループで交換が発生しなかった場合は、ソートされたとみなされます。
if (!isSort)
壊す;
}
}
4. クイックソート
クイックソートはバブルソートを改良したものです。 1962 年に CAR Hoare によって提案されました。その基本的な考え方は、1 回の並べ替えで並べ替えるデータを 2 つの独立した部分に分割し、一方の部分のすべてのデータがもう一方の部分のすべてのデータよりも小さくなり、この方法を使用してデータの 2 つの部分をすばやく分離することです。並べ替えでは、並べ替えプロセス全体を再帰的に実行できるため、データ全体が順序付けされたシーケンスになります。
クイック ソートでは、分割統治戦略を使用してリストを 2 つのサブリストに分割します。
手順は次のとおりです。
シーケンスから要素を取り出すことを「ピボット」と呼びます。
基底値より小さいすべての要素が基底の前に配置され、基底値より大きいすべての要素が基底の後ろに配置されるように、配列の順序を変更します (同じ数値をどちらの側にも配置できます)。このパーティションが終了すると、塩基はシーケンスの途中になります。これをパーティション操作と呼びます。
基本値より小さい要素の部分配列と基本値より大きい要素の部分配列を再帰的に並べ替えます。
次のようにコードをコピーします。
/*
* クイックソートをより効率的に実装します。<br />
* ピボットには左、中央、右の中央値 (@#median() を参照) を使用し、
* アルゴリズムのコアのより効率的な内部ループ。
*/
パブリック クラス クイックソート {
パブリック静的最終整数 CUTOFF = 11;
/**
* クイックソートアルゴリズム<br />
*
* @param arr 比較可能な項目の配列<br />
*/
public static <T extends Comparable<? super T>> void Quicksort(T[] arr) {
クイックソート(arr, 0, arr.length - 1);
}
/**
* 左、中央、右の中央値を取得します。<br />
* これらを並べて、ピボットを配列の最後に配置して非表示にします。<br />
*
* @param arr 比較可能な項目の配列<br />
* @param は部分配列の一番左のインデックスを残しました。<br />
* @param right 部分配列の右端のインデックス。<br />
* @return T
*/
public static <T extends Comparable<? super T>> T median(T[] arr, int left, int right) {
int センター = (左 + 右) / 2;
if (arr[left].compareTo(arr[center]) > 0)
swapRef(arr, left, center);
if (arr[左].compareTo(arr[右]) > 0)
swapRef(arr, left, right);
if (arr[center].compareTo(arr[right]) > 0)
swapRef(arr, center, right);
swapRef(arr, center, right - 1);
arr[right - 1]を返します;
}
/**
* クイックソートアルゴリズムで配列をソートする内部メソッド<br />
*
* @param は比較可能なアイテムの配列を配列します。<br />
* @param は部分配列の左端のインデックスを残しました。<br />
* @param right サブ配列の右端のインデックス<br />
*/
private static <T extends Comparable<? super T>> void QuickSort(T[] arr, int left, int right) {
if (左 + カットオフ <= 右) {
// ピボットを見つける
T pivot = median(arr, left, right);
// パーティショニングを開始する
int i = 左、j = 右 - 1;
のために （;;） {
while (arr[++i].compareTo(pivot) < 0);
while (arr[--j].compareTo(pivot) > 0);
if (i < j)
swapRef(arr, i, j);
それ以外
壊す;
}
// ピボット参照を小さなコレクションに戻します。
swapRef(arr, i, right - 1);
QuickSort(arr, left, i - 1); // 小さなコレクションを並べ替えます。
QuickSort(arr, i + 1, right); // 大きなコレクションを並べ替えます。
} それ以外 {
// 合計数が CUTOFF 未満の場合は、挿入ソートを使用します
// 代わりに (はるかに効率的になるため)。
並べ替え(arr、挿入左、右);
}
}
/**
* 配列内の参照を交換するメソッド。<br />
*
* @param はオブジェクトの配列です。<br />
* @param idx1 は最初の要素のインデックスです。<br />
* @param idx2 2 番目の要素のインデックス<br />
*/
public static <T> void swapRef(T[] arr, int idx1, int idx2) {
T tmp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = tmp;
}
/**
* 挿入ソートで部分配列を最初から最後までソートするメソッド
*アルゴリズム<br />
*
* @param arr 比較可能な項目の配列<br />
* @param は開始位置を開始します。<br />
* @param end 終了位置<br /> です。
*/
public static <T extends Comparable<? super T>> void insertSort(T[] arr, int start, int end) {
int i;
for (int j = start + 1; j <= end; j++) {
T tmp = arr[j];
for (i = j; i > start && tmp.compareTo(arr[i - 1]) < 0; i--) {
arr[i] = arr[i - 1];
}
arr[i] = tmp;
}
}
private static void printArray(Integer[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main(String[] args) {
整数[] データ = {10, 4, 9, 23, 1, 45, 27, 5, 2};
System.out.println("バブルソート...");
printArray(データ);
クイックソート(データ);
printArray(データ);
}
}
5. 選択の並べ替え
選択ソートは、シンプルで直感的なソート アルゴリズムです。仕組みは次のとおりです。まず、ソートされていないシーケンス内で最小の (大きい) 要素を見つけて、ソートされたシーケンスの先頭に格納します。次に、ソートされていない残りの要素から最小の (大きい) 要素を見つけて、それをソートされたシーケンスの最後に置きます。ソートされたシーケンス。すべての要素がソートされるまで続きます。
要素を決定する各プロセスには、最小値を選択するサブプロセスがあるため、人々はそれを明確に選択ソートと呼んでいます。
たとえば、シーケンス 5 8 5 2 9 では、最初のパスで最初の要素 5 が 2 と交換されることがわかっており、その後、元のシーケンス内の 2 つの 5 の相対的な順序が破壊されるため、選択ソートは次のようになります。ソートアルゴリズムが安定していません。
次のようにコードをコピーします。
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; //順序付けされていない領域の最小データ配列インデックス
for (int j = i + 1; j < data.length; j++) { // 順序付けされていない領域で最小のデータを見つけて、その配列の添字を保存します
if (データ[j] < データ[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // 非順序付け領域の最小位置がデフォルトの先頭データでない場合は交換する。
一時 = データ[i];
データ[i] = データ[minIndex];
データ[minIndex] = 温度;
}
}
}
6. マージソート
マージ ソートは、マージ操作に基づく効果的な並べ替えアルゴリズムです。このアルゴリズムは、分割統治法 (Divide and Conquer) を使用する非常に典型的なアプリケーションです。
マージ操作のプロセスは次のとおりです。
サイズが 2 つのソートされたシーケンスの合計になるようにスペースを適用します。このスペースは、マージされたシーケンスを格納するために使用されます。
2 つのポインターを設定します。初期位置は、ソートされた 2 つのシーケンスの開始位置です。
2 つのポインターが指す要素を比較し、比較的小さい要素を選択してマージ スペースに配置し、ポインターを次の位置に移動します。
ポインタがシーケンスの最後に到達するまで手順 3 を繰り返します。
他のシーケンスの残りの要素をすべて、マージされたシーケンスの最後に直接コピーします。
次のようにコードをコピーします。
public static int[] mergeSort(int[] arr) {//マージソート -- 再帰
if (配列の長さ == 1) {
arrを返します。
}
int 半分 = arr.length / 2;
int[] arr1 = 新しい int[half];
int[] arr2 = 新しい int[arr.length -half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr,half,arr2,0,arr2.length);
arr1 = マージソート(arr1);
arr2 = マージソート(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//マージ ソート サブルーチン
int[] 結果 = 新しい int[arr1.length + arr2.length];
int i = 0;
int j = 0;
int k = 0;
while (true) {
if (arr1[i] < arr2[j]) {
結果[k] = arr1[i];
if (++i > arr1.length - 1) {
壊す;
}
} それ以外 {
結果[k] = arr2[j];
if (++j > arr2.length - 1) {
壊す;
}
}
k++;
}
for (; i < arr1.length; i++) {
結果[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
結果[++k] = arr2[j];
}
結果を返します。
}
完全なコード (QuickSort を除く)
次のようにコードをコピーします。
パッケージ com.clzhang.sample. Thinking;
java.util.* をインポートします。
/**
* いくつかの一般的な並べ替えアルゴリズムの Java 実装
* @著者エイサー
*
*/
パブリック クラス CommonSort {
/**
※挿入ソートの具体的なアルゴリズムは以下の通りです。
* 1. 最初の要素から開始して、要素はソートされているとみなすことができます
* 2. 次の要素を取り出し、ソートされた要素シーケンスを後ろから前にスキャンします。
* 3. ソートされた要素が新しい要素より大きい場合、要素を次の位置に移動します
* 4. 並べ替えられた要素が新しい要素以下になる位置が見つかるまで、手順 3 を繰り返します。
* 5. この位置に新しい要素を挿入した後
* 6. 手順2～5を繰り返します。
*/
public static void insertSort(int[] data) {
for (int インデックス = 1; インデックス < data.length; インデックス++) {
int キー = データ[インデックス];
int 位置 = インデックス;
// 大きい値を右にシフト
while (位置 > 0 && データ[位置 - 1] > キー) {
データ[位置] = データ[位置 - 1];
位置 - ;
}
データ[位置] = キー;
}
}
/**
* ヒルソート。多数のソート操作に適したアルゴリズムの実装アイデアについては、Wikipedia を参照してください。
*/
static <E extends Comparable<? super E>> voidshellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) h = h*3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, . ..
for (; h >= 1; h /= 3)
for (int i = h; i < a.size(); i++)
for (int j = i; j >= h && a.get(j).compareTo(a.get(jh)) < 0; j-=h)
Collections.swap(a, j, jh);
}
/**
※バブルソートアルゴリズムの動作は以下の通りです。
* 1. 隣接する要素を比較します。最初のものが 2 番目のものより大きい場合は、両方を交換します。
* 2. 隣接する要素の各ペアに対して、最初の最初のペアから最後の最後のペアまで同じ作業を実行します。この時点では、最後の要素が最大の数値である必要があります。
* 3. 最後の要素を除くすべての要素に対して上記の手順を繰り返します。
* 4. 比較する数値のペアがなくなるまで、要素の数を減らしながら上記の手順を繰り返します。 [1]
*/
public static void bubbleSort(int[] data) {
int temp = 0;
for (int i = data.length - 1; i > 0; --i) {
ブール値 isSort = false;
for (int j = 0; j < i; ++j) {
if (データ[j + 1] < データ[j]) {
temp = データ[j];
データ[j] = データ[j + 1];
データ[j + 1] = 温度;
isSort = true;
}
}
// 内部ループで交換が発生した場合は比較を続行します。内部ループで交換が発生しなかった場合は、ソートされたとみなされます。
if (!isSort)
壊す;
}
}
/**
* 選択ソートの基本的な考え方は次のとおりです。
* 1. 配列を走査するプロセス中に、i がソートする必要がある現在のシーケンス番号を表す場合、残りの [i+1...n-1] の中から最小値を見つける必要があります。
* 2.次に、求めた最小値を i が指す値と交換します。
* 要素を決定する各プロセスには、最小値を選択するサブプロセスがあるため、人々はそれを明確に選択ソートと呼んでいます。
* @paramデータ
*/
public static void selectSort(int[] data) {
int minIndex = 0;
int temp = 0;
for (int i = 0; i < data.length; i++) {
minIndex = i; //順序付けされていない領域の最小データ配列インデックス
for (int j = i + 1; j < data.length; j++) { // 順序付けされていない領域で最小のデータを見つけて、その配列の添字を保存します
if (データ[j] < データ[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) { // 非順序付け領域の最小位置がデフォルトの先頭データでない場合は交換する。
一時 = データ[i];
データ[i] = データ[minIndex];
データ[minIndex] = 温度;
}
}
}
/**
※マージ操作の流れは以下の通りです。
* 1. ソートされた 2 つのシーケンスの合計のサイズになるようにスペースを適用します。このスペースは、マージされたシーケンスを格納するために使用されます。
* 2. 2 つのポインターを設定します。初期位置は、ソートされた 2 つのシーケンスの開始位置です。
* 3. 2つのポインタが指す要素を比較し、比較的小さい要素を選択してマージスペースに配置し、ポインタを次の位置に移動します
* 4. ポインタがシーケンスの最後に到達するまで手順 3 を繰り返します。
* 5. 他のシーケンスの残りの要素をすべて、マージされたシーケンスの最後に直接コピーします。
*/
public static int[] mergeSort(int[] arr) {//マージソート -- 再帰
if (配列の長さ == 1) {
arrを返します。
}
int 半分 = arr.length / 2;
int[] arr1 = 新しい int[half];
int[] arr2 = 新しい int[arr.length -half];
System.arraycopy(arr, 0, arr1, 0, arr1.length);
System.arraycopy(arr,half,arr2,0,arr2.length);
arr1 = マージソート(arr1);
arr2 = マージソート(arr2);
return mergeSortSub(arr1, arr2);
}
private static int[] mergeSortSub(int[] arr1, int[] arr2) {//マージ ソート サブルーチン
int[] 結果 = 新しい int[arr1.length + arr2.length];
int i = 0;
int j = 0;
int k = 0;
while (true) {
if (arr1[i] < arr2[j]) {
結果[k] = arr1[i];
if (++i > arr1.length - 1) {
壊す;
}
} それ以外 {
結果[k] = arr2[j];
if (++j > arr2.length - 1) {
壊す;
}
}
k++;
}
for (; i < arr1.length; i++) {
結果[++k] = arr1[i];
}
for (; j < arr2.length; j++) {
結果[++k] = arr2[j];
}
結果を返します。
}
private static void printArray(int[] c) {
for (int i = 0; i < c.length; i++)
System.out.print(c[i] + ",");
System.out.println();
}
public static void main(String []args){
int[] データ = {10,4,9,23,1,45,27,5,2};
System.out.println("バブルソート...");
int[] a = data.clone();
printArray(a);
バブルソート(a);
printArray(a);
System.out.println("selectSort...");
int[] b = data.clone();
printArray(b);
選択ソート(b);
printArray(b);
System.out.println("insertionSort...");
int[] c = data.clone();
printArray(c);
挿入ソート(c);
printArray(c);
System.out.println("shellSort...");
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<data.length;i++)
list.add(データ[i]);
System.out.println(リスト);
シェルソート(リスト);
System.out.println(リスト);
System.out.println("mergeSort...");
int[] d = data.clone();
printArray(d);
printArray(mergeSort(d));
}
}