アルゴリズムの改善（分割統治法）

import java.util.Arrays;

public class InsertionSort {

    public static void main(String[] args) {
        int[] data = { 5, 8, 3, 2 };

        System.out.println("0回目の走査: " + Arrays.toString(data));

        for (int i = 1; i < data.length; ++i) {
            int key = data[i];
            int j = i - 1;
            while (j >= 0 && data[j] > key) {
                data[j + 1] = data[j];
                j = j - 1;
            }
            data[j + 1] = key;
            System.out.println(i + "回目の走査: " + Arrays.toString(data));
        }

    }
}

import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
        int[] data = { 5, 8, 3, 2 };

        System.out.println(Arrays.toString(data) + " :整列前");

        int n = data.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // ギャップの値に基づいて挿入ソートを実行
            for (int i = gap; i < n; i += 1) {
                int temp = data[i];
                int j;
                // ギャップを考慮して要素を並び替える
                for (j = i; j >= gap && data[j - gap] > temp; j -= gap) {
                    data[j] = data[j - gap];
                }
                data[j] = temp;
            }

            System.out.println(Arrays.toString(data) + " :gap " + gap + " の途中経過");
        }

        System.out.println(Arrays.toString(data) + " :整列後");
    }
}

import java.util.Arrays;

public class MergeSort {
    
    private static int cnt;//マージ回数をカウントするための変数

    public static void main(String[] args) {
        int[] data = { 5, 8, 3, 2 };

        mergeSort(data, 0, data.length - 1);

    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            // 左半分をソート
            mergeSort(arr, left, mid);

            // 右半分をソート
            mergeSort(arr, mid + 1, right);

            // 2つのソート済み配列をマージ
            merge(arr, left, mid, right);

            System.out.println(++cnt + " 回目のマージ結果: " + Arrays.toString(arr)); // 途中経過を表示
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        // 左半分の配列を一時的な配列にコピー
        int[] leftArr = new int[mid - left + 1];
        for (int i = 0; i < leftArr.length; i++) {
            leftArr[i] = arr[left + i];
        }

        // 右半分の配列を一時的な配列にコピー
        int[] rightArr = new int[right - mid];
        for (int i = 0; i < rightArr.length; i++) {
            rightArr[i] = arr[mid + 1 + i];
        }

        int i = 0; // 左半分の配列のカウンタ
        int j = 0; // 右半分の配列のカウンタ
        int k = left; // マージする配列のカウンタ

        // 左半分と右半分を比較し、小さい方から順に配列に追加
        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        // 左半分の配列に要素が残っている場合、配列に追加
        while (i < leftArr.length) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }

        // 右半分の配列に要素が残っている場合、配列に追加
        while (j < rightArr.length) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }
}

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        int[] data = { 5, 8, 3, 2 };

        System.out.println("整列前: " + Arrays.toString(data));

        quickSort(data, 0, data.length - 1);

        System.out.println("整列後: " + Arrays.toString(data));
    }

    // クイックソートのメイン関数
    public static void quickSort(int[] data, int low, int high) {
        if (low < high) {
            // ピボットの位置を取得
            int pivotIndex = partition(data, low, high);

            // ピボットの左側を再帰的にソート
            quickSort(data, low, pivotIndex - 1);

            // ピボットの右側を再帰的にソート
            quickSort(data, pivotIndex + 1, high);

        }
    }

    // パーティション関数
    public static int partition(int[] data, int low, int high) {
        // ピボットを左端に設定
        int pivot = data[low];

        // ピボットより小さい要素を左側に配置するためのインデックス
        int i = low + 1;

        for (int j = low + 1; j <= high; j++) {
            if (data[j] < pivot) {
                // 要素を交換して、小さい要素を左側に配置
                swap(data, i, j);
                i++;
            }
        }

        // ピボットを正しい位置に配置
        swap(data, low, i - 1);

        return i - 1; // ピボットの位置を返す
    }

    // 要素を交換する関数
    public static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

import java.util.Arrays;

public class HeapSort {

    private static int cnt;

    public void heapSort(int arr[]) {
        int n = arr.length;

        // ヒープを構築する
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // 配列の要素をヒープから1つずつ取り出してソートする
        for (int i = n - 1; i > 0; i--) {
            // 最大値を配列の末尾と交換する
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // ヒープを再構築する
            heapify(arr, i, 0);

            System.out.println(Arrays.toString(arr) + " :" + ++cnt + "回目のヒープからの要素の取り出し"); // 途中経過を表示
        }
    }

    // ヒープを構築するためのユーティリティメソッド
    void heapify(int arr[], int n, int i) {
        int largest = i; // 親ノードの位置
        int left = 2 * i + 1; // 左の子ノードの位置
        int right = 2 * i + 2; // 右の子ノードの位置

        // 左の子ノードが親ノードより大きい場合
        if (left < n && arr[left] > arr[largest])
            largest = left;

        // 右の子ノードが親ノードまたは左の子ノードより大きい場合
        if (right < n && arr[right] > arr[largest])
            largest = right;

        // 最大値が親ノードでない場合、最大値と親ノードを交換し、再帰的にヒープを構築する
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

    // テスト用のプログラム
    public static void main(String args[]) {
        int[] arr = { 5, 8, 3, 2 };

        System.out.println(Arrays.toString(arr) + " :整列前");
        HeapSort heapSort = new HeapSort();
        heapSort.heapSort(arr);

    }
}