选择排序

tiancaisq

选择排序的本质在于每次循环确定一个最大/最小值
默认以第一位作为最大最小值索引（为什么不直接记录值，而是记录索引，因为数组位置需要做交换）
内层循环对剩余数组元素进行循环判断，更新最大/最小值数组对应的索引


因此选择排序两个循环，外层循环整个数组，内层循环从选择元素的下一个开始做比较，确定选择元素对应的数值
for(int i = 0; i< arr.length; i++){
     int minIndex = arr;
      for(int j = i+1; j< arr.length; j++){
           if(arr[j].compareTo(arr[minIndex] < 0)){
                    // 确认最小值，目标元素比默认元素还小，应当选择做交换
                    minIndex = j;
           }
      }
     //  内层循环完毕后就已经确认了i元素应该与哪个最大/最小 元素作交换，直接
     swap(arr, i, minIndex);
}

1. public static <E extends Comparable> void sort(E[] arr){
   
2.         // 选择排序，每次把最大、最小放在前面
   
3.         for(int i = 0; i<arr.length; i++){
   
4. 
   
5.             int minIndex = i;
   
6.             for(int j = i + 1; j<arr.length; j++){
   
7.                 if(arr[j].compareTo(arr[minIndex]) < 0){
   
8.                     minIndex = j;
   
9.                 }
   
10.             }
    
11. 
    
12.             swap(arr, minIndex, i);
    
13.         }
    
14.     }
    
15. 
    
16.     public static void main(String[] args) {
    
17.         Integer[] arr = {9,1,3,5,7,2,4,12,9};
    
18.         sort(arr);
    
19. 
    
20.         Stream.of(arr).forEach(System.out::println);
    
21.     }
    
22. 
    
23.     private static <E extends Comparable> void swap(E[] arr, int minIndex, int i) {
    
24.         E temp = arr[minIndex];
    
25.         arr[minIndex] = arr[i];
    
26.         arr[i] = temp;
    
27.     }

复制代码

A.compareTo(B) ， 返回的结果如果A 大于B 返回1， 如果相等返回0， 如果小于返回-1
那么同理可得，在实现Comparable 接口的时候，覆写CompareTo方法也按照这个思路去写，跟入参比较，直接用当前属性值去减入参属性值即可