课时29：数组排序案例分析
摘要：本次分享的主题是数组排序案例分析。主要分为一个部分：数组排序分析
接下来看一个经典的案例，即数组排序。数组排序是指将一个杂乱的数组按照特定的顺序进行排列。虽然数组排序听起来简单，但实际上它总是通过一个基础的模型来完成的。例如在本次讲解中先来实现一个升序排序的方式。仔细观察一下排序的处理过程。
那么这个代码应该怎么写？可以这样写。比如现在来分析一下数组排序的代码。现在先对数组排序进行简短的分析，然后再继续往下讲。首先说到数组先随意创建一个的数组，跟上一个 Int Date ，并为其赋予一些值,比如跟上 New Int 无序，先初始化一个无序的数组，并随意填写一些元素： 7 , 10 , 8 , 9 , 0, 1 , 2 , 3 , 5 , 10 , 10 , 9 ，最后再添加一个 7 。
public class ArrayDemo { public static void main(String args[]){ Io } }
接下来在代码中还需要添加一个数字 4 到这个数组里，并且为了更好地展示排序过程会多添加几个数字作为例子，也会尽量举一个极端的例子来说明。之后会在数组末尾添加数字 6 ，然后在接近末尾的位置将 00 、 01 放到一个相对靠后的位置。这样就得到了一个待排序的数组。那么这个数组排序后的结果应该是从 0 开始，依次是 1 , 2 , 3 等数字顺序排列。
现在来进行详细的分析。首先要对这个数组进行分析，第一点先确定一下原始数组的内容。原始数组中的值依次列出为 8 , 9 , 0 ，然后在代码中再添加 2 和 3 ，紧接着是 5 ，还有其他值，比如 10 。现在已经把这些值都列完了。接下来再加上 7 ，然后是 6 ，最后还有一个 1 。
接下来看一下最为传统的一种排序处理形式。这种处理形式的基本思路是在每次迭代中，将当前的最大值移动到数组的末尾。那么这是什么意思？接下来通过具体的过程来了解一下。
比如现在想进行第一次排序。第一次排序是这样进行的：先比较 8和 9 ，显然 9 比 8 大，所以 9 保持不动。接下来 9 与 0 比较，9 大于 0 ，因此 9 和 0 需要换位置，即向后移动。然后 9 与 2比较， 9 大于 2 ，所以 9 继续往后挪动。接着是 3 、 5 ，依次进行比较和可能的换位。但到这里还需要继续换吗？不需要了。
那么现在 7 该与谁换？ 7 与 10 换，然后 10 与 6 换， 6 再与1 换，最后再回到 10 进行换位。这就是第一次排序的过程。所以第一次排序结果之后会发现已经将一个较大的数据放到了最后。接下来继续进行下一步，稍微做一些标注。这些标注代表的是第一次排序的执行结果。为了方便理解用大红色来进行标示。
那么现在进行第二次排序， 8 与 0 、 2 、 3 、 5 的比较显然不需要多说，因为它们都比 8 小。而 9 在这个位置不需要动，因为9 已经比它前面的数都大了。接下来比较 9 和 7 ， 7 比 9 小，然后是 6 ，这里不需要详细说每个比较过程，但结果是 9 会“跳过”这些较小的数，保持在较后的位置。所以第二步移动的是 9 ，确保它处于更靠后的正确位置。到现在为止排序已经有了一些改变。
接下来进入第三次排序， 0 、 2 、 3 、 5 和 8 这些数之间的相对位置可能不需要变动，因为它们已经处于或接近最终位置。但需要关注 8 和 7 的比较，这里 7 需要向后移动。同时 6 和 1 也会发生变动，最终这些变动会“回归”到 8 的考虑中，但这里的重点是理解每次排序都在逐步将较大的数向后“拽”。这是第三次排序的概述。
接下来继续进行排序，观察每次操作是否都在将当前未排序部分的最大值向后移动？
然后再来看第四次排序，对于 0 、 2 、 3 、 5 、 7 、 6 这一系列数字，显然 0 、 2 、 3 、 5 和 7 的位置相对固定，主要关注的是 1 和 6 。这次应该移动 1 和 6 ，让 6 向前挪动到它应该在的位置。这样数据的一部分排序就完成了。这是第四次排序的结果。接下来观察前几次排序基本上都是在将较大的数值向前“顶”或移动到它们应该在的位置。
现在轮到 6 和 1 进行比较和可能的移动了。因为其他数字在这个步骤中没有机会移动。继续进行到第五个排序过程。在这个过程中数字序列又发生了一些改变。改变之后需关注 5 和 1 。这两个数字将进行再一次的比较和可能的交换位置，这是第六次排序。
现在把注意力放在这几个值上，让它们进行必要的调整。在 5 和 6排序完之后会发现 1 和 3 又需要进行更换。大家应该能理解这个更换的过程，这是第七次排序。第七次排序后又有一些值被确定了下来。每次排序都在逐步确定所需的数据位置。
接下来进行第八次排序，这次应该是 1 和 2 进行交换。到这里整个的排序流程就已经全部完成了。那么这种排序就是最简单的数据排序过程。接下来要实现这种排序，比如按照刚才所描述的数据依次排序的过程，实际上是应该一个一个进行的。现在给出了几个数据作为示例。下面先来编写代码实现一次排序，按照刚才所描述的方法。
为了让大家看得更清楚会先把打印数组的方法加进来。现在正在编写这段代码。这个程序可以这样写：使用 For 循环，从 Y 等于 0开 始，直到 Y 小于 Date.length ，每次循环 Y++ 后。在完成这段代码后程序需要实现一个比较和交换的流程。假设要比较数组中的元素，那么比较的流程应该是这样的：从第 0 开始， 0 与 1 比较，然后 1与 2 比较，以此类推。
所以可以这样写代码：如果 Date[Y] 大于Date[Y + 1] ，那么就表示需要交换这两个元素。交换数据的流程就是将 Date[Y] 的值赋给一个临时变量 Temp ，然后将 Date[Y + 1] 的值赋给 Date[Y] ，最后将 Temp 的值赋给 Date[Y + 1] 。这样数据交换的流程就完成了。之后 Y 继续递增进行下一次循环，直到遍历完整个数组。
public class ArrayDemo { public static void main(String args[]){ int data [] = new int [] {8,9,0,2,3,5,10,7,6,1}; for (int y = 0 ; y< data,length ; y ++) { } } public static void printArray(int temp []){ for (intx=0;x< temp.length ;x++){ System.out.println (temp[x]) ; } } }
在创建变量之后来看一下结果如何。现在将 Date 变量放在这里，并在这个位置对它进行输出。现在在这个代码块里再加一个输出，并且加上一个换行符，之后跟上 Out.println 。现在代码编写完成后一起来观察这个结果。通过编译并执行代码后为什么会出现“越界为十”的情况。
为什么索引会是十？这是因为已经到达了数组的最后一个元素，即9，而当尝试加一时，就超出了数组的范围，也就是发生了越界。所以这里应该怎么办？这里就需要减一。修改完代码后再次进行编译和执行。
for (int y=0 ;y<data.length ; y ++){ if (data[y]> data[y+11){//交换数据 int temp = data[y] ; data[y] = data[y+ 1]; data[y + 1] = temp ; } } printArray (data); } public static void printArray(inttemp []){ for (int x=0;x<temp.length;x++) { system.out.print(temp[x] + "、") ; } System.out.println() ; } }
这里将之前分析的结果直接展示给大家。这是刚才对问题的分析结果。现在利用这个分析结果来观察刚才的结果， 80235976 和 10 ，但需要注意的是这只是单次排序的结果。然而在实际应用中可能需要多次排序。那么最多可以排序多少次？数组的长度是完全可以满足多次排序需求的。因此为了进行简单的实验验证可以在代码中设置一个外部循环，让排序过程多次执行。
可以这样写：定义一个整型变量 X 并初始化为 0 ，当 X 小于数组 Date 的长度时，执行排序操作，并在每次循环结束时进行 X++ 。这样设置后外部循环将确保排序过程能够完整地执行多次。
D:\mldnjava>javac ArrayDemo.java D:\mldnjava>java ArrayDemo Exception in thread "main" java. lang. ArrayIndexOut0fBoundsException: 10 at ArrayDemo.main(ArrayDemo.java:5) D:\mldnjava>javac ArrayDemo.java D:\mldnjava>java ArrayDemo 8、0、2、3、5、9、7、6、1、10、 D:\mldnjava>
现在来编译并执行代码，再次观察结果可以看到虽然代码运行了，但实际上并没有实现预期的排序效果。进一步分析后发现每次循环中 Y 的比较次数是否可以有所减少。现在的 Y 还在重复判断后续的元素，这个过程其实可以优化。可以通过 X 减 1 的方式，随着X 的增长，判断次数也会相应减少。
接下来具体看一下这个过程。比如编译代码后再次执行。在整个排序过程中可以发现如果第一次需要全比对，那么第二次就会少比对一次，第三次又会少比对两次，以此类推。因此可以通过控制循环变量来优化代码。也就是说如果想要实现一个数组的排序功能，代码基础框架应该像这样构建。
public class ArrayDemo { public static void main(String args[]) { int data [] = new int[] {8,9,0,2,3,5,10,7,6,1} ; for (int x =0;x<data.length ; x ++) { for (int y = 0 ; y < data,length -1 ; y ++) { if (data[y]> data[y + 1]) {//交换数据 int temp = data[y] ; data[y] = data[y + 1] ; data[y + 1] = temp ; } } } printArray(data); } public static void printArray(int temp[]) { for (int x=0; x< temp.length ;x ++){ System.out.print (temp[x] +"、"); }
以上的程序代码都是通过主方法完成的。这并不符合面向对象的设计结构。那么最好的做法是将排序处理的操作交给哪一个方法来完成？可以交给未完成。这个方法应该被命名为未进行，而这个叫做处理完成。
那么这个位怎么处理？比如来看整个代码过程。这里请注意这边的代码过程。一个是排序，即给定数字就进行排序，然后第二个过程的话应该在这里有一个输出功能。那么可以这样写：首先找到一个类，这个类叫做 RVUT ，并将其放在这里。接着在这个类中写一个静态方法，命名为 Salt ，并接收一个整型参数 Date 。
那么这句话所描述的是什么含义？为何要添加一个 Static 关键字？以及在这里添加 Static 的目的是什么？我们主要进行的是对数组的排序处理，但是如果不加 Static 关键字，那么就需要先创建一个类的实例化对象来调用这个方法。而如果添加了 Static 关键字，那么就可以直接通过类名来调用这个方法，无需实例化对象。
class ArrayUtil { public static void sort(intdata[]){ for (intx=0 ;x<data.length;x++){ for (inty=0 iy< data.length-x-1;y++){ if (data[y] > data[y+11){//交换数据 int temp = dataly]; data[y]= data[y+1]; data[y + 1] = temp ; } } } } } public class ArrayDemo { public static void main (String args[]){ int data [] = new int[]{8,9,0,2,3,5,10,7,6,1}; printArray (data) ;
于是这个问题就产生了。为什么现在这个地方不使用实例化对象去调用方法，而是要通过类名直接调用？根据原则类中的方法如果不需要访问类的实例属性，那么这个方法就可以被声明为 Static 。既然 Static 方法不依赖于类的实例属性，那么创建一个实例化对象来调用这样的方法有必要吗？没有必要。
当在未来进行软件设计的时候，如果发现某个类中不存在需要实例化的属性，那么定义的方法就没有必要使用普通方法了。因为普通方法需要在创建了类的实例化对象之后才能被调用。
现在我们并不需要实例化对象。所以在当前的代码中直接进行方法调用即可，就像对日期进行排序那样。
既然我可以进行输出操作，那么将这段代码放在这里是否可以继续在此添加一个输出功能？比如添加一个名为 Rvut.PrintArray 的方法。那么现在在这里是否可以正常完成这些方法的调用？由于类中没有定义属性，所以在这里没有提及普通方法的意义。这就是为什么在这里没有实现普通方法的主要原因。此时已经实现了对数组的排序。
D:\mldnjava>java ArrayDemo 8、0、2、3、5、9、7、6、1、10、 D:\mldnjava>javac ArrayDemo.java D:\mldnjava>java ArrayDemo 0、1、2、3、5、6、7、8、9、10、 D:\mldnjava>javac ArrayDemo.java D:\mldnjava>javaArrayDemo 0、1、2、3、5、6、7、8、9、10、 D:\mldnjava>javac ArrayDemo.java
在整个过程中主方法代码是不是极其简洁？并且所有的功能都交给了类去进行封装和处理。所以这样的结构看起来就非常合理了。
