关于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;
    }
}