选择排序

介绍

思想: 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始(末尾)位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法，如：{6, 6，2}在进行选择排序，第一次就将第一个6和最后一个2进行了交换，此时第一个6跑到了第二个6的后面，表示该排序不稳定。

排序算法是否稳定，是指排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序是否相同，相同则为稳定排序，否则为不稳定。

执行过程：
在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个 元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
…
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

图解：

平均时间复杂度：O(n²)

实现代码

public class SelectSort {
    
    
    public static int[] selectSort(int[] sourceArray){
    
        int[] arr = Arrays.copyOf(sourceArray,sourceArray.length);
        //temp用来下面的交换的临时值
        int temp;
        for (int i = 0; i <arr.length-1 ; i++) {
    
            //minIndex用来记录此次遍历过程中的最小值的下标
            int minIndex = i;
            for (int j = i+1; j <arr.length ; j++) {
    
                if(arr[j]<arr[minIndex]){
    
                    minIndex=j;
                }
            }
            // 进行交换
            if(minIndex!=i){
    
                temp = arr[i];
                arr[i]=arr[minIndex];
                arr[minIndex] = temp;
            }
        }
       return arr;
    }
    //测试
    public static void main(String[] args) {
    
        int[] arr = {
    10,4,3,6,1,8,2,5,7,9,0};
        System.out.println("选择排序前:"+Arrays.toString(arr));
        System.out.println("--------------------");
        int[] arr1 = selectSort(arr);
        System.out.println("排序后："+Arrays.toString(arr1));
    }

}

截图