// 第 5 周 – 冒泡排序、选择排序和插入排序，逐步打印
// 运行：java SimpleSorts.java
import java.util.Arrays;

public class SimpleSorts {

    // 冒泡排序（改进版）：如果某一趟没有交换，数组就有序了。
    //   伪代码（从 1 开始）：
    //     For i ← n down to 2
    //       swapped ← false
    //       For j ← 1 to i − 1
    //         If A[j] > A[j + 1] then swap(A[j], A[j + 1]) ; swapped ← true
    //       End for
    //       If not swapped then exit
    //     End for
    static void bubbleSort(int[] a, boolean trace) {
        int n = a.length;
        for (int i = n - 1; i >= 1; i--) {
            boolean swapped = false;
            for (int j = 0; j < i; j++) {
                if (a[j] > a[j + 1]) {
                    int t = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = t;
                    swapped = true;
                }
            }
            if (trace) System.out.println("  after pass: " + Arrays.toString(a));
            if (!swapped) break;
        }
    }

    // 选择排序：找出未排序部分的最小值，把它放到前面。
    //   For i ← 1 to n − 1
    //     min ← i
    //     For j ← i + 1 to n : If A[j] < A[min] then min ← j
    //     swap(A[i], A[min])
    //   End for
    static void selectionSort(int[] a, boolean trace) {
        int n = a.length;
        for (int i = 0; i < n - 1; i++) {
            int min = i;
            for (int j = i + 1; j < n; j++) {
                if (a[j] < a[min]) min = j;
            }
            int t = a[i];
            a[i] = a[min];
            a[min] = t;
            if (trace) System.out.println("  step " + (i + 1) + ":     " + Arrays.toString(a));
        }
    }

    // 插入排序：把下一个元素插入到前面已经有序的部分。
    //   For i ← 2 to n
    //     x ← A[i] ; j ← i − 1
    //     While j ≥ 1 and A[j] > x : A[j + 1] ← A[j] ; j ← j − 1
    //     A[j + 1] ← x
    //   End for
    static void insertionSort(int[] a, boolean trace) {
        for (int i = 1; i < a.length; i++) {
            int x = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > x) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = x;
            if (trace) System.out.println("  step " + i + ":     " + Arrays.toString(a));
        }
    }

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

        System.out.println("Bubble sort " + Arrays.toString(data));
        bubbleSort(data.clone(), true);

        System.out.println("Selection sort " + Arrays.toString(data));
        selectionSort(data.clone(), true);

        System.out.println("Insertion sort " + Arrays.toString(data));
        insertionSort(data.clone(), true);
    }
}