对ArrayList中存储的TreeNode的排序回顾
一、背景导入
public void sort(List<TreeNode> list){
TreeNode temp = null;
for (int i=0; i<list.size()-1; i++){
for (int j=0; j<list.size()-1-i; j++){
if(list.get(j).freq > list.get(j+1).freq){
temp=list.get(i);
list.set(j,list.get(i+1));
list.set(j+1,temp);
}
}
}
}这段代码的背景是我们通过哈夫曼树实现文件压缩的过程中遇到的一个会卡壳的地方，这里先大致描述一下这个小项目的背景：
我们创建一个.txt文本里面随机放一些随机数量a-z的字符，然后通过BufferReader和FileReader读取文件，我们统计每个字符出现的频率，字符和其对应的频率之间建立映射关系，通过一个hashmap来存储，然后我们需要通过遍历哈希表的同时新建节点来放置每一对键值对，最后创建一个动态数组arraylist来存储这些节点，然后再开始我们的建树过程，下一篇会详细对文件压缩的实现方法进行分析。
but，在建立哈夫曼树之前，如果我们对哈夫曼树的建树过程有一些了解，就会发现此时我们动态数组中虽然存储了节点，但是这些节点的数据大小是无序的不利于我们正常建树，所以这时候还需要我们单独封装一个排序方法，对节点的大小进行排序。
二、思路建立
这时候我们可以暂时使用冒泡排序来实现，在头脑中模拟一下排序的思路
首先从动态数组中下标为0的节点开始， 获取节点的频率，与下标为1的节点大小进行比较，如果[0]>[1]则两者大小交换位置...
感觉这样说有些抽象
三、代码举例
那我们就来举一个例子
待排序列表：
list = [5, 3, 8, 4, 2]第一轮 (外部循环：i = 0)
//冒泡排序过程
第一轮 (i = 0)
//在第一轮中，我们需要比较整个列表（除了最后一个元素），所以 j 的范围是从 0 到 list.size() - 2，也//就是 0 到 3：
1. j = 0: 比较 5 和 3，5 > 3，交换：
- 列表状态：[3, 5, 8, 4, 2]
2. j = 1: 比较 5 和 8，5 < 8，不交换：
- 列表状态：[3, 5, 8, 4, 2]
3. j = 2: 比较 8 和 4，8 > 4，交换：
- 列表状态：[3, 5, 4, 8, 2]
4. j = 3: 比较 8 和 2，8 > 2，交换：
- 列表状态：[3, 5, 4, 2, 8]
//第一轮结束，最大元素 8 已正确“冒泡”到最后。第一轮结束，最大元素 8 已正确“冒泡”到最后。
再思考一遍：外层循环控制次数，内层循环控制的是遍历列表的进度
当i=1时候，我们开始内部循环的第二次遍历，但其实由于最大数已经被正确冒泡到最后一位，所以此时待排序的只有4位数[3,5,4,2]
但不妨先把排序继续进行下去
//第二轮 (i = 1)
//在第二轮，j 的范围是从 0 到 list.size() - 3，也就是 0 到 2，因为最后一个元素已排序：
1. j = 0: 比较 3 和 5，3 < 5，不交换：
- 列表状态：[3, 5, 4, 2, 8]
2. j = 1: 比较 5 和 4，5 > 4，交换：
- 列表状态：[3, 4, 5, 2, 8]
3. j = 2: 比较 5 和 2，5 > 2，交换：
- 列表状态：[3, 4, 2, 5, 8]
//第二轮结束，元素 5 已正确“冒泡”到倒数第二位。
//第三轮 (i = 2)
//在第三轮，j 的范围是从 0 到 list.size() - 4，也就是 0 到 1，因为最后两个元素已排序：
1. j = 0: 比较 3 和 4，3 < 4，不交换：
- 列表状态：[3, 4, 2, 5, 8]
2. j = 1: 比较 4 和 2，4 > 2，交换：
- 列表状态：[3, 2, 4, 5, 8]
//第三轮结束，元素 4 已正确“冒泡”到倒数第三位。
//第四轮 (i = 3)
//在第四轮中，j 的范围是从 0 到 list.size() - 5，也就是 0，只需比较一次，因为前三个位置已排序：
1. j = 0: 比较 3 和 2，3 > 2，交换：
- 列表状态：[2, 3, 4, 5, 8]
//经过第四轮，列表已经完全排序。四、代码分析与规律总结
随着外部循环变量i的大小每增加一次，内部循环进行一轮，最大数被冒泡至最后一位
假设这个列表的长度为len
当i=0时，j需要<(len-1)-0，循环结束，最大数冒泡至末位，待排序长度为len-1
当i=1时，j需要<(len-1)-1，循环结束，最大数冒泡至末位，待排序长度为len-2
.............................................................................................................................
当i=len-2时，j需要<(len-1)-(len-2)，即j=0和j+1=1比较后，排序结束，所有数字此时已被正确排序。
注意正确使用get.与set.方法获取节点中的数据
public void sort(List<TreeNode> list){
//思考泛型优化方式
//冒泡排序
//遍历节点，获得每个节点储存的的字符频率
TreeNode temp = null;
for (int i=0; i<list.size()-1; i++){
for (int j=0; j<list.size()-1-i; j++){
//-i可以理解为已被正确冒泡至末位的已排序个数（重要！！！）
//相邻元素比较
if(list.get(j).freq > list.get(j+1).freq){
temp=list.get(i);//需要冒泡的数据
list.set(j,list.get(i+1));//数据位置进行交换
list.set(j+1,temp);
}
}
}
}