选择排序算法之泛型优化

选择排序算法

工作原理：

每一次从待排序的数据元素中选中最小的一个元素，然后，再从剩余未排序元素中继续寻找最小元素，将2个元素交换位置，就达到了已排序的元素一直是从小到大了。

这个算法的时间复杂度为O(n²)，空间复杂度为O(1)。

/**
 * @Author: 翰林猿
 * @Description:选择排序
 **/
public class Select {
    public Select() {
    }
​
    public static void SelectionSort(int[] arr) {
        //i: 当前位置  j: 从当前位置开始增加的变量(用于从当前位置开始遍历，减少遍历量)
        for (int i = 0; i < arr.length; i++) {      //遍历数组,发现最小的,与当前的交换
            int min_index = i;                      //用于记录最小项的下标
            for (int j = i; j < arr.length; j++) {  //从当前位置开始遍历，找到最小的
                if (arr[min_index] > arr[j]) {       //如果最小项大于j处项
                    min_index = j;
                }
            }
            //到此为止，我们已经找到了比当前位置i小的最小项，将二者交换即可。
            swap(min_index, i, arr);
        }
    }
​
    public static void swap(int min_index, int i, int[] arr) {  
        int t = arr[min_index];
        arr[min_index] = arr[i];
        arr[i] = t;
    }
​
    public static void main(String[] args) {
        int[] arr = {1, 8, 9, 7, 3, 5, 6};
        Select.SelectionSort(arr);
        for (int it : arr) {
            System.out.println(it);
        }
    }
}

当然，为了匹配多种类型的对象，可以使用泛型匹配各类对象的排序

/**
 * @Author: 翰林猿
 * @Description:选择排序
 **/
public class Select {
    public Select() {
    }
​
    public static <E extends Comparable<E>>void SelectionSort(E[] arr) {        
        //i: 当前位置  j: 从当前位置开始增加的变量(用于从当前位置开始遍历，减少遍历量)
        for (int i = 0; i < arr.length; i++) {              //遍历数组,发现最小的,与当前的交换
            int min_index = i;                              //用于记录最小项的下标
            for (int j = i; j < arr.length; j++) {          //从当前位置开始遍历，找到最小的
                if (arr[min_index].compareTo(arr[j]) < 0) {       //如果最小项大于j处项
                    min_index = j;
                }
            }
            //到此为止，我们已经找到了比当前位置i小的最小项，将二者交换即可。
            swap(min_index, i, arr);
        }
    }
​
    public static <E> void swap(int min_index, int i, E[] arr) {
        E t = arr[min_index];
        arr[min_index] = arr[i];
        arr[i] = t;
    }
​
    public static void main(String[] args) {
        Integer[] arr = {1, 8, 9, 7, 3, 5, 6};
        Select.SelectionSort(arr);
        for (int it : arr) {
            System.out.println(it);
        }
    }
}