常见排序算法之选择排序

￡神魔★判官ぃ 2024-04-18 17:07 65阅读 0赞

# 选择排序 #

[原文地址][Link 1]  
原理：

对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置，接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了，然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。

## 图解： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NTcwNDY0_size_16_color_FFFFFF_t_70]

## 代码实现： ##

public class SelectionSort { 
        public static void main(String[] args) { 
            int arr[] = { 0, 1, 6, 9, 7, 3, 2, 4, 5, 8};
            System.out.println("排序前：");
            System.out.println(Arrays.toString(arr));
            selectionSort(arr);
            System.out.println("排序后：");
            System.out.println(Arrays.toString(arr));
    
        }
    
        public static void selectionSort(int[] arr) { 
    
          //逐渐向后比较，第i个位位置与后面的比较
            for (int i = 0; i < arr.length - 1; i++) { 
              
                for (int j = i+1; j < arr.length; j++) { 
                  //找出最小值与第i 个位置上交换
                    if (arr[i] > arr[j]) { 
                        int tmp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = tmp;
                    }
                }
                //System.out.println("第"+(i+1)+"轮后~~");
                //System.out.println(Arrays.toString(arr));
            }
    
        }
    }

## 测试时间： ##

public class SelectionSort { 
        public static void main(String[] args) { 
           // int arr[] = {0, 1, 6, 9, 7, 3, 2, 4, 5, 8};
            //创建要给80000个的随机的数组
            int[] arr = new int[80000];
            for (int i = 0; i < 80000; i++) { 
                arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
            }
            System.out.println("排序前：");
            System.out.println(Arrays.toString(arr));
            Date data1 = new Date();
            SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
            String date1Str = simpleDateFormat.format(data1);
            System.out.println("排序前的时间是=" + date1Str);
            selectionSort(arr);
            Date data2 = new Date();
            String date2Str = simpleDateFormat.format(data2);
            System.out.println("排序前的时间是=" + date2Str);
    
    
            System.out.println("排序后：");
            System.out.println(Arrays.toString(arr));
    
        }
    
        public static void selectionSort(int[] arr) { 
    
            for (int i = 0; i < arr.length - 1; i++) { 
                for (int j = i+1; j < arr.length; j++) { 
                    if (arr[i] > arr[j]) { 
                        int tmp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = tmp;
                    }
                }
                //System.out.println("第"+(i+1)+"轮后~~");
                //System.out.println(Arrays.toString(arr));
            }
    
        }
    }

排序前的时间是=2019-09-06 08:50:29  
排序前的时间是=2019-09-06 08:50:38

[Link 1]: http://blog.bubbletg.cn/2019/02/02/%E5%B8%B8%E8%A7%81%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%B9%8B%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NTcwNDY0_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/8d861e5d236045d6b79a5224ad816163.png