排序算法:选择排序

这篇具有很好参考价值的文章主要介绍了排序算法:选择排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

选择排序的思想是:双重循环遍历数组,每经过一轮比较,找到最小元素的下标,将其交换至首位。

public static void selectionSort(int[] arr) {
    int minIndex;
    for (int i = 0; i < arr.length - 1; i++) {
        minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[minIndex] > arr[j]) {
                // 记录最小值的下标
                minIndex = j;
            }
        }
        // 将最小元素交换至首位
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

        选择排序就好比第一个数字站在擂台上,大吼一声:“还有谁比我小?”。剩余数字来挨个打擂,如果出现比第一个数字小的数,则新的擂主产生。每轮打擂结束都会找出一个最小的数,将其交换至首位。经过 n-1 轮打擂,所有的数字就按照从小到大排序完成了。

        现在让我们思考一下,冒泡排序和选择排序有什么异同?

相同点:

  • 都是两层循环,时间复杂度都为  O(n²);
  • 都只使用有限个变量,空间复杂度  O(1);

不同点:

  • 冒泡排序在比较过程中就不断交换;而选择排序增加了一个变量保存最小值 / 最大值的下标,遍历完成后才交换,减少了交换次数。

事实上,冒泡排序和选择排序还有一个非常重要的不同点,那就是:

  • 冒泡排序法是稳定的,选择排序法是不稳定的。

想要理解这点不同,我们先要知道什么是排序算法的稳定性。

排序算法的稳定性

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i] = r[j],且 r[i] 在 r[j] 之前,而在排序后的序列中,r[i] 仍在 r[j] 之前,则称这种排序算法是稳定的;否则称为不稳定的。

        理解了稳定性的定义后,我们就能分析出:冒泡排序中,只有左边的数字大于右边的数字时才会发生交换,相等的数字之间不会发生交换,所以它是稳定的。

        而选择排序中,最小值和首位交换的过程可能会破坏稳定性。比如数列:[2, 2, 1],在选择排序中第一次进行交换时,原数列中的两个 2 的相对顺序就被改变了,因此,我们说选择排序是不稳定的。

        那么排序算法的稳定性有什么意义呢?其实它只在一种情况下有意义:当要排序的内容是一个对象的多个属性,且其原本的顺序存在意义时,如果我们需要在二次排序后保持原有排序的意义,就需要使用到稳定性的算法。

        举个例子,如果我们要对一组商品排序,商品存在两个属性:价格和销量。当我们按照价格从高到低排序后,要再按照销量对其排序,这时,如果要保证销量相同的商品仍保持价格从高到低的顺序,就必须使用稳定性算法。

        当然,算法的稳定性与具体的实现有关。在修改比较的条件后,稳定性排序算法可能会变成不稳定的。如冒泡算法中,如果将「左边的数大于右边的数,则交换」这个条件修改为「左边的数大于或等于右边的数,则交换」,冒泡算法就变得不稳定了。

        同样地,不稳定排序算法也可以经过修改,达到稳定的效果。思考一下,选择排序算法如何实现稳定排序呢?

        实现的方式有很多种,这里给出一种最简单的思路:新开一个数组,将每轮找出的最小值依次添加到新数组中,选择排序算法就变成稳定的了。

        但如果将寻找最小值的比较条件由arr[minIndex] > arr[j]修改为arr[minIndex] >= arr[j],即使新开一个数组,选择排序算法依旧是不稳定的。所以分析算法的稳定性时,需要结合具体的实现逻辑才能得出结论,我们通常所说的算法稳定性是基于一般实现而言的。

二元选择排序

        选择排序算法也是可以优化的,既然每轮遍历时找出了最小值,何不把最大值也顺便找出来呢?这就是二元选择排序的思想。

        使用二元选择排序,每轮选择时记录最小值和最大值,可以把数组需要遍历的范围缩小一倍。

public static void selectionSort2(int[] arr) {
    int minIndex, maxIndex;
    // i 只需要遍历一半
    for (int i = 0; i < arr.length / 2; i++) {
        minIndex = i;
        maxIndex = i;
        for (int j = i + 1; j < arr.length - i; j++) {
            if (arr[minIndex] > arr[j]) {
                // 记录最小值的下标
                minIndex = j;
            }
            if (arr[maxIndex] < arr[j]) {
                // 记录最大值的下标
                maxIndex = j;
            }
        }
        // 如果 minIndex 和 maxIndex 都相等,那么他们必定都等于 i,且后面的所有数字都与 arr[i] 相等,此时已经排序完成
        if (minIndex == maxIndex) break;
        // 将最小元素交换至首位
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
        // 如果最大值的下标刚好是 i,由于 arr[i] 和 arr[minIndex] 已经交换了,所以这里要更新 maxIndex 的值。
        if (maxIndex == i) maxIndex = minIndex;
        // 将最大元素交换至末尾
        int lastIndex = arr.length - 1 - i;
        temp = arr[lastIndex];
        arr[lastIndex] = arr[maxIndex];
        arr[maxIndex] = temp;
    }
}

        我们使用 minIndex 记录最小值的下标,maxIndex 记录最大值的下标。每次遍历后,将最小值交换到首位,最大值交换到末尾,就完成了排序。

        由于每一轮遍历可以排好两个数字,所以最外层的遍历只需遍历一半即可。

        二元选择排序中有一句很重要的代码,它位于交换最小值和交换最大值的代码中间:

if (maxIndex == i) maxIndex = minIndex;

        这行代码的作用处理了一种特殊情况:如果最大值的下标等于 i,也就是说 arr[i] 就是最大值,由于 arr[i] 是当前遍历轮次的首位,它已经和 arr[minIndex] 交换了,所以最大值的下标需要跟踪到 arr[i] 最新的下标 minIndex。

二元选择排序的效率

        在二元选择排序算法中,数组需要遍历的范围缩小了一倍。那么这样可以使选择排序的效率提升一倍吗?

        从代码可以看出,虽然二元选择排序最外层的遍历范围缩小了,但 for 循环内做的事情翻了一倍。也就是说二元选择排序无法将选择排序的效率提升一倍。但实测会发现二元选择排序的速度确实比选择排序的速度快一点点,它的速度提升主要是因为两点:

  • 在选择排序的外层 for 循环中,i 需要加到 arr.length - 1 ,二元选择排序中 i 只需要加到 arr.length / 2;
  • 在选择排序的内层 for 循环中,j 需要加到 arr.length ,二元选择排序中 j 只需要加到 arr.length - i;

我们不妨发扬一下极客精神,一起来做一个统计实验:

public class TestSelectionSort {
    public static void selectionSort(int[] arr) {
        int countI = 0;
        int countJ = 0;
        int countArr = 0;
        int minIndex;
        countI++;
        for (int i = 0; i < arr.length - 1; i++, countI++) {
            minIndex = i;
            countJ++;
            for (int j = i + 1; j < arr.length; j++, countJ++) {
                if (arr[minIndex] > arr[j]) {
                    // 记录最小值的下标
                    minIndex = j;
                }
                countArr++;
            }
            // 将最小元素交换至首位
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        int count = countI + countJ + countArr;
        System.out.println("selectionSort: countI = " + countI + ", countJ = " + countJ + ", countArr = " + countArr + ", count = " + count);
    }

    public static void selectionSort2(int[] arr) {
        int countI = 0;
        int countJ = 0;
        int countArr = 0;
        int minIndex, maxIndex;
        countI++;
        // i 只需要遍历一半
        for (int i = 0; i < arr.length / 2; i++, countI++) {
            minIndex = i;
            maxIndex = i;
            countJ++;
            for (int j = i + 1; j < arr.length - i; j++, countJ++) {
                if (arr[minIndex] > arr[j]) {
                    // 记录最小值的下标
                    minIndex = j;
                }
                if (arr[maxIndex] < arr[j]) {
                    // 记录最大值的下标
                    maxIndex = j;
                }
                countArr += 2;
            }
            // 如果 minIndex 和 maxIndex 都相等,那么他们必定都等于 i,且后面的所有数字都与 arr[i] 相等,此时已经排序完成
            if (minIndex == maxIndex) break;
            // 将最小元素交换至首位
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
            // 如果最大值的下标刚好是 i,由于 arr[i] 和 arr[minIndex] 已经交换了,所以这里要更新 maxIndex 的值。
            if (maxIndex == i) maxIndex = minIndex;
            // 将最大元素交换至末尾
            int lastIndex = arr.length - 1 - i;
            temp = arr[lastIndex];
            arr[lastIndex] = arr[maxIndex];
            arr[maxIndex] = temp;
        }
        int count = countI + countJ + countArr;
        System.out.println("selectionSort2: countI = " + countI + ", countJ = " + countJ + ", countArr = " + countArr + ", count = " + count);
    }
}

        在这个类中,我们用 countI 记录 i 的比较次数,countJ 记录 j 的比较次数,countArr 记录 arr 的比较次数,count 记录总比较次数。

测试用例:

import org.junit.Test;

import java.util.ArrayList;

public class UnitTest {
    @Test
    public void test() {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i <= 1000; i++) {
            // ArrayList 转 int[]
            int[] arr = list.stream().mapToInt(Integer::intValue).toArray();
            System.out.println("*** arr.length = " + arr.length + " ***");
            TestSelectionSort.selectionSort(arr);
            TestSelectionSort.selectionSort2(arr);
            list.add(i);
        }
    }
}

这里列出部分测试结果:

排序算法:选择排序,算法相关,算法,数据结构,排序算法

        可以看到,二元选择排序中, arr 数组的比较次数甚至略高于选择排序的比较次数,整体是相差无几的。只是 i 和 j 的比较次数较少,正是在这两个地方提高了效率。

        并且,在二元选择排序中,我们可以做一个剪枝优化,当 minIndex == maxIndex 时,说明后续所有的元素都相等,就好比班上最高的学生和最矮的学生一样高,说明整个班上的人身高都相同了。此时已经排序完成,可以提前跳出循环。通过这个剪枝优化,对于相同元素较多的数组,二元选择排序的效率将远远超过选择排序。

和选择排序一样,二元选择排序也是不稳定的。文章来源地址https://www.toymoban.com/news/detail-668319.html

到了这里,关于排序算法:选择排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】:选择排序与快速排序

    🔥 个人主页 : Quitecoder 🔥 专栏 :数据结构与算法 我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:腾讯云 欢迎来到排序的第二个部分:选择排序与快速排序! 选择排序是一种简单直观的比较排序算法。该算法的基本思想是在每一轮中选出当前未排序部分的最

    2024年03月17日
    浏览(51)
  • 【数据结构】排序算法(一)—>插入排序、希尔排序、选择排序、堆排序

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.直接插入排序 2.希尔排序 3.直接选择排序 4.堆排序 本篇文章博主将介绍排序算法中的插入排序:直接

    2024年02月08日
    浏览(47)
  • 【数据结构】——排序算法的相关习题

    1、直接插入排序 1、对n个元素进行直接插入排序,需要进行()趟处理。 A、n B、n+1 C、n-1 D、2n 解析: (C) 直接插入排序是将要排序的序列按照的大小插入至已排好序的子序列中,一直进行直到整个序列有序,所以对n个元素进行直接插入排序,一共插入元素n-1次,

    2024年02月03日
    浏览(42)
  • 【数据结构】常见排序算法——常见排序介绍、选择排序(直接选择排序、堆排序)交换排序(冒泡排序)

      选择排序是一种简单但不高效的排序算法,其基本思想是从待排序的数据中选择最小(或最大)的元素放到已排序的数据末尾。具体操作步骤如下: (1)找到数据中最小的元素,并把它交换到第一个位置; (2)在剩下未排序的元素中找到最小的元素,并把它交换到已排

    2024年02月04日
    浏览(52)
  • 直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序——“数据结构与算法”

    各位CSDN的uu们你们好呀,今天小雅兰的内容是数据结构与算法啦,是排序!!!下面,让我们进入七大排序的世界吧!!! 排序:所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在

    2024年02月15日
    浏览(65)
  • 【数据结构与算法】单链表的排序算法(选择,冒泡,递归)

    目录 选择排序 冒泡排序 快速排序 合并两条链表并排序 选择排序 链表的选择排序思想与数组的排序类似,但是链表需要先找到里面最小或者最大的值,然后将这个值用改链语句进行操作 我们先看这个改链语句的操作(min是笔者打错了应该是max,但是图已经画好了就没有改)

    2024年02月04日
    浏览(55)
  • 数据结构--7.2.1排序算法(冒泡、直接选择、直接插入)

            假设含有n个记录的序列为{r1,r2,……,rn},其相应的分别为{K1,K2,……,Kn},需确定1,2,3,……,n的一种排序p1,p2,p3,……,pn;使其相应的满足kp1=kp2=kp3=kp4=……=kpn非递减(或非递增)关系,即使得序列称为一个按有序得序列{rp1,rp2,

    2024年02月07日
    浏览(69)
  • 【一起学数据结构与算法】几种常见的排序(插入排序、选择排序、交换排序、归并排序)

    排序是计算机内经常进行的一种操作,其目的是将一组 “无序” 的记录序列调整为 “有序” 的记录序列。分 内部排序 和 外部排序 ,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能

    2023年04月09日
    浏览(44)
  • 【数据结构】详解七大排序算法(直接插入排序、希尔排序、直接选择排序、堆排序、冒泡排序、快速排序)

    1、基本思想    把待排序的数按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所以的记录插入完为止,得到一个新的有序序列。    实际中我们玩扑克牌时,就用到了插入排序的思想 基本步骤:    当插入第i个元素时,前面的arr[0]、arr[2]…arr

    2024年02月04日
    浏览(72)
  • 【数据结构】【算法】二叉树、二叉排序树、树的相关操作

    树结构是以分支关系定义的一种层次结构,应用树结构组织起来的数据,逻辑上都具有明显的层次关系。 操作系统中的文件管理系统、网络系统中的域名管理、数据库系统中的索引管理等都使用了树结构来组织和管理数据。 树 Tree 是由n个节点组成的有限集合。在任意一颗非

    2024年02月04日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包