算法学习(二)选择排序

shawsun 2020-07-04

一、引言

上一篇学习了冒泡排序,还是比较简单的一种排序,这一篇学习一下选择排序,也是基础排序的其中一种,手写一遍,加上自己的注释,理解以后写图例,其实算法也不是很高深的东西,记录一下~~

二、选择排序算法

选择算法工具类

/**
 * 选择排序算法工具类
 */
public class XuanZeUtil {

    /**
     * 选择排序【对外暴露静态方法】
     */
    public static void selectSort(int[] arr) {
        System.out.println("========排序前的数组,元素为:" + showItem(arr) + "========");
        //1、对数据循环,取出数据比较
        for (int i = 0; i < arr.length - 1; i++) {
            //2、设置min变量,用于存放较小元素的数组下标,这样当前批次比较完毕时,最终存放的就是此趟内最小的元素的下标
            int min = i;
            //3、再次对数据循环,取出数据比较【每一趟比较的元素越来越少,j = i + 1】
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            //4、内层循环结束时,如果min发生变化,则进行交换
            if (min != i) {
                //5、从新定义一个变量temp,作为交换变量用
                int temp = arr[i];
                arr[i] = arr[min];
                arr[min] = temp;
            }
            System.out.println("第【" + (i + 1) + "】次排序后的数组,元素为:" + showItem(arr) + "========");
        }
    }

    /**
     * 返回数组字符串
     */
    public static String showItem(int[] arr) {
        String itemStr = "";
        if (null != arr) {
            itemStr = "【 ";
            for (int item : arr) {
                itemStr = itemStr + " " + item;
            }
            itemStr += " 】";
        }
        return itemStr;
    }

}

测试类

import algorithm.XuanZeUtil;

/**
 * 选择排序工具测试类
 */
public class XuanZeTest {
    public static void main(String[] args) {
        //1、设置乱序数组
        int[] arr = {1, 8, 3, 6, 9, 4, 5};
        //2、调用选择排序工具类
        XuanZeUtil.selectSort(arr);
    }
}

算法学习(二)选择排序

解析

基本思想:每一趟从待排序的数据元素中选择最小(或最大)的一个元素作为首元素,直到所有元素排完为止,简单选择排序是不稳定排序。

  时间复杂度:O(n2)

  图解:

算法学习(二)选择排序

  图中可看出,选择排序有以下特点:

  • 每次排序过后,下一轮排序所需要对比的元素都会减少1
  • 总共会经历n - 1次数组遍历,才最终完成排序过程,每次遍历一共比较 n - i -1 次(n为数组长度)

相关推荐