|
冒泡排序法 |
冒泡排序法冒泡算法，在传统的c语言教科书上讲的很多，它是一种比较稳定的排序算法。大家在使用这个排序算法的时候，可以从它的名字来联想一下它的实现形式。一说到冒泡，大家首先想到的是一条小鱼在水里游着，并且“布鲁布鲁”的吐出一串串小气泡，冒到水面上。其实冒泡排序法也和小于吐泡泡一样，每次只吐出一个，并且连续不断地一个接一个吐。冒泡排序算法的中心思想，即是相邻的两个数进行比较后根据大小需求交换位置。先从最简单的两个元素的数组看起，由此进行举一反三。假设一个数组内部只有两个元素“int array = {8, 0};”。对其进行排序时，我们仅需要做一次判断即可以知道哪个元素大，哪个元素小，假设我们从小到大进行排列，那么排列出的结果就应该是“array = {0, 8};”。再看当有三个元素的数组。假设一个数组内部只有两个元素“int array = {8, 0, 1};”。那我们还是进行两两比较，第一次比较，可以得出数组应该为“array = {0, 1, 8};”，也是只需要一次比较就可以完成数组的排序。但如果数组改变一下元素的位置，即“int array = {8, 1, 0};”，那么我们再来看一下，第一次两两元素比较变成了“array = {1, 0, 8};”，因此碰到这种极端情况时，冒泡法一次比较完成不了排序，那么应该进行第二次比较，最终第二次比较我们可以得出结果“array = {0, 1, 8};”再来看看四个元素时候数组的排序，这次我们举一个极端情况，即将一个从大到小排列的数组变成由小到大的顺序排列。数组为“int array = {9, 8, 1, 0};”。那么此时第一次相邻两个元素比较可以得出“array = {8, 1, 0, 9};”，第二次相邻元素两两比较可以得出“array = {1, 0, 8, 9};”，第三次两两比较可以得出“array = {0, 1, 8, 9};”。基于上述的分析，我们可以知道，一个数组如果有n个元素需要进行排序时，其排序的极端情况应该是n-1次。具体的排序流程，如下。
冒泡排序法的流程
因此根据上述分析，我们可以写出代码如下。
接下来，我们将程序改装一下，让它在每一步相邻两个元素比较的过程打印出来，如图5-4-3所示。我们可以看到，越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同水里的小金鱼吐出的泡泡一串串慢慢浮出水面，故名“冒泡排序”。
立即学习“Java免费学习笔记（深入）”；
冒泡法排序单步打印
选择排序法
选择排序选择排序，俗称“硬着头皮排序”，当然这个“硬着头皮排序”是我给它取的名字，因为它是最最直观的排序方法，完美诠释了“暴力美学”这四个字。要理解选择排序，先想象一下小学上体育课时，老师是怎么排列队伍的。先从小朋友里面随便拉一个老师认为最矮的同学出来，让他做排头，然后依次拿其他的同学和他比较，如果比他高，就放到其后面去，比他矮就放到前面，接着再来目测第二个，以此类推。当然上面这段话是描述的体育老师内心思路。而我们对数组排序的时候，同样可以使用这种方式。我们可以先指定一个排头兵，假设我们要进行从小到大排列时，那我们先假设第一个元素为数组中最小的元素，接着分别去和剩余的其它元素比较，如果发现比它小的，那么将其自己和那个元素互换，用这种方式，只需要遍历完整个数组，就可以把最小的元素放到首个元素的位置了。如下所示。
选择排序做一次遍历比较
上图中，我们通过第一次的遍历比较，将最小的元素排列到了数组的最左端，而接下来要做的，只需要一次将剩余的9个元素进行比较，找出最小值，再放到0右边，以此类推，最后我们可以写出如下图所示的选择排序程序。
