手把手教你搞懂冒泡排序和选择排序
冒泡排序
原理:
从头(左边)开始比较每一对相邻的元素,如果第1个比第2个大,就交换它们的位置,执行完一轮后,最末尾(最右边)就是最大的元素。
举例:
假设存在数组nums={6,8,2,9,4},对nums数组进行排序
从左往右开始,拿出两个元素进行对比,出现两种情况:
1.左边元素 <= 右边元素,不变
2.左边元素 > 右边元素,交换他们的位置(这里可以写成>=吗?不行,因为会造成排序不稳定)
接下来就是新的一轮排序,逻辑跟上图的流程是一样的,不同的是会将最大的元素排除在外,不用进行比较。
手撕代码:
/* 没有使用过优化策略的冒泡排序 */ public class BubbleSort1 { //测试数据 public static int[] nums = {4,1,7,11,9,55}; //main方法 public static void main(String[] args){ //这个for循环每循环完一次,end--,说明就把最大的元素给选出来了 for (int end = nums.length - 1; end > 0; end--){ for (int begin = 1; begin <= end; begin++){ if(nums[begin] < nums[begin - 1]){ //每当发现左边的元素大于右边的元素 //交换元素 int temp = nums[begin]; nums[begin] = nums[begin - 1]; nums[begin - 1] = temp; } } } //打印验证结果 for(int num : nums){ System.out.print(num+"_"); } } }
时间复杂度为O(n^2),
也就是n的平方,不过这是平均时间复杂度
存在最好时间复杂度O(n)
,那就是数组本来就有序,也就是说只扫描一遍就行了。
优化策略:
由于存在部分有序的情况,例如nums数组为{8,5,2,10,11,12},也就是说10,11,12都没有比较的必要了
优化代码:
/* 使用过优化策略的冒泡排序 */ public class BubbleSort1 { public static int[] nums = {4,1,7,11,9,55}; public static void main(String[] args){ for (int end = nums.length - 1; end > 0; end--){ int sortIndex = 1; //记录最后一次交换位置 for (int begin = 1; begin <= end; begin++){ if(nums[begin] < nums[begin - 1]){ int temp = nums[begin - 1]; nums[begin - 1] = nums[begin]; nums[begin] = temp; sortIndex = begin; } end = sortIndex; } } for(int num : nums){ System.out.print(num+"_"); } } }
选择排序
原理:
从数组中找到最大的元素,然后与末尾(最右边)的元素交换位置,执行完一轮后,末尾(最右边)的那个元素就是最大的元素。
举例:
假设存在数组nums={5,8,1,9,3},对nums数组进行排序,准备一个maxIdex代表当前最大元素的下标
接下来就是新的一轮排序,逻辑跟上图的流程是一样的,不同的是会将最大的元素排除在外,不用进行比较。
手撕代码:
/** * 选择排序 */ public class SelectionSort { //测试数据 private static int[] nums = {6,3,2,8,9}; //main方法 public static void main(String[] args){ //这个for循环每循环完一次,end--,说明就把最大的元素给选出来了 for(int end = nums.length - 1; end > 0; end--){ int maxIndex = 0; //假设下标0是数组中最大元素 for(int begin = 1; begin <= end; begin++){ //从左往右开始比较 if(nums[maxIndex] < nums[begin]){ //发现存在一个元素大于假设最大元素 maxIndex = begin; //更改最大元素索引 } } //最右边一个元素和最大值元素交换位置 int temp = nums[maxIndex]; nums[maxIndex] = nums[end]; nums[end] = temp; } //打印结果 for(int num : nums){ System.out.print(num+"_"); } } }
总结
本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注猪先飞的更多文章!
相关文章
- 这篇文章主要为大家详细介绍了js实现数组冒泡排序、快速排序的原理,感兴趣的小伙伴们可以参考一下...2016-03-10
- 本文给大家汇总介绍了几个个人收藏的JavaScript实现冒泡排序的代码,都是非常的不错,有需要的小伙伴可以参考下...2016-06-12
- 这篇文章主要介绍了VC++实现选择排序算法简单示例,代码简洁易懂,有助于读者对数据结构与算法的学习,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了c# 冒泡排序算法,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了GOLANG版的冒泡排序和快速排序分享,需要的朋友可以参考下...2020-05-11
- 这篇文章主要介绍了C语言对数组元素进行冒泡排序的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04
- 这篇文章主要介绍了C++选择排序算法实例,本文先是介绍了什么是选择排序,然后给出了实现代码,需要的朋友可以参考下...2020-04-25
- 冒泡排序和快速排序算法在开发应用中各有优点了,下面我们来看几个关于php排序的几个例子。 使用PHP描述冒泡排序和快速排序算法,对象可以是一个数组。 使用PHP描...2016-11-25
- c语言实现插入排序、冒泡排序、选择排序、快速排序、堆排序、归并排序、希尔排序示例,需要的朋友可以参考下...2020-04-25
- 冒泡排序我们排序算法中的许多中的其中一样了,这里我们一起来了解一下php实现冒泡排序实现方法与原理,具体如下。 一个程序应包括: 对数据的描述:在程序中要指定数...2016-11-25
- 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。...2020-04-25
- 这篇文章主要介绍了堆排序算法(选择排序改进),有需要的朋友可以参考一下...2020-04-25
PHP常用排序算法实例小结【基本排序,冒泡排序,快速排序,插入排序】
小编推荐的这篇文章介绍了PHP常用排序算法实例小结,基本排序,冒泡排序,快速排序,插入排序,非常实用,有兴趣的同学快来看看吧。 代码如下复制代码classbevin{public$pub...2017-07-06- 这篇文章主要介绍了c#冒泡排序示例分享,需要的朋友可以参考下...2020-06-25
- 这里给大家介绍的是通过某个方法实现判断命令行中输入的数字是几个,这样再用冒泡法排序的时候就不用担心输入的是几个数字,用到的知识主要是冒泡法排序...2020-04-25
- 冒泡排序为最基本的排序算法之一,其时间复杂度为O(n^2),这里我们就来简单看一下冒泡排序算法及Ruby版的简单实现,首先还是先来了解算法原理:...2020-06-30
- 冒泡排序是php中众多排序中的一个最简单的排序方法了下面一聚教程小伙伴就同各位介绍一个冒泡排序的例子,希望能帮助到各位。 冒泡排序简介: 冒泡排序(Bubble Sort),是...2016-11-25
- 这篇文章主要介绍了c#冒泡排序算法示例,需要的朋友可以参考下...2020-06-25
- 冒泡排序是一种计算机科学领域的较简单的排序算法,这篇文章主要介绍了c++冒泡排序示例,需要的朋友可以参考下...2020-04-25
- 本篇文章是对使用c语言实现冒泡排序,选择排序,快速排序的代码进行了详细的分析介绍,需要的朋友参考下...2020-04-25