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