zcq

    1. package com.atguigu.sort;
    3. import java.text.SimpleDateFormat;
    4. import java.util.Arrays;
    5. import java.util.Date;
    6. //选择排序
    7. public class SelectSort {
    9.     public static void main(String[] args) {
    10.         //int [] arr = {101, 34, 119, 1, -1, 90, 123};
    12.         //创建要给80000个的随机的数组
    13.         int[] arr = new int[80000];
    14.         for (int i = 0; i < 80000; i++) {
    15.             arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
    16.         }
    18.         System.out.println("排序前");
    19.         //System.out.println(Arrays.toString(arr));
    21.         Date data1 = new Date();
    22.         SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    23.         String date1Str = simpleDateFormat.format(data1);
    24.         System.out.println("排序前的时间是=" + date1Str);
    26.         selectSort(arr);
    29.         Date data2 = new Date();
    30.         String date2Str = simpleDateFormat.format(data2);
    31.         System.out.println("排序前的时间是=" + date2Str);
    33.         //System.out.println("排序后");
    34.         //System.out.println(Arrays.toString(arr));
    37.     }
    39.     //选择排序
    40.     public static void selectSort(int[] arr) {
    44.         //在推导的过程，我们发现了规律，因此，可以使用for来解决
    45.         //选择排序时间复杂度是 O(n^2)
    46.         for (int i = 0; i < arr.length - 1; i++) {
    47.             int minIndex = i;
    48.             int min = arr[i];
    49.             for (int j = i + 1; j < arr.length; j++) {
    50.                 if (min > arr[j]) { // 说明假定的最小值，并不是最小
    51.                     min = arr[j]; // 重置min
    52.                     minIndex = j; // 重置minIndex
    53.                 }
    54.             }
    56.             // 将最小值，放在arr[0], 即交换
    57.             if (minIndex != i) {
    58.                 arr[minIndex] = arr[i];
    59.                 arr[i] = min;
    60.             }
    62.             //System.out.println("第"+(i+1)+"轮后~~");
    63.             //System.out.println(Arrays.toString(arr));// 1, 34, 119, 101
    64.         }
    67.         /*
    69.         //使用逐步推导的方式来，讲解选择排序
    70.         //第1轮
    71.         //原始的数组 ：     101, 34, 119, 1
    72.         //第一轮排序 :       1, 34, 119, 101
    73.         //算法 先简单--》 做复杂， 就是可以把一个复杂的算法，拆分成简单的问题-》逐步解决
    75.         //第1轮
    76.         int minIndex = 0;
    77.         int min = arr[0];
    78.         for(int j = 0 + 1; j < arr.length; j++) {
    79.             if (min > arr[j]) { //说明假定的最小值，并不是最小
    80.                 min = arr[j]; //重置min
    81.                 minIndex = j; //重置minIndex
    82.             }
    83.         }
    86.         //将最小值，放在arr[0], 即交换
    87.         if(minIndex != 0) {
    88.             arr[minIndex] = arr[0];
    89.             arr[0] = min;
    90.         }
    92.         System.out.println("第1轮后~~");
    93.         System.out.println(Arrays.toString(arr));// 1, 34, 119, 101
    96.         //第2轮
    97.         minIndex = 1;
    98.         min = arr[1];
    99.         for (int j = 1 + 1; j < arr.length; j++) {
    100.             if (min > arr[j]) { // 说明假定的最小值，并不是最小
    101.                 min = arr[j]; // 重置min
    102.                 minIndex = j; // 重置minIndex
    103.             }
    104.         }
    106.         // 将最小值，放在arr[0], 即交换
    107.         if(minIndex != 1) {
    108.             arr[minIndex] = arr[1];
    109.             arr[1] = min;
    110.         }
    112.         System.out.println("第2轮后~~");
    113.         System.out.println(Arrays.toString(arr));// 1, 34, 119, 101
    115.         //第3轮
    116.         minIndex = 2;
    117.         min = arr[2];
    118.         for (int j = 2 + 1; j < arr.length; j++) {
    119.             if (min > arr[j]) { // 说明假定的最小值，并不是最小
    120.                 min = arr[j]; // 重置min
    121.                 minIndex = j; // 重置minIndex
    122.             }
    123.         }
    125.         // 将最小值，放在arr[0], 即交换
    126.         if (minIndex != 2) {
    127.             arr[minIndex] = arr[2];
    128.             arr[2] = min;
    129.         }
    131.         System.out.println("第3轮后~~");
    132.         System.out.println(Arrays.toString(arr));// 1, 34, 101, 119 */
    135.     }
    137. }