排序算法---选择算法

基本介绍：

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

排序思想：

• 第一次从 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次，得到一个按排序码从小到大排列的有序序列。

思路分析：

• 初始状态 [8 3 2 1 7 4 6 5]
• 第一次交换完成后：[1 3 2 8 7 4 6 5]
• 第二次交换完成后：[1 23 8 7 4 6 5]
• 第三次交换完成后：[1 2 3 8 7 4 6 5]
• 第四次交换完成后：[1 2 3 4 7 8 6 5]
• 第五次交换完成后：[1 2 3 4 5 8 6 7]
• 第六次交换完成后：[1 2 3 4 5 68 7]
• 第七次交换完成后：[1 2 3 4 5 6 78]

说明：

• 选择排序一共有arr.lenth()-1轮排序
• 每一轮排序，又是一个循环，循环的规则：
  先假定当前这个数是最小的数；
  然后和后边的每个数进行比较，如果有发现有比当前更小的数，就重新确定最小的数，并得到下标；
  当遍历到数组最后时，就得到本轮的最小数和下标。
• 最后进行交换

代码实现：

package DataStructures.com.test.Sort;

import java.text.SimpleDateFormat;
import java.util.Date;

/**
 *
 */
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));

    }

    public static void SelectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++){       //假定：最小数的下标是0，最小的数是arr[0]
            int minIndex = i;
            int min = arr[i];
            for (int j = i+1; j <arr.length;j++){
                if (min > arr[j]) {//说明我们假定的最小值不是真正的最小值
                    minIndex=j;//重置最小值的下标
                    min = arr[j];//重置最小值
                }
            }

            //如果最小值的下标不等于i,说明最小值被重置过，进行交换
            if (minIndex!=i) {
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }


    }
}

本文地址：https://blog.csdn.net/weixin_43217222/article/details/107353666