Home 算法 选择排序(Selection Sort)

选择排序(Selection Sort)

0 77

2、选择排序(Selection Sort)

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

  • 初始状态:无序区为R[1..n],有序区为空;
  • 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
  • n-1趟结束,数组有序化了。

2.2 动图演示

 

 

import java.util.Arrays;
import java.util.Random;

/**
 * @Author Chengzhi
 * @Date 2021/9/3 15:50
 * @Version 1.0
 *
 * 选择排序实现
 */
public class SelectionSort {

    public static void main(String[] args) {
        //生成随机数组
        Random rd = new Random();
        int[] num = new int[10];
        for (int i = 0; i < 10; i++) {
            num[i] = rd.nextInt(100) + 1;
        }
        System.out.println(Arrays.toString(num));
        //进行选择排序
        SelectionSort(num);
        System.out.println(Arrays.toString(num));
    }
    private static int[] SelectionSort(int[] num) {
        // 选择排序的工作原理:
        // 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
        // 然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
        // 以此类推,直到所有元素均排序完毕。 
        int i = 0;
        int j = 0;
        int min;
        int temp = 0;
        for(i = 0;i < num.length - 1;i++){//已排序序列下标;
            min = i;
            for(j = i + 1;j < num.length;j++){//找到最小的元素
                if(num[j] < num[min]){
                    min = j ;//记住下标即可;
                }
            }
            //交换
            temp = num[min];
            num[min] = num[i];
            num[i] = temp;
        }
        return num;
    }
}

SIMILAR ARTICLES

发表评论

发表评论