冒泡排序

冒泡排序（优化版）（交换排序）：

　　数组实现：

　　顾名思义，冒泡排序，首先将一组乱序数字中的最大数移到最后，随后除去每次移动到最后的数字，再将前面的所有数字中最大数移到最后...以此类推。（也就是先排序后面的），这里做的优化就是基于后面已经排好序的情况下进行的，假如一组数：4、2、8、3、4、1，第一轮排好后：2、4、3、4、1、8，此时8已经排好，所以以后无需比较此数，设一个标志位记录本轮有没有进行交换动作，如若没有，说明已经排好序，不需要再进行后面的比较。

冒泡排序是稳定的。（稳定是指：相同两个元素在排序前后的相对位置不发生改变）

　　如果忘记了，可以先看下列分析图：

具体代码：

 1 public static void bubbleSort(int[] nums) {
 2         int temp = 0;
 3         boolean flag = false;
 4         for (int j = 0; j < nums.length - 1; j++) {
 5             for (int i = 0; i < nums.length - 1 - j; i++) {// 此处-i是将后面的值确定化，并不再比较它们，减少内循环
 6 
 7                 if (nums[i] > nums[i + 1]) {//交换，并记录本轮是否有过交换
 8                     count++;//记录一共比较多少次
 9                     flag = true;
10                     temp = nums[i];
11                     nums[i] = nums[i + 1];
12                     nums[i + 1] = temp;
13                 }
14             }
15             if (!flag)// 优化: 说明本轮没有进行比较，避免第j次已经排好序的状态下，又继续排序.
16                 return;17             else
18                 flag = false;
19         }
20     }

　　注意：测试时的计算机配置不同，结果可能不同，但是排序之间的相对结果应该是合理的。

　　冒泡排序的最坏情况下：时间复杂度为O(n²)

　　测试80000随机数，范围在1000w内的随机数。结果如下：

　　前后差约为：16秒（效率很差，即使再怎么优化也不能提升，如果是很多数排序，千万不要用冒泡排序）

　　before:2020/05/10 23:07:17:982
　　after:2020/05/10 23:07:33:307

　　比较了交换次数:1603714390

　　链表实现：

 1     public void bubbleSort(Node head) {
 2         if (null == head.getNext()) {//验证链表是否为空
 3             throw new RuntimeException("head getnext is null");
 4         }
 5         boolean flag = false;//优化标志位
 6         for (int i = 0; i < size; i++) {
 7             Node temp = head;//代替辅助头结点
 8             while (temp.getNext() != head) {//由于采用循环双链表，所以判断当前结点下一个是否为头结点，如果是则一轮比较结束
 9                 Node n1 = temp;//保存当前结点
10                 Node n2 = temp.getNext();//保存下一结点
11                 if (n1.getValue() > n2.getValue()) {//开始比较进行交换
12                     swap(n1, n2);//交换方法在下方
13                     flag = true;
14                     continue;//优化点（其实大数量下没什么卵用）
15                 }
16                 temp = temp.getNext();
17             }
18             if (!flag) {
19                 return;
20             } else {
21                 flag = false;
22             }
23         }
24     }
25     //这里的交换方法，需要你仔细思量，最好在纸上画一下
26     public void swap(Node node1, Node node2) {
27         node1.getPre().setNext(node2);
28         node2.setPre(node1.getPre());
29         node1.setNext(node2.getNext());
30         node2.getNext().setPre(node1);
31         node1.setPre(node2);
32         node2.setNext(node1);
33     }

　　测试：

　　冒泡排序的优化在上万数量级下，没有什么卵用，冒泡退出舞台，没有可以挽留的余地了。链表形式的冒泡看看就行了。。。由于是环形双链表，其交换效率比移动数组还差！不要测试了，80000数据跑了几分钟。。。不如数组。