public class SelectionSort {
    
    /**
     * 选择排序
     * @param arr 待排序的整数数组
     */
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            // 在未排序区间 [i, n-1] 中查找最小元素
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 将最小元素交换到已排序区间的末尾
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }
    
    /**
     * 选择排序（泛型版本）
     */
    public static <T extends Comparable<T>> void sortGeneric(T[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j].compareTo(arr[minIndex]) < 0) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                T temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }
    
    /**
     * 双向选择排序
     * 每轮同时找出最小值和最大值，分别放到两端
     */
    public static void sortBidirectional(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int minIndex = left, maxIndex = right;
            for (int i = left; i <= right; i++) {
                if (arr[i] < arr[minIndex]) minIndex = i;
                if (arr[i] > arr[maxIndex]) maxIndex = i;
            }
            // 注意处理边界情况
            int temp = arr[left];
            arr[left] = arr[minIndex];
            arr[minIndex] = temp;
            
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            
            temp = arr[right];
            arr[right] = arr[maxIndex];
            arr[maxIndex] = temp;
            
            left++;
            right--;
        }
    }
}