首页 > 其他分享 >第三章 数组(5)

第三章 数组(5)

时间:2024-09-03 21:25:12浏览次数:10  
标签:位置 第三章 元素 冒泡排序 算法 数组 排序

3.5 数组排序算法

        对数据进行升序或降序排列是日常工作中经常遇到的需求,这就要求开发者必须掌握基本的数据排序算法,本节将介绍冒泡排序、选择排序和Arrays类提供的排序方法。

        3.5.1 冒泡排序

        冒泡排序是最常用的数组排序算法之一,它排序数组元素的过程通常按照“小数往前放,大数往后放”这样类似水中气泡往上升的动作,所以称作冒泡排序。它以简洁的思想与实现方法而备受青睐,是初学者最先接触的一个排序算法。

        (1)基本思路

        冒泡排序的基本思路是对比相邻的元素值,如果满足条件就交换元素值,把较小的元素移动到数组前面,把大的元素移动到数组后面(也就是交换两个元素的位置),这样较小的元素就像气泡一样从底部上升到顶部。

        (2)计算过程

        冒泡算法由双层循环实现,其中外层循环用于控制排序轮数,总轮数通常等于数组长度减1,因为最后一次循环只剩下一个数组元素,不需要对比。而内层循环主要用于对比数组中每个临近元素的大小,以确定是否交换位置,对比和交换次数以排序轮数而减少。例如,一个拥有6个元素的数组,在排序过程中每一次循环的排序过程和结果如下图所示,绿色的数字处于正在进行比较的状态,蓝色的数字表示处于等待排序的状态,黑色的数字表示已经完成排序的状态。

        算法完成第一轮比较后,把最大的元素值95移动到了最下面(相应的比95小的元素向前移动,类似气泡上升),当95下沉到底部之后就不会再参与下一轮的比较。按照这样的逻辑,每一轮比较之后,都会有一个最大元素下沉到底部。 当所有的元素都“沉底”之后,即得到升序排列的数组。

        3.5.2 直接选择排序

        直接选择排序算法属于选择排序的一种,它的排序速度要比冒泡排序快一些,也是常用的排序算法。

        (1)基本思路

        直接选择排序的基本思路是先指定一个排序位置(例如数组末尾),让指定位置的元素与其他元素逐一对比,如果知道最大或最小值就交换两个位置的值。

        直接选择排序与冒泡排序是有区别的。直接选择排序不是交换相邻元素,而是把满足条件的元素与指定的排序位置交换(如第一个元素与最后一个元素交换),这样排序好的位置逐渐扩大,最后整个数组都成为已排序好的格式。

        与冒泡排序相比,直接选择排序的交换次数要少很多,所以速度会快些。

        (2)计算过程

        以升序排列为例,算法会找出数组中值最大的元素,将值最大的元素与数组最后一个元素交换位置。例如,一个拥有6个元素的数组,在排序过程中每一次比较的过程和结果如图3所示,蓝色的数字表示等待比较的状态,黑色的数字表示已经完成排序的状态。在第一次比较的过程中,先找到了最大值63,再将63这个元素与最后一个元素互换位置, 完成互换之后,63的位置就固定了,不再参与下一次比较。第二次比较过程中,先找到了最大值24,再将24这个元素与当前最后一个元素互换位置,完成互换之后,24的位置就固定了。依此类推,每一次比较之后都会将最大的元素放在数组末尾。

        算法比较的次数为数组长度减1,因为最后一次比较时,只剩下两个等待比较的元素,完成这两个元素的比较之后,整个数组就完成了排序。

        3.5.3 反转排序

        顾名思义,反转排序就是以相反的顺序将原有数组的内容重新排序。反转排序算法在程序开发中也经常使用。

        (1)基本思路

        反转排序的思路非常简单,也很好理解,其实现思路就是将数组的第一个元素和最后一个元素进行替换,将第二个元素和倒数第二个元素进行替换,以此类推,直到将数组中的所有元素进行替换。

        反转排序是对数组两边的元素进行替换,所以for循环只需要循环数组长度的半数次。

标签:位置,第三章,元素,冒泡排序,算法,数组,排序
From: https://blog.csdn.net/qq_62387839/article/details/141872035

相关文章

  • 第三章 数组 课后训练(3)
            训练5鸡蛋装箱    某公司准备好十个包装箱,每箱装60枚鸡蛋。由于机器故障,每箱少装了2枚鸡蛋,使用数组的相关知识体现该过程。publicstaticvoidmain(String[]args){intarr[][]=newint[10][58];//一共十个箱子,每个箱子应装60个,现在少......
  • 请问结构体数组是如何进行定义的呢?定义方法分为两种,第一种是声明和赋值分开进行的。第
    问题描述:根据下列代码回答下列问题。//Createdby黑马程序员.#include"iostream"usingnamespacestd;intmain(){structStudent{stringname;intage;stringgender;};structStudentarr[3];//结构体......
  • 面试最常见算法3—数组
    1.二维数组螺旋打印给定一个二维数组 array,请返回「螺旋遍历」该数组的结果。螺旋遍历:从左上角开始,按照 向右、向下、向左、向上 的顺序 依次 提取元素,然后再进入内部一层重复相同的步骤,直到提取完所有元素。示例1:输入:array=[[1,2,3],[8,9,4],[7,6,5]]输出:[1,2,3,4,5,6,7,......
  • C语言指针的进阶理解——指针数组
    //整型数组 //顾名思义是存放整型类型的元素的数组 intarr1[]={1,2,3,4,5};//arr内元素的类型是int //字符数组 //顾名思义是存放字符类型元素的数组 chararr2[]={'a','b','c'};//arr内元素的类型是char那么指针数组你是不是也能推算出来它大概的模样了,差不......
  • 算法与数据结构——二叉树数组表示
    二叉树数组表示在链表表示下,二叉树的存储单元为节点TreeNode,节点之间通过指针相连接。同前面的队列或栈,二叉树同样可以使用数组来表示。表示完美二叉树给定一棵完美二叉树,我们将所有节点按照层序遍历的顺序存储在一个数组中,则每个节点都对应唯一的数组索引。按照层序遍历的特......
  • Go 必知必会:探索 Go 语言中的数组和切片深入理解顺序集合
    文末有面经共享群在Go语言的丰富数据类型中,数组和切片是处理有序数据集合的强大工具,它们允许开发者以连续的内存块来存储和管理相同类型的多个元素。无论是在处理大量数据时的性能优化,还是在实现算法时对数据结构的需求,数组和切片都扮演着至关重要的角色。Go语言中的数组在......
  • 代码随想录算法训练营|Day01 LeetCode 704.二分查找,27.移除元素,977.有序数组的平方
    数组理论基础数组是存放在连续空间上的相同类型数据的集合数组的元素是不能删的,只能覆盖704.二分查找LeetCode:704.有序数组的平方classSolution{public:intsearch(vector<int>&nums,inttarget){intlength=nums.size();inti=0......
  • 代码随想录算法训练营,9月2日 | 242.有效的字母异位词,349. 两个数组的交集,202. 快乐数,1
    哈希表理论基础1.根据关键码的值而直接进行访问的数据结构(直白来讲其实数组就是一张哈希表,哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素);2.哈希表都是用来快速判断一个元素是否出现集合里;3.哈希函数:把值对应到哈希表的函数;哈希碰撞:映射到哈希表同一个索引......
  • [JS] 数组空位与遍历方法
    当数组中存在空位时,遍历数组需要选择合适的方法,不同的方法可能返回不同的结果。示例数组:constarr=[1,2,,3,4];数组空位不会影响数组长度,arr的长度是5。for循环最朴素的for循环会遍历到数组的每一位,对于空位,访问时返回undefined。for(leti=0;i<arr.length;i++......
  • [JS] 数组空位与遍历方法
    当数组中存在空位时,遍历数组需要选择合适的方法,不同的方法可能返回不同的结果。示例数组:constarr=[1,2,,3,4];数组空位不会影响数组长度,arr的长度是5。for循环最朴素的for循环会遍历到数组的每一位,对于空位,访问时返回undefined。for(leti=0;i<arr.length;i++......