关于java:选择排序

抉择排序

第一次从数组中查最小的元素，放到数组起始地位，而后从残余的元素中找到最小的，放到数组有序局部开端，顺次这样查找排序，直至完结。

题目

给定一组数据进行抉择排序，以 {9, 3, 4, 2, 0, 1, 5, 8} 为例。

抉择排序过程

工夫复杂度 O(N²) 剖析

第一次排序，须要比拟了 N - 1 次；
第二次排序，须要比拟了 N - 2 次；
……
第 N - 1 次排序，须要比拟了 1 次；

比拟次数 =(N-1)+(N-2)+…+1=((1+ N-1)*(N-1))/2=N²/2 + N/2
所以工夫复杂度为：O(N²)

Java 代码

public class SortUtils {public void selectionSort(int[] arr) {if(arr == null || arr.length < 2) {return;}
        for(int i = 0, len = arr.length - 1; i < len; i++) {
            int minIndex = i;
            for(int j = i + 1; j < len + 1; j++) {minIndex = arr[j] < arr[minIndex] ? j :   minIndex;
            }
            swap(arr, minIndex, i);
        }
    }

    public void swap(int[] arr, int i, int j) {if(i == j) {return;}
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}