2.选择排序（Selection sort）

题目

设计一个算法可将{4, 2, -3, 6, 1} （或其他乱序的数组）按升序排序得到 {-3, 1, 2, 4, 6}。

解题思路

如果有一沓人民币，怎么按照面额从小到大按顺序排序？
答：每次从这沓人民币中取出面额最小的放到一边，循环往复直到原有的这沓人民币被取完就排序完成了。
同理，我们可以循环遍历题目中的数组A每次将最小的element移动到数组A的左边，等for循环执行完之后数组A就是一个排好序的数组了。
{4, 2, -3, 6, 1} >
-3 { 2, 4, 6, 1} >
-3, 1 { 4, 6, 2} >
-3, 1, 2 { 6, 4} >
-3, 1, 2, 4 {6} >
{-3, 1, 2, 4 6}

Code

    public void selectSort(int[] arr){
        //corner case: 没有边界值判断的代码是不健壮的
        if(arr == null || arr.length <=1){
            return;
        }
        for(int i=0;i<arr.length-1;i++){//为什么是arr.length-1 ?因为最后一个element已经没有其他ele与其比较了
            int minIndex = i;
            for (int j=minIndex+1;j<arr.length;j++){//为什么j=minIndex+1？因为上次操作之后minIndex+1角标左边的元素已经是sort好的了。
                if(arr[j]<arr[minIndex]){
                    minIndex = j;
                }
            }
            swap2(arr, minIndex, i);
        }
    }
    //交换数组的元素
    private void swap1(int[] arr, int index1, int index2){
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    //交换数组的元素 实现2，在函数调用次数巨大的情况下可以提高一些效率
    private void swap2(int[] arr, int index1, int index2){
        if(index1 == index2)return;
        arr[index1] = arr[index1] + arr[index2];
        arr[index2] = arr[index1] - arr[index2];
        arr[index1] = arr[index1] - arr[index2];
    }

时空复杂度分析

time complexity:
嵌套for => for循环中的代码执行了n*(n-1)次 = > n^2-n => 去掉对复杂度影响较小的系数 => 时间复杂度为O(n^2)

space complexity:
没有创建多余的数组也没有递归,所以空间复杂度是O(1).