Java案例怎么实现选择排序？

本文目录导读：

1. 基本选择排序实现
2. 完整案例演示
3. 增强版选择排序（降序和对象排序）
4. 测试主程序
5. 性能测试

我来详细讲解Java中实现选择排序的几种方式。

基本选择排序实现

选择排序的核心思想：每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置,直到全部待排序的数据元素排完。

public class SelectionSort {
    /**
     * 基本选择排序-升序
     * @param arr 待排序数组
     */
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        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] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 交换当前位置和最小值位置
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }
}

完整案例演示

public class SelectionSortDemo {
    public static void main(String[] args) {
        // 测试用例1：基本数组
        int[] arr1 = {64, 25, 12, 22, 11};
        System.out.println("原始数组: " + arrayToString(arr1));
        selectionSort(arr1);
        System.out.println("排序后数组: " + arrayToString(arr1));
        // 测试用例2：包含重复元素
        int[] arr2 = {5, 2, 8, 2, 9, 1, 5};
        System.out.println("\n测试重复元素:");
        System.out.println("原始数组: " + arrayToString(arr2));
        selectionSort(arr2);
        System.out.println("排序后数组: " + arrayToString(arr2));
        // 测试用例3：已排序数组
        int[] arr3 = {1, 2, 3, 4, 5, 6};
        System.out.println("\n测试已排序数组:");
        System.out.println("原始数组: " + arrayToString(arr3));
        selectionSort(arr3);
        System.out.println("排序后数组: " + arrayToString(arr3));
        // 测试用例4：空数组和单个元素
        int[] arr4 = {};
        int[] arr5 = {42};
        System.out.println("\n测试边界情况:");
        System.out.println("空数组: " + arrayToString(arr4));
        selectionSort(arr4);
        System.out.println("单个元素: " + arrayToString(arr5));
        selectionSort(arr5);
    }
    // 选择排序算法
    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        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] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                swap(arr, i, minIndex);
            }
        }
    }
    // 交换数组中的两个元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    // 数组转字符串
    private static String arrayToString(int[] arr) {
        if (arr == null || arr.length == 0) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i < arr.length - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}

增强版选择排序（降序和对象排序）

public class AdvancedSelectionSort {
    // 降序排序
    public static void selectionSortDesc(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int maxIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }
            if (maxIndex != i) {
                int temp = arr[i];
                arr[i] = arr[maxIndex];
                arr[maxIndex] = temp;
            }
        }
    }
    // 泛型版本（支持对象排序）
    public static <T extends Comparable<T>> void selectionSortGeneric(T[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        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 selectionSortWithSteps(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int n = arr.length;
        System.out.println("选择排序过程演示:");
        System.out.println("初始数组: " + arrayToString(arr));
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            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;
                System.out.println("第 " + (i + 1) + " 步: " + arrayToString(arr));
            }
        }
    }
}

测试主程序

public class TestSelectionSort {
    public static void main(String[] args) {
        // 测试基本排序
        System.out.println("=== 基本选择排序测试 ===");
        int[] arr1 = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前: " + arrayToString(arr1));
        SelectionSortDemo.selectionSort(arr1);
        System.out.println("排序后: " + arrayToString(arr1));
        // 测试降序排序
        System.out.println("\n=== 降序排序测试 ===");
        int[] arr2 = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("排序前: " + arrayToString(arr2));
        AdvancedSelectionSort.selectionSortDesc(arr2);
        System.out.println("降序后: " + arrayToString(arr2));
        // 测试泛型版本
        System.out.println("\n=== 泛型版本测试 ===");
        String[] arr3 = {"banana", "apple", "cherry", "date"};
        System.out.println("排序前: " + arrayToString(arr3));
        AdvancedSelectionSort.selectionSortGeneric(arr3);
        System.out.println("排序后: " + arrayToString(arr3));
        // 测试排序过程可视化
        System.out.println("\n=== 排序过程演示 ===");
        int[] arr4 = {29, 10, 14, 37, 13};
        AdvancedSelectionSort.selectionSortWithSteps(arr4);
    }
    // 辅助方法：数组转字符串
    private static String arrayToString(int[] arr) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i < arr.length - 1) sb.append(", ");
        }
        sb.append("]");
        return sb.toString();
    }
    private static <T> String arrayToString(T[] arr) {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i < arr.length - 1) sb.append(", ");
        }
        sb.append("]");
        return sb.toString();
    }
}

性能测试

public class SelectionSortPerformance {
    public static void main(String[] args) {
        // 创建测试数组
        int size = 10000;
        int[] arr = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            arr[i] = random.nextInt(10000);
        }
        // 计时
        long startTime = System.currentTimeMillis();
        SelectionSortDemo.selectionSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("排序 " + size + " 个元素用时: " + (endTime - startTime) + " 毫秒");
    }
}

1. 算法特点：

   • 时间复杂度：O(n²)
   • 空间复杂度：O(1)
   • 不稳定排序算法

2. 实现要点：

   • 找到未排序部分的最小值索引
   • 与当前位置交换
   • 支持升序和降序

3. 优缺点：

   • 优点：简单直观，数据交换次数少
   • 缺点：效率较低，不适合大数据集

4. 适用场景：

   • 数据量较小（< 1000）
   • 对稳定性没有要求
   • 需要简单易懂的实现

这个实现包含了基本选择排序、降序排序、泛型版本和可视化版本,可以根据实际需求选择合适的实现方式。