欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

排序算法---选择算法

程序员文章站 2022-07-10 21:14:05
基本介绍:选择排序也属于内部排序,是从待排序的数据中,按照指定规则选出某一元素,再按规定交换位置后达到排序的目的。排序思想:第一次从 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...

基本介绍:

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

排序思想:

  • 第一次从 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