排序算法：选择排序

小鱼儿 2023-02-28 01:21 18阅读 0赞

# 1，选择排序基本介绍 #

*  选择排序也属于内部排序，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置已达到排序的目的
 *  选择排序的基本思想是：从第一个数开始，依次与后面的数进行比较，选出最小的数并进行位置交换，之后进行第二个和后续所有数据的比较和交换，以此类推。通过`length - 1`次后，获取到一个从小到大排列的有序数组
 *  选择排序的时间复杂度为`O(n^2)`。大数据量下，相对于冒泡排序性能会好很多，主要是因为选择排序比冒泡排序内部交换更少

# 2，选择排序示例 #

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

# 3，选择排序代码演示 #

package com.self.datastructure.sort;
    
    import java.util.Arrays;
    
    /** * 选择排序 * @author PJ_ZHANG * @create 2020-01-15 14:36 **/
    public class SelectSort { 
    
        public static void main(String[] args) { 
            // int[] array = {10, 8, 3, 9, 2, 6, -1};
            // 10万个数测试，测试结果为5S
            int[] array = new int[100000];
            for (int i = 0; i < 100000; i++) { 
                array[i] = (int) (Math.random() * 8000000);
            }
            long startTime = System.currentTimeMillis();
            selectSort(array);
            // System.out.println(Arrays.toString(array));
            System.out.println("cast time : " + (System.currentTimeMillis() - startTime));
        }
    
        // 选择排序处理
        // 从一个数开始, 依次与后面所有的数比较, 并将当前数替换为最小数, 并在头部固定
        // 全部处理完成后, 会形成一个顺序数组
        private static void selectSort(int[] array) { 
            // 从第一个元素开始比较, 比较到倒数第二个元素, 最后一个元素无需自比较
            for (int i = 0; i < array.length - 1; i++) { 
                int temp = array[i]; // 默认取当前值为最小值
                int minIndex = i; // 最小值索引
                // 内循环从外循环的后一个元素开始算起, 进行元素比较, 一直比较到最后一个元素
                for (int j = i + 1; j < array.length; j++) { 
                    // 比较获取到最小值
                    if (temp > array[j]) { 
                        temp = array[j]; // 最小值
                        minIndex = j; // 最小值索引
                    }
                }
                // 循环完成后, 如果存在小于该元素的索引值, 则进行替换
                if (minIndex != i) { 
                    array[minIndex] = array[i];
                    array[i] = temp;
                }
            }
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE5NzYzODg_size_16_color_FFFFFF_t_70]: /images/20230209/a5108276d16e4405bcab252c06fa9dfe.png