java数据结构和算法——选择排序算法

一、选择排序算法的基本介绍

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

二、选择排序算法的思想

• 选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：
• 第一次从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]交换
• 得到一个按排序码从小到大排列的有序序列

三、选择排序算法的思路分析图

四、选择排序算法的应用示例需求

示例需求：有一群牛 , 颜值的打分分别是 101, 34, 119, 1 请使用选择排序从低到高进行排序

五、选择排序算法推导过程示例演示

1、代码

package com.rf.springboot01.dataStructure.sort;

import java.util.Arrays;

/**
 * @description: 选择排序算法推导过程示例演示
 * @author: xiaozhi
 * @create: 2020-08-05 21:59
 */
public class SelectSort {
    public static void main(String[] args) {
        int[] arr ={101, 34, 119, 1};
        System.out.println("排序前的数组-----------------");
        System.out.println(Arrays.toString(arr));

        selectSort(arr);

        System.out.println("排序后的数组-----------------");
        System.out.println(Arrays.toString(arr));
    }
    /** 
    * @Description: 选择排序推导过程示例方法
    * @Param:  
    * @Author: xz  
    * @return: 
    * @Date: 2020/8/5 22:00  
    */
    public static void selectSort(int[] arr){

        System.out.println("选择排序推导过程+++++++++++++++++");

        //第一轮排序
        int minIndex=0;//假设最小值的数组下标为0
        int minValue=arr[0];//假设最小的值为数组下标为0的数
        for(int j=0+1;jarr[j]){//如果假设的数组下标为0的最小值比后面的数大
                minValue=arr[j];//重置最小值
                minIndex=j;//重置最小值下标
            }
        }
        //原始数组结果     101, 34, 119, 1
        //第一轮排序结果   1，34, 119, 101
        if(minIndex!=0){//真正的最小值数组小标不为0，进行交换
            arr[minIndex]=arr[0];//把假设的数组下标为0的最小值（arr[0]即101）赋值给真正最小值（arr[minIndex]即1）的位置
            arr[0]=minValue;//把真正的最小值（minValue即1）赋值给数组下标为0（arr[0]即101）的位置
        }
        System.out.println("第一轮排序后的数组=============");
        System.out.println(Arrays.toString(arr));



        //第二轮排序
        minIndex=1;//假设最小值的数组下标为1
        minValue=arr[1];//假设最小的值为数组下标为1的数
        for(int j=1+1;jarr[j]){//如果假设的数组下标为1的最小值比后面的数大
                minValue=arr[j];//重置最小值
                minIndex=j;//重置最小值下标
            }
        }

        //第一轮排序结果   1，34, 119, 101
        //第二轮排序结果   1, 34, 119, 101
        if(minIndex!=1){//真正的最小值数组小标不为1，进行交换
            arr[minIndex]=arr[1];
            arr[1]=minValue;
        }
        System.out.println("第二轮排序后的数组=============");
        System.out.println(Arrays.toString(arr));



        //第三轮排序
        minIndex=2;//假设最小值的数组下标为2
        minValue=arr[2];//假设最小的值为数组下标为2的数
        for(int j=2+1;jarr[j]){//如果假设的数组下标为2的最小值比后面的数大
                minValue=arr[j];//重置最小值
                minIndex=j;//重置最小值下标
            }
        }
        //第二轮排序结果   1, 34, 119, 101
        //第三轮排序结果  1, 34, 101, 119
        if(minIndex!=2){//真正的最小值数组小标不为3，进行交换
            arr[minIndex]=arr[2];//把假设的数组下标为0的最小值（arr[2]即119）赋值给真正最小值（arr[minIndex]即101）的位置
            arr[2]=minValue;//把真正的最小值（minValue即101）赋值给数组下标为2（arr[0]即119）的位置
        }
        System.out.println("第三轮排序后的数组=============");
        System.out.println(Arrays.toString(arr));

    }
}

2、运行main函数，结果如下：

六、选择排序算法的完整示例演示

1、代码

package com.rf.springboot01.dataStructure.sort;


import java.util.Arrays;

/**
 * @description:  选择排序完整示例
 * @author: xiaozhi
 * @create: 2020-08-05 22:32
 */
public class SelectSort2 {
    public static void main(String[] args) {
        int[] arr ={101, 34, 119, 1};
        System.out.println("排序前的数组-----------------");
        System.out.println(Arrays.toString(arr));

        selectSort(arr);

        System.out.println("排序后的数组-----------------");
        System.out.println(Arrays.toString(arr));
    }

    /**
     * @Description: 选择排序完整示例
     * @Param:
     * @Author: xz
     * @return:
     * @Date: 2020/8/5 22:00
     */
    public static void selectSort(int[] arr){

        for(int i=0;i