// 第 5 周 – 实践课练习的参考答案
// 运行：java Exercises05.java
import java.util.Arrays;

public class Exercises05 {

    // E1. 数组是否有序？– O(n)
    static boolean isSorted(int[] a) {
        for (int i = 1; i < a.length; i++) if (a[i - 1] > a[i]) return false;
        return true;
    }

    // E2. 降序插入排序：只需把关系反过来
    static void insertionSortDesc(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int x = a[i], j = i - 1;
            while (j >= 0 && a[j] < x) { a[j + 1] = a[j]; j--; }
            a[j + 1] = x;
        }
    }

    // E3. 用选择排序对字符串排序（compareTo）
    static void selectionSortStrings(String[] a) {
        for (int i = 0; i < a.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) if (a[j].compareTo(a[min]) < 0) min = j;
            String t = a[i]; a[i] = a[min]; a[min] = t;
        }
    }

    // E4. 按分数对记录排序 – 插入排序是稳定的
    record Student(String name, int score) {
        public String toString() { return name + ":" + score; }
    }

    static void sortByScore(Student[] a) {
        for (int i = 1; i < a.length; i++) {
            Student x = a[i];
            int j = i - 1;
            while (j >= 0 && a[j].score() > x.score()) { a[j + 1] = a[j]; j--; } // 用 > 而不是 >=：稳定！
            a[j + 1] = x;
        }
    }

    // E5. 最小的 k 个元素：选择排序的前 k 步 – O(k·n)
    static int[] kSmallest(int[] a, int k) {
        int[] b = a.clone();
        for (int i = 0; i < k; i++) {
            int min = i;
            for (int j = i + 1; j < b.length; j++) if (b[j] < b[min]) min = j;
            int t = b[i]; b[i] = b[min]; b[min] = t;
        }
        return Arrays.copyOf(b, k);
    }

    // E6. 计数排序（取值范围较小，0..maxValue）– O(n + k)，不是比较排序
    static void countingSort(int[] a, int maxValue) {
        int[] count = new int[maxValue + 1];
        for (int v : a) count[v]++;
        int k = 0;
        for (int v = 0; v <= maxValue; v++)
            while (count[v]-- > 0) a[k++] = v;
    }

    // E7. 冒泡排序交换多少次？（= 逆序对的个数）
    static int inversions(int[] a) {
        int c = 0;
        for (int i = 0; i < a.length; i++)
            for (int j = i + 1; j < a.length; j++)
                if (a[i] > a[j]) c++;
        return c;
    }

    public static void main(String[] args) {
        System.out.println("E1. isSorted([1,2,2,5]) = " + isSorted(new int[] { 1, 2, 2, 5 }) + ", isSorted([3,1]) = " + isSorted(new int[] { 3, 1 }));
        int[] d = { 5, 2, 8, 1, 9, 3 };
        insertionSortDesc(d);
        System.out.println("E2. descending: " + Arrays.toString(d));
        String[] cities = { "Wuhan", "Beijing", "Shanghai", "Chengdu", "Eger" };
        selectionSortStrings(cities);
        System.out.println("E3. cities: " + Arrays.toString(cities));
        Student[] st = { new Student("Li", 85), new Student("Wang", 90), new Student("Zhang", 85), new Student("Chen", 70) };
        sortByScore(st);
        System.out.println("E4. by score (stable): " + Arrays.toString(st));
        System.out.println("E5. 3 smallest: " + Arrays.toString(kSmallest(new int[] { 7, 2, 9, 4, 1, 8 }, 3)));
        int[] grades = { 3, 5, 1, 4, 5, 2, 3, 5, 4, 1 };
        countingSort(grades, 5);
        System.out.println("E6. counting sort (grades): " + Arrays.toString(grades));
        System.out.println("E7. inversions [5,2,8,1,9,3]: " + inversions(new int[] { 5, 2, 8, 1, 9, 3 }));
    }
}