《数据结构与算法之选择排序（Java实现）》

云丶言 2021-05-29

154

说在前头：本人为大二在读学生，书写文章的目的是为了对自己掌握的知识和技术进行一定的记录，同时乐于与大家一起分享，因本人资历尚浅，能力有限，文章难免存在一些错漏之处，还请阅读此文章的大牛们见谅与斧正。若在阅读时有任何的问题，也可通过评论提出，本人将根据自身能力对问题进行一定的解答。

前言

—

在前面的文章中，我们谈论了冒泡排序算法。冒泡排序算法有个很大的缺点就是：每一轮对比时总是有多个数据发生位置的变化，而这种变化无法确定数据的最终排序位置，需要每一轮经过都多次替换，数据交换频率太高，算法效率较低。

选择排序算法可以避免这种多次交换数据的低效率工作，其算法时间复杂度为O（N2），虽然与冒泡排序算法的时间复杂度处于同一量级，但选择排序算法大大减小了数据交换的频率，排序效率会比冒泡排序快的多。

—

算法思想

选择排序的算法思想：其思想重点在于“选择”，从左往右对数据进行比较，从排序好的数组中选择最小的值与左边第一个数据进行位置的互换，已经被选择的数不再进行下一轮的“选择”，以此往复，直到数据排序完成。（如下图所示）

—

具体实现代码

Select.java

package com.bosen.select;


/**
 * <p>选择排序算法</p>
 * @author Bosen 2021/5/28 10:29
 */
public class Select {


    /*
     * 待排序的数组
     */
    private int[] array;
    
    /*
     * 未排序的数据个数
     */
    private int length;


    /*
     * 最小数的下标
     */
    private int minIndex;


    private int temp;


    public Select(int[] array) {
        this.array = array;
        this.minIndex = 0;
        this.length = array.length;
    }


    public void sort() {
        display("初始状态：");
        for (int i=0; i<length-1; i++) {
            minIndex = i;
            for (int j=i+1; j<length; j++) {
                // 当前数据更小，进行记录
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {// 执行数据位置的交换操作
                temp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = temp;
            }
            display("第"+(i+1)+"轮比较：");
        }
    }
    
    /*
     * 打印排序信息
     */
    public void display(String msg) {
        System.out.print(msg);
        for (int i : array) {
            System.out.print("\t"+i);
        }
        System.out.println();
    }
}

Test.java

package com.bosen.select;


public class Test {
    public static void main(String[] args) {
        int[] array = {5, 7, 9, 4, 11, 10};
        Select select = new Select(array);
        select.sort();
    }
}

输出结果：

—

算法优化

传统的选择排序算法都是每一轮只“选择”最小或最大的数据，但为了减少遍历的次数，我们可以在每一轮比较时，同时选择最大和最小的数据，这样遍历的成本就缩小了一半。

—

优化后的代码

package com.bosen.select;


/**
 * <p>选择排序算法</p>
 * @author Bosen 2021/5/28 10:29
 */
public class Select {


    /*
     * 待排序的数组
     */
    private int[] array;
    
    /*
     * 未排序的数据个数
     */
    private int length;


    /*
     * 最小数的下标
     */
    private int minIndex;


    /*
     * 最大数的下标
     */
    private int maxIndex;


    private int temp;


    public Select(int[] array) {
        this.array = array;
        this.minIndex = 0;
        this.length = array.length;
    }


    public void sort() {
        display("初始状态：");
        for (int i=0; i<length/2; i++) {
            minIndex = i;
            maxIndex = i;
            for (int j=i+1; j<length-i; j++) {
                // 当前数据更小，进行记录
                if (array[minIndex] > array[j]) {
                    minIndex = j;
                } else if (array[maxIndex] < array[j]) {
                    maxIndex = j;
                }
            }
            if (minIndex != i) {// 执行数据位置的交换操作
                temp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = temp;
                // 如果max指向当前数据，则认为当前数据同时为最大和最小的值
                if (maxIndex == i) {
                    maxIndex = minIndex;
                }
            }
            if (maxIndex != length-1-i) {
                temp = array[length-1-i];
                array[length-1-i] = array[maxIndex];
                array[maxIndex] = temp;
            }
            display("第"+(i+1)+"轮比较：");
        }
    }
    
    /*
     * 打印排序信息
     */
    public void display(String msg) {
        System.out.print(msg);
        for (int i : array) {
            System.out.print("\t"+i);
        }
        System.out.println();
    }
}

输出结果：

总结

—

此篇文章，向大家介绍了选择排序算法的基本算法思想，具体代码实现示例，并对算法进行一定的优化。希望此篇文章对您有所帮助。

👇长按二维码关注

java

文章转载自云丶言，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。