首页 / 算法 / 算法常识——冒泡排序
算法常识——冒泡排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法常识——冒泡排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2141字,纯文字阅读大概需要4分钟。
内容图文
![算法常识——冒泡排序](/upload/InfoBanner/zyjiaocheng/1300/b764fd23e2344caea1f9b2f9f3bba58e.jpg)
前言
冒泡排序是一种通用的算法,凡是通用的,可以理解为效率不高,但是通用。
code
从小到大的排序:
static void Main(string[] args)
{
int[] intarr = new int[] {1,6,8,2,3,5,10,48,9 };
sort(intarr);
foreach(var i in intarr)
{
Console.Write(i+"\n");
}
Console.ReadKey();
}
public static void sort(int[] arr)
{
var temp = 0;
var hasSore = true;
for(var i=0;i<arr.Length-1;i++)
{
for (var j=0;j<arr.Length-1-i;j++)
{
if (arr[j] > arr[j + 1])
{
temp = arr[j+1];
arr[j + 1] = arr[j];
arr[j] = temp;
hasSore = false;
}
}
if (hasSore)
{
break;
}
}
}
这里面稍微有点难以理解的地方是如何一开始就确认:
i<arr.Length-1
j<arr.Length-1-i
先来看下冒泡排序的过程。
首先要确认i,j的意思是什么?
在这里我把i变量认为是已经排好的个数,那么其范围也就确认了,那么排好多少序后,成功呢?答案其实是arr.length-2个排序完毕,其实就不同排序了。
我们知道三个元素排序。
如果使用:
if (arr[j] > arr[j + 1])
{
temp = arr[j+1];
arr[j + 1] = arr[j];
arr[j] = temp;
hasSore = false;
}
只需要一次。假设arr.length-3排序好了,只要确认第arr.length-2个那么就确认了。
很多人第一次遇到的时候总理解为需要arr.length-1个确认好,那是因为我们理解为倒数第一个确认好,最后一个确认好。
这个其实是有公式的,为arr.length-m+1。m为一次性能够确认的值。1的意思是做好一次。
j 是该次需要多少元素排好一个元素。
1.第一步需要确认最后一个元素是最大值。
也就是说需要比较的是全部。因为j,所以比较范围是0到arr.length-1,那么j的范围是0到 arr.length-2
2.第二步需要确定倒数第二大元素是多少。
j的比较范围是0到arr.length-2,那么j的范围是0到arr.length-3,也就是确认一个后j的一个范围就不需要确认(可以解释数组缩短了),也就是 arr.length-1-i
为什么hasSore为true的时候可以break呢?因为如果顺序没有变化,那么其实已经排好了。
其实几乎达不到i=arr.length-2的情况,为何这么说呢?每循环一次,其实已经在排序了,把冒泡排序的时间排序归纳为o(n^2),也是不正确的。
继续优化
class Program
{
static void Main(string[] args)
{
int[] intarr = new int[] {1,6,8,2,3,5,10,48,9 };
sort(intarr);
foreach(var i in intarr)
{
Console.Write(i+"\n");
}
Console.ReadKey();
}
public static void sort(int[] arr)
{
var temp = 0;
var hasSore = true;
var sortEnd = arr.Length - 1;
for (var i=0;i<arr.Length-1;i++)
{
for (var j=0;j< sortEnd; j++)
{
if (arr[j] > arr[j + 1])
{
temp = arr[j+1];
arr[j + 1] = arr[j];
arr[j] = temp;
sortEnd = j;
hasSore = false;
}
}
if (hasSore)
{
break;
}
}
}
}
原理:
上面我们只要7和6换了位子就可以了,但是计算机可不会这么做。
但是我们知道其实9和10是排好了顺序的。
如何判断到最后一个交换位置的位置,那么就可以肯定后面的位置包括了后面交换的位置是已经判断了的。
就比如说这里:
加入7和6交换了位置,然后7没有和9交换位置,9也没有和10交换位置,那么是不是可以判断6到7到9到10是排序好的?
这里难以理解的是6,为什么6也被排序好了?因为6和7比较排序的时候6肯定是前面的最大值,也就是仅次于7的值。
我们比较的是6,也就是j,那么第二次判断的时候只需要去判断0-(j-1),所以可以向上面那么做。
原文:https://www.cnblogs.com/aoximin/p/12251638.html
内容总结
以上是互联网集市为您收集整理的算法常识——冒泡排序全部内容,希望文章能够帮你解决算法常识——冒泡排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。