一、导读
在众多语言所涉及到的额算法中，冒泡排序和选择排序有着不一样的地位：它们几乎是所有编程语言的学习者们都最先接触到的算法。 本篇博客将梳理这两种代码的原理和代码，并对冒泡排序进行一定的优化。二、冒泡排序
1.冒泡的示意图
首先，我们有一个数组，就在下面的图中，可能你认不出来，好吧，就是最上面的那一排格子。 “我去，这么丑！”你现在一定是这么想的。关于这个，请用理解的眼光看待。
2.窗体
让我们回到这一排格……数组上，冒泡的原理是使用一个长度为2的窗体选定数组中的两个相邻元素，根据刚刚“数组”的锻炼，相比你也找到那个窗体了。请注意窗体的作用，详细的说起来窗体有三个作用： 1）移动，窗体是移动的，它移动的速度为每一次循环移动一个索引，当窗体移动到我们规定的位置后，窗体会回到数组的前端并且重复之前的移动模式 2）圈定范围，窗体是有一个固定的长度的，这个长度是2。当然，这里有两点需要注意。 首先，窗体的长度可以是3，你完全可以用一个圈定3个数组元素的窗体并对窗体中的元素进行操作，这从代码的角度是完全可行的。但是，需要注意也是我们必须注意的是，扩大窗体的长度没有任何意义，或者更准确的表达式“没有任何正面意义”。 其次，在实际的代码中，并没有体现窗体这个东西，有的仅仅是一个可以对应我们现在所说的窗体的角标。但是，我认为用窗体这样具体的有形之物可以更容易的理解冒泡排序的原理。 3）操作圈定的范围中的数组元素 而我们所说的操作有两种，比较和交换。 可以这么说，冒泡算法就是通过窗体实现的。
如果你已经理解了什么叫做窗体，那么接下来，我们可以轻松的阐述什么是冒泡了。
3.冒泡的实现流程
好了，我们开始排序，窗体出现在数组的开头，圈定了数组的两个元素， 然后，窗体对圈定的两个元素进行操作，这些操作的结果，是将窗体中两个元素里较大的那个排到窗体的尾部，啊，也就是上面示意图中标着“大”的那一端。 实现此功能的操作包含了两个动作，首先会比较窗体中的元素，如果在窗体头部的元素大于窗体尾部的元素，我们不去管它们；反正我们交换它们的顺序。 我们现在可以理解什么是冒泡中的“泡”了，是的，窗体所圈元素中较大的就是泡。然后我们来看看它是怎么“冒”的。 窗体在进行完操作后会向数组的后方移动，然后，它圈定了数组的两个元素，注意，这两个元素中索引靠前的那个是我们前面找到的泡。 这里我不得不澄清一个概念，泡指的不是较大的元素，而是“较大”本身，我们会在接下来的阐述中进一步理解这个概念。 回到刚刚的步骤，我们重新圈定了窗体，窗体包括了刚刚的泡（“较大”），然后我们使用窗体对这两个新的元素进行操作，我们更新了泡。 这里不得不插一句，现在的泡不仅仅是刚刚比较完的两个元素之间的较大，也是我们比较过得三个元素中的较大（因为刚刚比较的双方中有一方是之前的泡，而泡等于之前的较大）。 按照这样的规则，当我们将窗体移动到数组的尾端（同时泡也一步一步的在向数组的尾部移动，因为泡始终在窗体的尾部，泡就是这么“冒”的）时，数组的状态是这样的： 窗体的尾端与数组的尾端重叠；窗体的尾端（也就是数组的尾端）中存放的是泡；泡所对应的元素是窗体移动经过的数组范围中较大的元素；最重要的，窗体走遍了整个数组。 将上面几句废话总结一下：泡中存放的是整个数组中最大的元素，并且这个元素已经存放到数组的尾部了。 接下来，我们就要将这个在数组尾部的最大元素排除掉（你当然可以不排除，这对代码的功能没有丝毫的影响，它只不过会变慢而已）然后重复上面的流程。 窗体每次从数组的头部走到尾部，都可以将最大的数装到泡里冒出来。而且，显而易见的，窗口每一轮移动都比上一轮缩短了一个单位（一个单位就是一个索引的长度）。 直到最后一轮，数组中只有一个元素是没有排序的，它的排序是可以省略的，因为对仅仅一个元素而言，它本来就是最大的（如果你非要理解成是最小的我也没办法，你赢了），这样整个数组的排序就完成了。4.代码
你一定已经晕了，没关系，我们把思路和代码结合起来看private static void maopao(int[] array) {
for (int i = 0; i < array.length-1; i++) {//每一轮冒泡
for (int j=0;j<array.length-1-i;j++){ //从数组的开头冒到不需要冒的地方
if (array[j]>array[j+1]){//比较窗体中两元素的大小
int temp =array[j+1];//如果有需要，就交换
array[j+1]=array[j];
array[j]=temp;
}//此时当前窗口的泡已经冒出来了
}//此时，当前轮的泡已经冒出来了
}//整个数组所有轮次都冒过泡了
}
5.冒泡的优化原理
你以为这样就结束了吗？不！当然没有！ 当前的冒泡排序的性能极其稳定：一轮冒一个泡，雷打不动（这真是极好的）。 有没有什么优化措施？有人想到了选择排序？不你想多了。你有没有相关冒泡真的又不要一轮一个、一轮一个的冒吗？ 答案是没必要，我们可以通过小小的改动优化冒泡的性能，使它可以实现在某些轮次一轮冒出两个泡。请注意上面那张图中红圈圈中的部分，红圈中的是一个轮次的最后，窗体尾部与数组待比较区域的尾部重合时，窗体中进行最后一次比较。 我们分析一下这次比较时发生了什么： 窗口中有两个元素，前面的是泡，后面的是还没参与到（本轮）冒泡中的元素 如果泡大于另一个元素，窗体交换两个元素，从上一个窗体位置操作来的泡被放到了当前窗体的尾部，当前轮次结束，冒出了一个泡。 而相反的，如果泡不大于另一个元素，窗体不交换两个元素，这就说明当前窗体圈定的两个元素中较大的不是上个窗体位置时的泡。 这就说明，本轮循环的泡就是当前窗体尾部的元素，这是当前轮次冒泡的结果；然后，不能忽略的是，当前窗口中头部的元素是保存在上一个窗口位置的尾部，也就是说，它是上一个窗口位置的泡。 那么还记得泡是什么吗？泡是窗体走过的路中的最大。也就是说，它是除去了本轮（和在本轮之前的轮次）冒出的泡外最大的元素，它必定是下一个窗体轮次的泡。
概括一下吧，当一个轮次中最后一次比较后两个元素没有交换顺序时，参与最后一次比较的两个元素中较大的一个是当前轮次的泡（最大值），而较小的一个是下一个轮次中的最大值，也就是说，在这个轮次中，实际上完成了两个轮次的任务。
6.冒泡优化代码
private static void maopao(int[] array) {
for (int i = 0; i < array.length-1; i++) {
for (int j=0;j<array.length-1-i;j++){
if(j==array.length-2-i)//如果现在是最后一轮比较
if(array[j]<array[j+1])//如果比较双方不换位置
i++;//我们实际上多完成了一轮任务
if (array[j]>array[j+1]){
int temp =array[j+1];
array[j+1]=array[j];
array[j]=temp;
}
}
}
}
三、选择排序
1.冒泡排序的缺点一
在上面，我们完整的分析了冒泡排序的原理和代码实现，我们冒了很长时间的泡，现在我们来谈一谈冒泡算法的缺点。 其实冒泡算法的缺点很是明显，它至少存在两个比较明显的缺点。 首先，冒泡算法的最基本操作归根到底还是比较和交换（其实只要是排序，就没有可以离开这两种操作的）。比较嘛，只要有两个数相比就好了，为什么需要规定必须是相邻的两个数进项比较呢？这里是不是很是让人纠结呢？ 那么就让我们来消除这种纠结吧。2.克服缺点一的思路
我们刚刚只是说冒泡中的“相邻比较”似乎很多余，但是没有说明作为一个缺点它缺在了哪里。 其实，说它是缺点的原因是很好理解的，效率。计算机在进行一切处理的时候都是要进行运算的，窗体的移动这也是一次运算啊（表示窗体的索引数+1），比较时我们还需要做一次索引+1 的运算以获取相邻于窗体索引的下一个索引，这也是一次运算啊。而且，我们悲哀的发现这种运算是避免不了的。窗体一动就是一次运算，不运算？行啊，窗体别动了。对应的，相邻元素一笔又是一次运算，不运算？行啊，相邻的元素别比了。 这种冗余的操作增加了Cpu的负担，降低了程序的运行效率，那么有什么可以让程序比较轻松呢？ 有一种方式，从数组中取出指定一个变量，先让这个变量等于数组中的某个元素（当然我们也可以直接指定一个静止的数组元素作为比较的一端），然后用这个变量分别比较其它元素进行比较并按照冒泡法的规则进行交换操作，这就省去了窗体移动的动作。3.克服了缺点一的代码
public static void selectSort(int[] arr)
{
for(int x=0; x<arr.length-1; x++)
{
for(int y=x+1; y<arr.length; y++)
{
if(arr[x]>arr[y])
{
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
}
}
4.冒泡排序的缺点二以及优化思路
上面的那个缺点知识冒泡排序的小缺点而已，一个更加具有影响力的缺点是它的交换，如果需要排列的集合是反序的，那么冒泡法每次比较都要进行交换操作，每次交换需要进行三步……而这么多次交换中，绝大部分都是没有用的无效操作，因为每一轮排序我们需要的有效的排序只有一次，是的，最后一次。 那么我们是不是可以只通过一次交换就能完成一轮排序中排序任务呢？我们可以，只需要知道交换的双方。我们可以轻松的锁定这个问题的答案，交换的一方是一轮结束时我们比较出来的最值，另一方是排序的轮次所指定的位置。我们可以很轻松的实现这一目标，只要我们使用一个第三方变量来存储最值的索引。5.克服了缺点二的代码
public static void selectSort_2(int[] arr)
{
for(int x=0; x<arr.length-1; x++)//指定到了第x+1个元素
{
int index = x;//极值索引
for(int y=x+1; y<arr.length; y++)
{
if(num>arr[y])
{
index = y;//仅仅是保存一个索引
}
}
if(index!=x)//当前指定的
{int temp = arr[index];arr[index] = arr[i]<span style="font-family: Arial, Helvetica, sans-serif;">};arr[i] = temp;}//交换</span><span style="white-space:pre"></span>}
}
6.这就是选择排序
当我们克服了冒泡的两个缺点后，我们发现我们的冒泡法已经面目全非了，它似乎已经变成了一种全新的方法。 是的，这就是选择排序，选择排序的最大特点就是使用第三方变量记录索引，使得每一轮比较只进行一次交换操作，是一种效率更优于冒泡排序的排序算法。然而，高效也不完全是好事，选择排序算法的高效带来了安全隐患，这种隐患发生于数组中有相同的元素时，这时的交换不能保证相同元素之间的相对顺序不变。这时因为选择排序交换操作的执行条件是索引值不等，而冒泡排序的则是比较元素的值，在相等的情况下不去交换。
------Java培训、Android培训、iOS培训、.Net培训、期待与您交流！ ------