ソートアルゴリズムは、データ構造とアルゴリズムで最も基本的なアルゴリズムの1つです。
ソートアルゴリズムは内部ソートと外部ソートに分類できます。
内部ソートとは、データレコードがメモリ内でソートされることです。
一方、外部ソートは、ソートするデータが非常に大きく、一度にすべてのソートレコードを保持できないため、ソート処理中に外部メモリにアクセスする必要があるためです。
一般的な内部ソートアルゴリズムは以下の通りです：
挿入ソート、ヒルソート、選択ソート、バブルソート、正規化ソート、クイックソート、ヒープソート、ベースソートなど。
1つのグラフにまとめました。
- 時間の複雑さについて：
正方形順） ソート 様々な種類の単純ソート：直接挿入、直接選択、バブルソート。
線形対数順）ソート クイックソート、ヒープソート、マージソート；
O(n1+§))ソートで、§は0から1の間の定数です。 ヒルのソート
線形順序 ) ソート ベースソート、バケットソート、ボックスソート。
- 安定性について
安定したソートアルゴリズム：バブルソート、挿入ソート、サブサンプションソート、ベースソート。
安定しないソートアルゴリズム：セレクションソート、クイックソート、ヒルソート、ヒープソート。
バブルソート
アルゴリズムのステップ
隣り合う要素を比較します。1つ目が2つ目より大きければ、両方を入れ替えます。
最初のペアから最後のペアまで、隣り合う要素の各ペアについて同じことを行います。このステップの後、最後の要素が最大の数になります。
最後の要素を除くすべての要素について、上記の手順を繰り返します。
一度に比較する数字のペアがなくなるまで、より少ない要素について上記の手順を繰り返します。
// Java コード実装
2public class BubbleSort implements IArraySort {
3
4 @Override
5 public int[] sort(int[] sourceArray) throws Exception {
6 // パラメータの内容を変更せずにarrをコピーする
7 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
8
9 for (int i = 1; i < arr.length; i++) {
10 // もしtrueなら、このループでスワップが行われていないこと、つまりソートされるシーケンスがすでに順序付けされていて、ソートが完了していることを示すフラグを設定する。
11 boolean flag = true;
12
13 for (int j = 0; j < arr.length - i; j++) {
14 if (arr[j] > arr[j + 1]) {
15 int tmp = arr[j];
16 arr[j] = arr[j + 1];
17 arr[j + 1] = tmp;
18
19 flag = false;
20 }
21 }
22
23 if (flag) {
24 break;
25 }
26 }
27 return arr;
28 }
29}
選択ソート
アルゴリズムのステップ
まず、ソートされていないシーケンスで最小の要素を見つけ、それをソートされたシーケンスの先頭に格納します。
次に、ソートされていない残りの要素から最小の要素を見つけ、ソートされたシーケンスの最後に配置します。
すべての要素がソートされるまで、ステップ2を繰り返します。
//Java コード実装
2public class SelectionSort implements IArraySort {
3
4 @Override
5 public int[] sort(int[] sourceArray) throws Exception {
6 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
7
8 // 合計N-1ラウンドの比較
9 for (int i = 0; i < arr.length - 1; i++) {
10 int min = i;
11
12 // 1ラウンドに必要な比較の数 N-i
13 for (int j = i + 1; j < arr.length; j++) {
14 if (arr[j] < arr[min]) {
15 // 要素の現在の最小値を記録する 添え字を見つけることができる
16 min = j;
17 }
18 }
19
20 // 見つかった最小の値とiの位置の値を入れ替える
21 if (i != min) {
22 int tmp = arr[i];
23 arr[i] = arr[min];
24 arr[min] = tmp;
25 }
26
27 }
28 return arr;
29 }
30}
挿入ソート
アルゴリズムのステップ
ソートされる最初のシーケンスの最初の要素を順序付きシーケンスとみなし、2番目から最後の要素をソートされていないシーケンスとして扱います。
ソートされていないシーケンスを最初から最後まで順次スキャンし、スキャンされた各要素を順序付きシーケンスの適切な位置に挿入します。
//Java コード実装
2public class InsertSort implements IArraySort {
3
4 @Override
5 public int[] sort(int[] sourceArray) throws Exception {
6 // パラメータの内容を変更せずにarrをコピーする
7 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
8
9 // 添え字が1の要素から始めて、挿入する適切な位置を選択する。添え字が0の要素は1つだけなので、デフォルトは順序付けされている
10 for (int i = 1; i < arr.length; i++) {
11
12 // 挿入するデータを記録する
13 int tmp = arr[i];
14
15 // すでにソートされた配列の右端から始めて、比較してそれより小さい数を見つける
16 int j = i;
17 while (j > 0 && tmp < arr[j - 1]) {
18 arr[j] = arr[j - 1];
19 j--;
20 }
21
22 // それより小さい数の存在、挿入する
23 if (j != i) {
24 arr[j] = tmp;
25 }
26
27 }
28 return arr;
29 }
30}
ヒルソート
アルゴリズムのステップ
インクリメンタルシーケンスt1、t2、......、tkを選択し、ここでti > tj、tk = 1；
シーケンスkをインクリメンタルシーケンスの数kでソートします；
各ソートでは、対応するインクリメントti に従って、ソートされるシーケンスが長さmのいくつかのサブシーケンスに分割され、それぞれのサブテーブルに対して直接挿入ソートが実行されます。インクリメントファクターが1の場合のみ、シーケンス全体がテーブルとして扱われ、テーブルの長さはシーケンス全体の長さとなります。
//Java コード実装
2public class ShellSort implements IArraySort {
3
4 @Override
5 public int[] sort(int[] sourceArray) throws Exception {
6 // パラメータの内容を変更せずにarrをコピーする
7 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
8
9 int gap = 1;
10 while (gap < arr.length) {
11 gap = gap * 3 + 1;
12 }
13
14 while (gap > 0) {
15 for (int i = gap; i < arr.length; i++) {
16 int tmp = arr[i];
17 int j = i - gap;
18 while (j >= 0 && arr[j] > tmp) {
19 arr[j + gap] = arr[j];
20 j -= gap;
21 }
22 arr[j + gap] = tmp;
23 }
24 gap = (int) Math.floor(gap / 3);
25 }
26
27 return arr;
28 }
29}
ソート
アルゴリズムのステップ
すでにソートされた2つのシーケンスの合計サイズになるようにスペースを要求し、このスペースはマージされたシーケンスを格納するために使用されます；
すでにソートされた2つの配列のそれぞれの開始位置を初期位置とする2つのポインタを設定します；
2つのポインタが指す要素を比較し、比較的小さい要素を選んでマージスペースに入れ、ポインタを次の位置に移動します；
ポインタがシーケンスの最後に達するまで、ステップ3を繰り返します；
もう一方のシーケンスの残りのすべての要素を、マージされたシーケンスの最後に直接コピーします。
//Java コード実装
public class MergeSort implements IArraySort {
2
3 @Override
4 public int[] sort(int[] sourceArray) throws Exception {
5 // パラメータの内容を変更せずにarrをコピーする
6 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
7
8 if (arr.length < 2) {
9 return arr;
10 }
11 int middle = (int) Math.floor(arr.length / 2);
12
13 int[] left = Arrays.copyOfRange(arr, 0, middle);
14 int[] right = Arrays.copyOfRange(arr, middle, arr.length);
15
16 return merge(sort(left), sort(right));
17 }
18
19 protected int[] merge(int[] left, int[] right) {
20 int[] result = new int[left.length + right.length];
21 int i = 0;
22 while (left.length > 0 && right.length > 0) {
23 if (left[0] <= right[0]) {
24 result[i++] = left[0];
25 left = Arrays.copyOfRange(left, 1, left.length);
26 } else {
27 result[i++] = right[0];
28 right = Arrays.copyOfRange(right, 1, right.length);
29 }
30 }
31
32 while (left.length > 0) {
33 result[i++] = left[0];
34 left = Arrays.copyOfRange(left, 1, left.length);
35 }
36
37 while (right.length > 0) {
38 result[i++] = right[0];
39 right = Arrays.copyOfRange(right, 1, right.length);
40 }
41
42 return result;
43 }
44
45}
高速ソート
アルゴリズムのステップ
ベンチマーク」と呼ばれる配列から要素を選びます。
ベンチマーク値より小さい要素はすべてベンチマークの前に、ベンチマーク値より大きい要素はすべてベンチマークの後ろに配置されるように、配列を並べ替えます。このパーティショニングが終了すると、ベンチマークは配列の中央に位置します。これをパーティショニング操作と呼びます；
基準値より小さい要素の部分配列と、基準値より大きい要素の部分配列を再帰的にソートします；
//Java コード実装
2public class QuickSort implements IArraySort {
3
4 @Override
5 public int[] sort(int[] sourceArray) throws Exception {
6 // パラメータの内容を変更せずにarrをコピーする
7 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
8
9 return quickSort(arr, 0, arr.length - 1);
10 }
11
12 private int[] quickSort(int[] arr, int left, int right) {
13 if (left < right) {
14 int partitionIndex = partition(arr, left, right);
15 quickSort(arr, left, partitionIndex - 1);
16 quickSort(arr, partitionIndex + 1, right);
17 }
18 return arr;
19 }
20
21 private int partition(int[] arr, int left, int right) {
22 // 基準値を設定する
23 int pivot = left;
24 int index = pivot + 1;
25 for (int i = index; i <= right; i++) {
26 if (arr[i] < arr[pivot]) {
27 swap(arr, i, index);
28 index++;
29 }
30 }
31 swap(arr, pivot, index - 1);
32 return index - 1;
33 }
34
35 private void swap(int[] arr, int i, int j) {
36 int temp = arr[i];
37 arr[i] = arr[j];
38 arr[j] = temp;
39 }
40
41}
- すべての優秀なプログラマーが学ぶべき、GitHub上のオープンソースのデータ構造とアルゴリズムプロジェクト
- データ構造とアルゴリズムの美しさ: データ構造とアルゴリズムを体系的かつ効率的に学ぶための要点のつかみ方
- 古典的ソートアルゴリズム トップ10 アニメーションと解説, Watch Me Enough！
