1 基本介绍

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

2 选择排序思想

尚硅谷Java数据结构和算法更多Java–大数据–前端–python人工智能-区块链资料下载，可访问百度：尚硅谷官网第128页选择排序（selectsorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]_{arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]}arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]_{arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]}arr[n-1]中选取最小值，与arr[i-1]交换，…,第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

3 选择排序思路分析图

在这里插入图片描述

对一个数组的选择排序再进行讲解

4 代码示例

package com.sukang.sort;import java.text.SimpleDateFormat;import java.util.Arrays;import java.util.Date;/** * @description: * @author: sukang * @date: 2020-07-08 8:38 */public class SelectSort {    public static void main(String[] args) {        //创建要给80000个的随机的数组        int[] arr = new int[80000];        for (int i = 0; i < 80000; i++) {            arr[i] = (int)(Math.random()*8000000);//生成一个[0,8000000)数        }        //没排序之前数组遍历        System.out.println("排序前的数组" + Arrays.toString(arr));        Date data1=new Date();        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-ddHH:mm:ss");        String date1Str = simpleDateFormat.format(data1);        System.out.println("排序前的时间是="+date1Str);        selectSort(arr);        Date data2 = new Date();        String date2Str = simpleDateFormat.format(data2);        System.out.println("排序后的时间是="+date2Str);        //排序之后数组遍历        System.out.println("排序后的数组" + Arrays.toString(arr));    }    public static void selectSort(int[] arr){        //在推导的过程，我们发现了规律，因此，可以使用for来解决        //选择排序时间复杂度是O(n^2)        for (int i = 0; i < arr.length - 1; i++) {            //声明最小值索引            int minIndex = i;            //声明最小值            int min = arr[i];            for (int j = i + 1; j < arr.length; j++) {                if(min > arr[j]){                    min = arr[j];                    minIndex = j;                }            }            if(minIndex != i){                arr[minIndex] = arr[i];                arr[i] = min;            }        }        /*//使用逐步推导的方式来，讲解选择排序        //第1轮        //原始的数组：101,34,119,1        //第一轮排序:1,34,119,101        //算法先简单--》做复杂，就是可以把一个复杂的算法，拆分成简单的问题-》逐步解决        //第1轮        int minIndex = 0;        int min = arr[0];        for(int j = 0 + 1; j < arr.length; j++){            if(min > arr[j]) {//说明假定的最小值，并不是最小                min = arr[j];//重置min                minIndex = j;//重置minIndex            }        }        //将最小值，放在arr[0],即交换        if(minIndex != 0){            arr[minIndex] = arr[0];            arr[0] = min;        }        System.out.println("第1轮后~~");        System.out.println(Arrays.toString(arr));//1,34,119,101        //第2轮        minIndex = 1;        min = arr[1];        for(int j = 1 + 1; j < arr.length; j++){            if(min > arr[j]) {//说明假定的最小值，并不是最小                min = arr[j];//重置min                minIndex = j;//重置minIndex            }        }        //将最小值，放在arr[0],即交换        if(minIndex != 1){            arr[minIndex] = arr[1];            arr[1] = min;        }        System.out.println("第2轮后~~");        System.out.println(Arrays.toString(arr));//1,34,119,101        //第3轮        minIndex = 2;        min = arr[2];        for(int j = 2 + 1; j < arr.length; j++){            if(min > arr[j]) {//说明假定的最小值，并不是最小                min = arr[j];//重置min                minIndex = j;//重置minIndex            }        }        //将最小值，放在arr[0],即交换        if(minIndex != 2){            arr[minIndex] = arr[2];            arr[2] = min;        }        System.out.println("第3轮后~~");        System.out.println(Arrays.toString(arr));//1,34,101,119*/    }}

运行结果

转载地址：http://zonti.baihongyu.com/

你可能感兴趣的文章