排序算法——选择排序

简单介绍

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

图解分析图：

image-20230217212437015

思路：

  1. 选择排序一共有 数组大小 - 1 轮排序
  2. 每1轮排序，又是一个循环, 循环的规则(代码)
    1. 先假定当前这个数是最小数
    2. 然后和后面的每个数进行比较，如果发现有比当前数更小的数，就重新确定最小数，并得到下标
    3. 当遍历到数组的最后时，就得到本轮最小数和下标
    4. 交换

代码

算法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//选择排序
    public static void selecctSorting ( int[] arr ) {

        for ( int i = 0 ; i < arr.length - 1 ; i++ ) {
            int minIndex = i;
            int min = arr[ minIndex ];
            for ( int j = i + 1 ; j < arr.length ; j++ ) {
                if ( min > arr[ j ] ) {
                    min      = arr[ j ]; //重置min
                    minIndex = j;
                }
            }
            if ( min != arr[ i ] ) {  //加一个判断，避免不必要的交换，浪费时间
                //将这个最小值放在此时的最前面
                arr[ minIndex ] = arr[ i ];
                arr[ i ]        = min;
            }
//            System.out.println ( "第" + ( i + 1 ) + "轮后 " + Arrays.toString ( arr ) );
        }
    }

测试性能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class SlecctSorting {
    public static void main ( String[] args ) {

       /* int[] arr = {101, 34, 119, 1};
        selecctSorting ( arr );
        System.out.println ("排序后 " + Arrays.toString ( arr ) );*/

        //创建80000个数据的数组
        int arr[] = new int[ 80000 ];
        randomArr ( arr );
        System.out.println ("选择排序所用时间" );
        String date1String = Date ( );
        System.out.println ("排序前时间是："+date1String );
        selecctSorting ( arr );
        String date2String = Date ( );
        System.out.println ("排序后时间是："+date2String );
    }

    //选择排序
    public static void selecctSorting ( int[] arr ) {

        for ( int i = 0 ; i < arr.length - 1 ; i++ ) {
            int minIndex = i;
            int min = arr[ minIndex ];
            for ( int j = i + 1 ; j < arr.length ; j++ ) {
                if ( min > arr[ j ] ) {
                    min      = arr[ j ]; //重置min
                    minIndex = j;
                }
            }
            if ( min != arr[ i ] ) {  //加一个判断，避免不必要的交换，浪费时间
                //将这个最小值放在此时的最前面
                arr[ minIndex ] = arr[ i ];
                arr[ i ]        = min;
            }
//            System.out.println ( "第" + ( i + 1 ) + "轮后 " + Arrays.toString ( arr ) );
        }
    }

    private static void randomArr ( int[] arr ) {
        for(int i = 0; i < arr.length;i++){
            arr[ i ] = (int) ( Math.random ( ) * 8000000 );  //会生成【0，8000000）直接的数
        }
    }

    /**
     * 将此时调用函数的时间格式化打出来
     * @return 年-月-日 时-分秒
     */
    private static String Date ( ) {
        Date date1 = new Date ( );  //调函数的当前时间
        SimpleDateFormat simpleFormatter = new SimpleDateFormat ( "HH:mm:ss" );//格式化
        return simpleFormatter.format(date1 );
    }
}

结果

image-20230217221613345