Java八大排序算法之选择排序

一、动图演示

Java八大排序算法之选择排序

二、思路分析

1.  第一个跟后面的所有数相比,如果小于(或小于)第一个数的时候,暂存较小数的下标,第一趟结束后,将第一个数,与暂存的那个最小数进行交换,第一个数就是最小(或最大的数)

2.  下标移到第二位,第二个数跟后面的所有数相比,一趟下来,确定第二小(或第二大)的数

重复以上步骤

直到指针移到倒数第二位,确定倒数第二小(或倒数第二大)的数,那么最后一位也就确定了,排序完成。

三、负杂度分析

1.  不管原始数组是否有序,时间复杂度都是O(n2),

因为没一个数都要与其他数比较一次,(n-1)2次,分解:n2-2n+1,  去掉低次幂和常数,剩下n2,所以最后的时间复杂度是n2

2.  空间复杂度是O(1),因为只定义了两个辅助变量,与n的大小无关,所以空间复杂度为O(1)

四、Java 代码如下:

import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
        int[] n = new int[]{1,6,3,8,33,27,66,9,7,88};
        int temp,index = -1;
        for (int i = 0; i < n.length-1; i++) {
            index=i;
            //如果大于,暂存较小的数的下标
            for (int j = i+1; j <n.length; j++) {
                if(n[index]>n[j]){
                    index = j;
                }
            }
            ////将一趟下来求出的最小数,与这个数交换
            if(index>0){
                temp = n[i];
                n[i] = n[index];
                n[index] = temp;
            }
            System.out.println(Arrays.toString(n));
        }
        System.out.println(Arrays.toString(n));
    }
}

相关推荐