ソート方式是、挿入ソート、選択ソート、交換ソート、マージソート、分配ソートに分類されます。

挿入ソート

直接挿入ソート

動作フロー： コード実装：

public class SortAlgorithm {
    public static void insertionSort(int[] data) {
        for (int idx = 1; idx < data.length; idx++) {
            int key = data[idx];
            int prev = idx - 1;
            while (prev >= 0 && data[prev] > key) {
                data[prev + 1] = data[prev];
                prev--;
            }
            data[prev + 1] = key;
        }
    }
}

特性：データの順序性が高いほど効果的です。 適用シーン：データ規模が小さい場合、または既にほぼ整列されている場合に非常に効率的です。

シェルソート

動作フロー： コード実装：

public class SortAlgorithm {
    public static void shellSort(int[] data) {
        int length = data.length;
        for (int gap = length / 2; gap >= 1; gap /= 2) {
            for (int idx = gap; idx < length; idx++) {
                int pos = idx;
                int temp = data[pos];
                if (temp < data[pos - gap]) {
                    data[pos] = data[pos - gap];
                    pos -= gap;
                }
                data[pos] = temp;
            }
        }
    }
}

交換ソート

バブルソート

コード実装：

public class SortAlgorithm {
    public static void bubbleSort(int[] data) {
        int size = data.length;
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - 1 - i; j++) {
                if (data[j] > data[j + 1]) {
                    int tmp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = tmp;
                }
            }
        }
    }
}

クイックソート（双方向ポインタ方式）

動作フロー：8 コード実装：

public class SortAlgorithm {
    public static void quickSort(int[] data, int start, int end) {
        if (start > end) return;
        int pivot = data[start];
        int left = start;
        int right = end;
        while (left < right) {
            while (data[right] >= pivot && left < right) {
                right--;
            }
            while (data[left] <= pivot && left < right) {
                left++;
            }
            if (left < right) {
                int temp = data[right];
                data[right] = data[left];
                data[left] = temp;
            }
        }
        data[start] = data[left];
        data[left] = pivot;
        quickSort(data, start, left - 1);
        quickSort(data, left + 1, end);
    }
}

選択ソート

直接選択ソート

動作フロー： コード実装：

public class SortAlgorithm {
    public static void selectionSort(int[] data) {
        int length = data.length;
        for (int i = 0; i < length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < length; j++) {
                if (data[j] < data[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                int swap = data[i];
                data[i] = data[minIndex];
                data[minIndex] = swap;
            }
        }
    }
}

時間計算量：O(n²) 空間計算量：O(1)

ヒープソート（最大ヒープ、最小ヒープ）

完全二分木の構造を使用して一次元配列を維持する方法

最大ヒープの構築： ヒープソート（最大値を葉节点と交換して最大要素を削除）： コード実装：

public class SortAlgorithm {
    public static void heapSort(int[] data) {
        int length = data.length;
        for (int i = (length - 1) / 2; i >= 0; i--) {
            buildHeap(data, i, length);
        }
        for (int i = length - 1; i > 0; i--) {
            int tmp = data[i];
            data[i] = data[0];
            data[0] = tmp;
            buildHeap(data, 0, i);
        }
    }

    private static void buildHeap(int[] data, int parent, int size) {
        int parentValue = data[parent];
        int child = 2 * parent + 1;
        while (child < size) {
            int rightChild = child + 1;
            if (rightChild < size && data[child] < data[rightChild]) {
                child++;
            }
            if (parentValue > data[child]) {
                break;
            }
            data[parent] = data[child];
            parent = child;
            child = 2 * child + 1;
        }
        data[parent] = parentValue;
    }
}

マージソート

分割後にマージ（单个有序序列に分割してから、逐步的にマージして完全有序序列を形成）

動作フロー：

アルゴリズム	最良	平均	最悪	空間計算量	安定性
マージソート	O(n log n)	O(n log n)	O(n log n)	O(n)	安定

分配ソート

ビンソート（バケットソート）

動作フロー：

基数ソート（分配と収集）

(1) 以下のデータ序列を想定します： 73 22 93 43 55 14 28 65 39 81 まず各桁の値に基づいて、遍历中にデータをそれぞれ编号0から9のビンに配置します（桁の値とビン番号が一対一対応）。 配置結果（論理的な想像）は下图のようになります： 配置结束后。接下来バインのデータはバイン番号が小さい顺に（バイン内データは上部から下部へ）再度收集して連結し、以下のように順序付けられていないデータ序列を取得します： 81 22 73 93 43 14 55 65 28 39 次に、十の位の値に基づいて再度配置を行います（原理は上記と同じ）。配置結果（論理的な想像）は下图のようになります： 配置结束后。接下来全てのバイン内のデータを再度收集して連結し、以下のデータ序列を取得します： 14 22 28 39 43 55 65 73 81 93 内部ソート方式の比較 ---------

時間計算量 (1) 直接挿入、直接選択、バブルソートアルゴリズムの時間計算量はO(n²) (2) クイック、マージ、ヒープソートアルゴリズムの時間計算量はO(n log₂n) (3) シェルソートアルゴリズムの時間計算量は不容易計算：O(n log₂n)またはO(n^1.25) (4) 基数ソートアルゴリズムの時間計算量はO(d × (rd+n))で、rdは基数、dは关键字の桁数、nは要素数です。

安定性 (1) 直接挿入、バブル、マージ、基数ソートアルゴリズムは安定です。 (2) 直接選択、シェル、クイック、ヒープソートは安定ではありません。

補助空間 (1) 直接挿入、直接選択、バブル、シェル、ヒープソートアルゴリズムは補助空間O(1)が必要です。 (2) クイックソートアルゴリズムは補助空間O(log₂n)が必要です。 (3) マージソートアルゴリズムは補助空間O(n)が必要です。 (4) 基数ソートアルゴリズムは補助空間O(n+rd)が必要です。