ここでは ヒープソート（Heap Sort） と シェルソート（Shell Sort） の
わかりやすい Java 実装コードを提示します。
- 初心者向けに読みやすくコメント付き
- main で両方を実行して比較可能
- 配列は同じものを使ってコピーして比較
ヒープソート（Heap Sort）Java 実装
public class HeapSortExample {
// ヒープソート本体
public static void heapSort(int[] arr) {
int n = arr.length;
// 1. 配列を最大ヒープにする（heapify を下から行う）
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 2. ヒープの先頭(最大値)を末尾に移す → 範囲を縮めて heapify
for (int i = n - 1; i >= 0; i--) {
// 先頭と末尾をスワップ
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 残り部分をヒープ化
heapify(arr, i, 0);
}
}
// i を根とする部分木をヒープ化 (size は有効範囲)
private static void heapify(int[] arr, int size, int i) {
int largest = i; // 親ノード
int left = 2 * i + 1; // 左の子
int right = 2 * i + 2; // 右の子
// 左が親より大きければ更新
if (left < size && arr[left] > arr[largest]) {
largest = left;
}
// 右が親より大きければ更新
if (right < size && arr[right] > arr[largest]) {
largest = right;
}
// 親が最大でないならスワップして再帰的に heapify
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, size, largest);
}
}
}
シェルソート（Shell Sort）Java 実装
public class ShellSortExample {
public static void shellSort(int[] arr) {
int n = arr.length;
// ギャップを大きく取り、だんだん狭める（一般的な n/2 方式）
for (int gap = n / 2; gap > 0; gap /= 2) {
// gap 離れたところを挿入ソート的に並べる
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
// gap 分離れた位置を比較して挿入位置を決める
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
}
両方を main で動かすテストコード
import java.util.Arrays;
public class SortCompareMain {
public static void main(String[] args) {
int[] baseArray = { 7, 2, 9, 4, 3, 8, 1, 6 };
// ヒープソート
int[] heapArr = Arrays.copyOf(baseArray, baseArray.length);
HeapSortExample.heapSort(heapArr);
// シェルソート
int[] shellArr = Arrays.copyOf(baseArray, baseArray.length);
ShellSortExample.shellSort(shellArr);
System.out.println("元の配列: " + Arrays.toString(baseArray));
System.out.println("ヒープソート後: " + Arrays.toString(heapArr));
System.out.println("シェルソート後: " + Arrays.toString(shellArr));
}
}
実行結果（例）
元の配列: [7, 2, 9, 4, 3, 8, 1, 6]
ヒープソート後: [1, 2, 3, 4, 6, 7, 8, 9]
シェルソート後: [1, 2, 3, 4, 6, 7, 8, 9]