浅谈选择排序

思想

首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置（如果第一个元素就是最小元素那么就和自己交换）。在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。这种方法叫做选择排序，因为它在不断地选择剩余元素之中的最小者。

过程分析

举例：{5,1,2,0,1,8}

----------------------------第一次排序-------------------------

原始数据：5 1 2 0 1 8
除5以外的最小元素为0,则5与0交换
结果： 0 1 2 5 1 8

----------------------------第二次排序-------------------------

原始数据： 0 1 2 5 1 8
除0 1以外的最小元素为1,不交换
结果：0 1 2 5 1 8

----------------------------第三次排序-------------------------

原始数据： 0 1 2 5 1 8
除0 1 2以外的最小元素为1,则2与1交换
结果：0 1 1 5 2 8

----------------------------第四次排序-------------------------

原始数据： 0 1 1 5 2 8
除0 1 1 5以外的最小元素为2,则5与2交换
结果：0 1 1 2 5 8

----------------------------第五次排序-------------------------

原始数据： 0 1 1 5 2 8
除0 1 1 5 2以外的最小元素为2,不交换
结果：0 1 1 2 5 8

源码

public class SelectionSort{
    
    public static void main(String[] args)
    {
        //将数组a按升序排列
        int[] a = {5,1,2,0,1,8};
        
        System.out.print("排序前：");
        for(int i : a) {
            System.out.print(i+" ");
        }
        System.out.println();
        
        for(int i = 0; i<a.length; i++) {
            int minIndex = i;//最小元素的索引
            for(int j = i+1; j<a.length; j++) {
                if(a[j]<a[minIndex]) {
                    minIndex = j;//更新目前找到的最小值元素的索引
                }
            }
            
            //内层循环结束后，再进行交换
            if(minIndex > i) {
                int temp = a[minIndex];
                a[minIndex] = a[i];
                a[i] = temp;
            }
        }
        
        System.out.print("排序后：");
        for(int i : a) {
            System.out.print(i+" ");
        }
    }
}

复杂度分析

假设有N个元素，首先看内循环，第一次内循环比较N-1次，第二次比较N-2，……，最后一次比较1次。共比较（N-1）+ (N-2) + … + 1，等差数列求和，N(N-1)/2，去掉最高项系数，时间复杂度为O(N^2)