选择排序算法介绍

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

选择排序算法介绍,算法与数据结构每日练习,排序算法,算法,java

算法介绍

选择排序(Selection Sort)是一种简单直观的排序算法。它的基本思想是每次从待排序的元素中选取最小(或最大)的元素,放到已排序部分的末尾,直到全部元素排序完毕。

以下是选择排序的详细步骤:

  1. 首先,在待排序序列中找到最小(或最大)的元素,并将它与序列的第一个元素进行交换。这样,该元素就被放置在已排序序列的起始位置。
  2. 接下来,在剩余的待排序序列中找到最小(或最大)的元素,将它与序列的第二个元素进行交换。这样,该元素就被放置在已排序序列的末尾位置,且已排序序列长度增加1。
  3. 重复上述步骤,直到所有元素都排列好。

以下是选择排序的示例代码实现(使用升序排序为例):

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i; // 假设当前索引对应的元素为最小值

            // 在剩余未排序的部分中找到最小值的索引
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 将最小值与当前位置交换
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        
        System.out.println("原始数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        selectionSort(arr);
        
        System.out.println("\n排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

以上代码演示了选择排序的过程。在每一轮迭代中,它找到未排序部分的最小元素,并将其与未排序部分的起始位置进行交换。通过不断缩小未排序部分的范围,直到整个数组排序完成。

选择排序的时间复杂度为O(n^2),其中n是待排序序列的长度。尽管选择排序在时间复杂度上不是最优的,但它的实现简单易理解,并且在小规模数据或部分有序的数据排序时性能较好。

算法优化

对选择排序进行一些简单的优化可以提高其性能,以下是两种常见的优化方法:

  1. 最小/最大值优化:在每一轮选择最小(或最大)元素时,可以同时记录最小值和最大值的索引,然后分别交换到已排序序列的起始位置和末尾位置。这样可以减少每轮迭代中的比较次数,从而提高效率。

  2. 优化无需交换:在每一轮找到最小(或最大)元素的索引后,并不立即进行交换操作,而是等待整个序列遍历完毕,最后再统一进行交换。这样可以减少交换操作的次数,由于交换操作需要移动数据,减少了数据的移动次数可以提高效率。

下面是基于上述两种优化方法的选择排序示例代码实现:

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            int maxIndex = i;

            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                } else if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }

            if (minIndex != i) {
                swap(arr, i, minIndex);
            }

            // 如果最大值的索引被交换到了i位置,更新maxIndex
            if (maxIndex == i) {
                maxIndex = minIndex;
            }

            if (maxIndex != n - 1) {
                swap(arr, n - 1, maxIndex);
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};

        System.out.println("原始数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        selectionSort(arr);

        System.out.println("\n排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

这些优化方法可以在某些情况下提高选择排序的性能,但需要注意的是,选择排序的时间复杂度仍然是O(n^2),因此对于大规模数据排序,更高效的排序算法如快速排序、归并排序等可能更合适。文章来源地址https://www.toymoban.com/news/detail-566600.html

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

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

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

相关文章

  • 数据结构算法--2 冒泡排序,选择排序,插入排序

    思想就是将相邻元素两两比较,当一个元素大于右侧相邻元素时,交换他们的位置,小于右侧元素时,位置不变,最终序列中的最大元素,像气泡一样,到了最右侧。 这时冒泡排序第一轮结束,数列最右侧元素9的位置可认为是一个有序区,有序区目前有一个元素. 第二轮排序

    2024年02月13日
    浏览(64)
  • 【数据结构与算法】:选择排序与快速排序

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

    2024年03月17日
    浏览(53)
  • 【数据结构】八大排序之简单选择排序算法

    🦄 个人主页 :修修修也 🎏 所属专栏 :数据结构 ⚙️ 操作环境 : Visual Studio 2022 目录 一.简单选择排序简介及思路 二.简单选择排序的代码实现 三.简单选择排序的优化 四.简单选择排序的时间复杂度分析 结语 简单选择排序算法(Simple Selection Sort) 是一种简单直观的 选择排序算

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

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

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

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

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

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

    2024年02月04日
    浏览(56)
  • 数据结构--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日
    浏览(73)
  • 【一起学数据结构与算法】几种常见的排序(插入排序、选择排序、交换排序、归并排序)

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

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

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

    2024年02月04日
    浏览(77)
  • C++基础-介绍·数据结构·排序·算法

    C++是一门风格严谨又不失自由的开发语言,提供了完整的内存管理、支持函数式编程和面向对象编程,支持模板、多继承、多实现、重载、重写等多态特性。 优势在于目前90%的操作系统、数据库、应用基础架构、硬件嵌入式等都是使用C/C++制作的,而C++是对C的标准扩展,掌握

    2024年02月03日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包