排序算法之选择排序

基本思想

选择排序算法的基本思想是：首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么它就和自己交换）。再次，在剩下的元素中找到最小的元素，将它和数组的第二个元素交换位置。如此重复，直到将整个数组排序。

代码实现

package sortdemo;

public class SelectSort {
    public static void main(String[] args){
        int[] arr = {3,0,6,5,7,4,9,8,1};
        System.out.println("排序之前：");
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
        selectSort(arr);
        System.out.println();
        System.out.println("排序之后:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    public static void selectSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            int min = i;
            for(int j=i+1;j<arr.length;j++)
                if(arr[j]<arr[min]) min=j;//交换arr[i]和arr[min]
            swap(arr,min,i);
        }
    }
    public static void swap(int[] arr,int a,int b){
        int temp = arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
        
    }

}

复杂度

选择排序的时间复杂度：简单选择排序的比较次数与序列的初始排序无关。假设待排序的序列有N个元素，则比较次数永远都是N(N-1)/2。而移动次数与序列的初始排序有关。当序列正序时，移动次数最少，为0。当序列反序时，移动次数最多，为3N(N-1)/2。综上，简单选择排序的时间复杂度为O(N^2)。