一看就会的【选择排序】及优化

逃离我推掉我的手 2022-11-12 11:58 193阅读 0赞

最简单的选择排序，每次循环找到一个最小值放到数组的最左侧

/**
         * 最简单版本选择排序，每次循环找到一个最小的值放在最左边
         *
         * @param arr
         */
        public static void selectSort1(int[] arr) {
    
            for (int j = 0; j < arr.length; j++) {
    
                int min = arr[j];
                int minIndex = j;
                for (int i = j; i < arr.length; i++) {
    
                    if (arr[i] < min) {
                        min = arr[i];
                        minIndex = i;
                    }
                }
    
                arr[minIndex] = arr[j];
                arr[j] = min;
            }
        }

优化版本

1. 减少循环次数

2. 如果最小值就是本身则不做交换

/**
         * 优化版本选择排序，假设数组有n个数，前n-1次排序完成后，最后一个数肯定是最大/最小的，可以忽略
         *
         * @param arr
         */
        public static void selectSort2(int[] arr) {
    
            // 此处 arr.length - 1 少循环一次
            for (int j = 0; j < arr.length - 1; j++) {
    
                int min = arr[j];
                int minIndex = j;
                for (int i = j; i < arr.length; i++) {
    
                    // 此处不应该每次都做交换，在依次循环结束后找到最小值后做一次交换
                    if (arr[i] < min) {
                        min = arr[i];
                        minIndex = i;
                    }
                }
    
                // 有可能当前节点就是最小值，不需要自己和自己做交换
                if (minIndex != j) {
                    arr[minIndex] = arr[j];
                    arr[j] = min;
                }
            }
        }