Gausst松鼠会

这个屌丝很懒，什么也没留下！

热门标签

《大话数据结构》8、9查找、排序_大话数据结构查找与排序

作者：Gausst松鼠会 | 2024-04-13 22:22:42

踩

大话数据结构查找与排序

第8章查找 291

查找:
查找 (Searching) 就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素〈或记录〉。

8.1开场白 292

当你精心写了一篇博文或者上传一组照片到互联网上，来自世界各地的无数“蜘蛛”便会蜂拥而至。所谓蜘蛛就是搜索引擎公司服务器上软件，它把互联网当成了蜘蛛网，没日没夜的访问上面的各种信息。

查找算法介绍

在java中，我们常用的查找有四种:
1) 顺序(线性)查找
2) 二分查找/折半查找
1
2
3

插值查找
斐波那契查找

线性查找算法
有一个数列： {1,8, 10, 89, 1000, 1234} ，判断数列中是否包含此名称【顺序查找】要求: 如果找到了，就提示找到，并给出下标值。思路：如果查找到全部符合条件的值。[思路分析.]

   package com.zcr.search;

/**
 * @author zcr
 * @date 2019/7/7-20:29
 */
public class SeqSearch {

    public static void main(String[] args) {
        int arr[] = {1,9,11,-1,34,89};//没有顺序的数组
        int index = seqSearch(arr,11);
        if (index == -1) {
            System.out.println("没有找到");
        } else {
            System.out.println("找到了，下标为="+index);
        }
    }

    //这里我们实现的线性查找是找到一个满足条件的值，就返回
    public static int seqSearch(int[] arr,int value) {
        //线性查找是逐一对比，发现有相同值，就返回下标
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == value){
                return i;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

二分查找算法
二分查找：
请对一个有序数组进行二分查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。
课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000.
在这里插入图片描述

package com.zcr.search;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zcr
 * @date 2019/7/7-20:39
 */
public class BinarySearch {

    public static void main(String[] args) {
        /*int arr[] = {1,8,10,89,1000,1234};//使用二分查找算法的前提是该数组是有序的
        int resIndex = binarySerach(arr,0,arr.length - 1,-1);//如果写一个没有的数，会出现死循环，死递归
        System.out.println(resIndex);*/
        int arr[] = {1,8,10,89,1000,1000,1000,1234};//使用二分查找算法的前提是该数组是有序的
        List<Integer> resIndex = binarySerach2(arr,0,arr.length - 1,1000);//如果写一个没有的数，会出现死循环，死递归
        System.out.println(resIndex);
    }

    //二分查找

    /**
     *
     * @param arr 数组
     * @param left 左边的索引
     * @param right 右边的索引
     * @param findVal 要查找的值
     * @return 如果找到返回下标，找不到返回-1
     */
    public static int binarySerach(int[] arr,int left,int right,int findVal) {

        /*//当left > right时，说明递归整个数组就是没有找到，就返回-1
        if (left > right) {
            return -1;
        }*/

        while (left < right) {
            int mid = (left + right) / 2;
            int midVal = arr[mid];

            if (findVal > midVal) {//向右递归
                return binarySerach(arr,mid + 1,right,findVal);
            } else if (findVal < midVal) {//向左递归
                return binarySerach(arr,left,mid,findVal);
            } else {
                return mid;
            }
        }
        return -1;

    }

    //当存在多个相同的数值时，把所有的值都找到
    //思路分析：在找到mid值时，不要马上返回；
    // 向mid索引值的左边扫描，将所有满足1000的元素的下标都加入到一个集合中ArrayList
    //向mid索引值的右边扫描，将所有满足1000的元素的下标都加入到一个集合中ArrayList
    public static List<Integer> binarySerach2(int[] arr, int left, int right, int findVal) {

        /*//当left > right时，说明递归整个数组就是没有找到，就返回-1
        if (left > right) {
            return -1;
        }*/

        while (left < right) {
            int mid = (left + right) / 2;
            int midVal = arr[mid];

            if (findVal > midVal) {//向右递归
                return binarySerach2(arr,mid + 1,right,findVal);
            } else if (findVal < midVal) {//向左递归
                return binarySerach2(arr,left,mid,findVal);
            } else {
                List<Integer>  resIndexlist = new ArrayList<Integer>();
                int temp = mid - 1;
                while (true) {
                    if (temp < 0 || arr[temp] != findVal) {//退出
                        break;
                    }
                    //否则，就把temp放入到集合中
                    resIndexlist.add(temp);
                    temp--;//temp左移
                }

                resIndexlist.add(mid);

                temp = mid + 1;
                while (true) {
                    if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
                        break;
                    }
                    //否则，就把temp放入到集合中
                    resIndexlist.add(temp);
                    temp++;//temp左移
                }
                return resIndexlist;
            }
        }
        return new ArrayList<Integer>();

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

插值查找算法
插值查找原理介绍:

插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right.key 就是前面我们讲的 findVal
在这里插入图片描述
改成

int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;/插值索引/
对应前面的代码公式：int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])
举例说明插值查找算法 1-100 的数组

插值查找算法

package com.zcr.search;

import java.util.Arrays;

/**
 * @author zcr
 * @date 2019/7/7-21:16
 */
public class InsertValueSearch {

    public static void main(String[] args) {

        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i + 1;
        }
        System.out.println(Arrays.toString(arr));

        int resIndex = insertValueSearch(arr,0,arr.length - 1,1);
        System.out.println(resIndex);

    }

    //编写插值查找算法
    //也要求数组是有序的
    public static int insertValueSearch(int[] arr,int left, int right, int findVal) {

        System.out.println("hello");//查找次数
        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
            return -1;
        }

        //求出mid
        //自适应
        int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
        int midVal = arr[mid];
        if (findVal > midVal) {//向右查找递归
            return insertValueSearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {//向左递归查找
            return insertValueSearch(arr, right, mid - 1, findVal);
        } else {
            return mid;
        }



    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

插值查找应用案例：
请对一个有序数组进行插值查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。

插值查找
插值查找注意事项：
对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.
关键字分布不均匀的情况下，该方法不一定比折半查找要好

斐波那契(黄金分割法)查找算法
斐波那契(黄金分割法)查找基本介绍:

黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不大的效果。
斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数的比例，无限接近黄金分割值0.618

斐波那契(黄金分割法)查找算法
斐波那契(黄金分割法)原理:
斐波那契查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1（F代表斐波那契数列），如下图所示
在这里插入图片描述
对F(k-1)-1的理解：
1.由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，可以得到 （F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 。该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1
2.类似的，每一子段也可以用相同的方式分割
3.但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。
在这里插入图片描述
斐波那契(黄金分割法)查找算法
斐波那契查找应用案例：
请对一个有序数组进行斐波那契查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。

package com.zcr.search;

import java.util.Arrays;

/**
 * @author zcr
 * @date 2019/7/7-21:35
 */
public class FibonacciSearch {
    public static int maxSize = 20;

    public static void main(String[] args) {
        int[] arr = {1,8,10,89,1000,1234};
        System.out.println(fibSearch(arr,89));
    }

    //必须是有序的
    //因为后面的mid = low + F(k - 1) - 1，需要使用到斐波那契数列，所以我们要先获取一个斐波那契数列
    //用非递归的方式得到（）也可以使用递归的方式
    public static int[] fib() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    //编写斐波那契查找算法
    //使用非递归的方式
    public static int fibSearch(int[] a,int key) {
        int low = 0;
        int high = a.length - 1;
        int k = 0;//表示斐波那契分割数值的下标
        int mid = 0;//存放mid值
        int f[] = fib();//获取到斐波那契数列
        //获取到斐波那契数值的下标
        while (high > f[k] - 1) {
            k++;
        }

        //因为f[k]的值可能大于a数组的长度，因此需要使用Arrays类构造一个新的数组，并指向a
        int[] temp = Arrays.copyOf(a,f[k]);//不足的部分会使用0填充
        //实际上需要使用a数组的最后的数填充temp
        //temp = {1,8,10,89,1000,1234,0,0,0}->{1,8,10,89,1000,1234,1234,1234,1234}
        for (int i = high + 1; i < temp.length; i++) {
            temp[i] = a[high];
        }

        //使用循环，找到key
        while (low <= high) {
            mid = low + f[k - 1] - 1;
            if (key < temp[mid]) {//向数组的左边查找递归
                high = mid - 1;
                //为什么是k--？
                //1.全部元素=前面的元素+后边的元素
                //2.f[k] = f[k - 1] + f[k -2]
                //因为前面有f[k - 1]个元素，所以可以继续拆分f[k-1] = f[k - 2] + f[k -3]
                //即在f[k - 1]的前面继续查找，k--
                //即下次循环时，mid = f[k-1-1] - 1
                k--;
            } else if (key > temp[mid]) {
                low = mid + 1;
                //为什么是k-2?
                //1.全部元素=前面的元素+后边的元素
                //2.f[k] = f[k - 1] + f[k -2]
                //因为后面有f[k - 2]个元素，所以可以继续拆分f[k-2] = f[k - 3] + f[k -4]
                //即在f[k - 2]的前面面继续查找，k-2
                //即下次循环时，mid = f[k-1-2] - 1
                k -= 2;
            } else {
                //需要确定返回的是哪个下标
                if (mid <= high) {
                    return mid;
                } else {
                    return high;
                }
            }

        }
        return -1;



    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

8.2查找概论 293

比如网络时代的新名词，如“蜗居”、“蚁族”等，如果需要将它们收录到汉语词典中，显然收录时就需要查找它们是否存在，以及找到如果不存在时应该收录的位置。

查找表 (Search Table)是由同一类型的数据元素〈或记录)构成的集合。

关键字 (Key) 是数据元素中某个数据项的值，又称为键值，用它可以标识一个数据元素。也可以标识一个记录的某个数据项(字段) ，我们称为关键码

若此关键字可以唯一地标识一个记录，则称此关键字为主关键字 (Primary l{，酬。注意这也就意味着，对不同的记录，其主关键宇均不相同。主关键字所在的数据项称为主关键码

那么对于那些可以识别多个数据元素(或记录)的关键字，我们称为次关键字 (Secon也ryKey) 。。次关键字也可以理解为是不以唯一标识一个数据元素(或记录。)的关键字，它对应的数据项就是次关键码。

查找( Searchìng )就是根据给定的某个值，在查找表中确定-个其关键字等于给定值的数据元素(或记录)。

在这里插入图片描述

查找表按照操作方式来分有两大种:静态查找袭和动态查找表。
静态查找表(如tic Search’ Table) :只作查找操作的查找表。宫的主要操作有:
(1) 查询某个"特定的"数据 '元素是否在查找表中。
(2) 检索某个"特定的数据元索和各种属性。

动态查找表 (Dynamic Search Table): 在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。显然动态查找表的操作就是两个:
(1) 查找时插入数据元素。
(2) 查找时删除数据元素。

为了提高查找的效率，我们需要专门为查找操作设置数据结构，这种面向查找操作的数据结构称为查找结构。

从逻辑上来说，查找所基于的数据结构是集合，集合中的记录之间没有本质关系。可是要想获得较高的查找性能，我们就不能不改变数据元素之问的关系，在存储时可以将查找集合组织成表、树等结掏。

例如，对于静态查找表来说，我们不妨应用线性表结构来组织数据，这样可以使用顺序查找算法，如果再对主关键字排序，则可以应用折半查找等技术进行高效的查找。

如果是需要动态查找，则会复杂一些，可以考虑二叉排序树的查找技术。

另外，还可以用散列表结构来解决一些查找问题，这些技术都将在后面的讲解中说明。

8.3顺序表查找 295

我们要针对这一线性表进行查找操作，因此它就是静态查找表。

顺序查找 (Sequential Search) 又叫线性查找，是最基本的查找技术，它的查找过程是:从表中第一个(或最后一个)记录开始，逐个进行记亲的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录;如果直到最后一个(或第一个)记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

8.3.1顺序表查找算法 296

8.3.2顺序表查找优化 297

package Sequential_Search;
/**
 * 顺序表查找
 * 数组下标为0的位置不用来储存实际内容
 * @author Yongh
 *
 */
public class Sequential_Search {
    /*
     * 顺序查找
     */
    public int seqSearch(int[] arr,int key) {
        int n=arr.length;
        for(int i=1;i<n;i++) {  //i从1开始
            if(key==arr[i])
                return i;
        }
        return 0;
    }
    /*
     * 顺序查找优化，带哨兵
     */
    public int seqSearch2(int[] arr,int key) {
        int i=arr.length-1;
        arr[0]=key;  //将arr[0]设为哨兵
        while(arr[i]!=key)
            i--;
        return i;  //返回0说明查找失败
    }
     
    public static void main(String[] args) {
        int[] arr = {0,45,68,32,15};
        Sequential_Search aSearch = new Sequential_Search();
        System.out.println(aSearch.seqSearch(arr, 15));
        System.out.println(aSearch.seqSearch(arr, 45));
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

结果：
4
1

这段代码非常简单，就是在数组 a (注意元素值从下标 1 开始)中查看有没有关键字 (key) ，当你需要查找复杂表结构的记录时，只需要把数组 a 与关键字 key 定义成你需要的表结构和数据类型即可。

顺序表查找优化

到这里并非足够完美，因为每次循环时都需要对 i 是否越界，即是否小于等于 n 作判断。事实上，还可以有更好一点的办法，设置一个哨兵，可以解决不需要每次让 i 与 n 作比较。看下面的改进后的顺序查找算法代码。

此时代码是从尾部开始查找，由于 a[0]=key，也就是说，如果在 a[i]中有 key 则返回 i 值，查找成功。否则一定在最终的 a[0]处等于 key，此时返回的是 0，即说明 a[l] -a[n]中没有关键字 key，查找失败。

这种在查找方向的尽头放置"哨兵"免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但在总数据较多时，效率提高很大，是非常好的编码技巧。当然， "哨兵"也不一定就一定要在数组开始，也可以在未端。

对于这种顺序查找算法来说，查找成功最好的情况就是在第一个位置就找到了，算法时间复杂度为 O(1)，最坏的情况是在最后一位置才找到，需要 n 次比较，时间复杂度为 O(n)，当查找不成功时，需要n+1 次比较，时间复杂度为 O(n)。我们之前推导过，关键字在任何一位置的概率是相同的，所以平均查找次数为O(n+1)/2 ，所以最终时间复杂度还是 O(n)。

很显然，顺序查找技术是有很大缺点的，n 很大时，查找效率极为低下，不过优点也是有的，这个算法非常简单，对静态查找表的记录没有任何要求，在一些小型数据的查找时，是可以适用的。

另外，也正由于查找概率的不同，我们完全可以将容易查找到的记录般在前面，而不常用的记录放置在后面，效率就可以有大幅提高。

8.4有序表查找 298

我在纸上已经写好了一个100以内的正整数请你猜，问几次可以猜出来。当时已经介绍了如何才可以最快的猜出这个数字。我们把这种每次取中间记录查找的方法叫做折半查找。

8.4.1折半查找 298

折半查找 (Binary Search) 技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序) ，线性表必须采用顺序存储。折半查找的基本思想是:在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功;若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域元记录，查找失败为止。

折半查找，又称作二分查找。必须满足两个前提：

1.存储结构必须是顺序存储
2.关键码必须有序排列

假设数据按升序排列。从中间项与关键值（key）开始对比，若关键值（key）>中间值，则在右半区间继续查找，反之则左半区间继续查找。以此类推，直至找到匹配值，或者查找内无记录，查找失败。

时间复杂度：O(logn)，可从二叉树的性质4推得。

折半查找的Java实现代码：

package OrderedTable_Search;
/**
 * 折半查找
 * @author Yongh
 *
 */
public class BinarySearch {
    public int binarySearch(int[] arr,int n,int key) {
        int low=1;
        int high=n;
        while(low<=high) {
            int mid = (low+high)/2;
            if(arr[mid]<key)
                low=mid+1;   //要+1
            else if(arr[mid]>key)
                high=mid-1;  //要-1
            else
                return mid;        
        }                      
        return 0;
    }
     
    public static void main(String[] args) {
        int[] arr = {0,1,16,24,35,47,59,62,73,88,99};
        int n=arr.length-1;
        int key=62;
        BinarySearch aSearch = new BinarySearch();
        System.out.println(aSearch.binarySearch(arr, n, key));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

结果：
4

我们之前 6.6 节讲的二叉树的性质 4，有过对 ”具有 n 个结点的完全二叉树的深度为Llog2nJ+1。 " 性质的推导过程。在这里尽管折半查找判定二叉树并不是完全二叉树，但同样相同的推导可以得出，最坏情况是查找到关键字或查找失败的次数为 llogznJ+l。
最好的情况?那还用说吗，当然是 1 次了。

因此最终我们折半算法的时间复杂度为O(logn) ，它显然远远好于顺序查找的O(n) 时间复杂度了。

不过由于折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，这样的算法已经比较好了。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。

8.4.2插值查找 301

对于表长较大，关键字分布比较均匀的查找表来说，可以采用插值查找：

将折半查找中代码的第12行
在这里插入图片描述
也就是 mid 等于最低下标 k>w 加上最高下标 high 与 klw 的差的一半。算法科学家们考虑的就是将这个 1/2 进行改进，改进为下面的计算方案:

改进为：
在这里插入图片描述

在这里插入图片描述
　　改进后的第12行代码如下：

int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]);/*插值*/
1

在这里插入图片描述
　　注意：关键字分布不均匀的情况下，该方法不一定比折半查找要好。

8.4.3斐波那契查找 302

我们再介绍一种有序查找，斐波那契查找 (Fibonacci Sea.rc时，它是利用了黄金分割原理来实现的。

先需要有一个斐波那契数列的数组，如困
在这里插入图片描述

斐波那契数列如下所示：
在这里插入图片描述
斐波那契查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1（F代表斐波那契数列），如下图所示：

对F(k-1)-1的理解：
由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，可以得到（F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 。该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1

类似的，每一子段也可以用相同的方式分割，从而方便编程。

但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可，由以下代码得到：

while(n>fib(k)-1)
k++;

顺序表长度增加后，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。

时间复杂度：O(logn)

以下为具体的Java代码，还有不理解的地方可看对应处的注释：

package OrderedTable_Search;
/**
 * 斐波那契查找
 * 下标为0位置不存储记录
 * 顺便编写了斐波那契数列的代码
 * @author Yongh
 *
 */
public class FibonacciSearch {
    /*
     * 斐波那契数列
     * 采用递归
     */
    public static int fib(int n) {
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        return fib(n-1)+fib(n-2);
    }
     
    /*
     * 斐波那契数列
     * 不采用递归
     */
    public static int fib2(int n) {
        int a=0;
        int b=1;       
        if(n==0)
            return a;
        if(n==1)
            return b;
        int c=0;
        for(int i=2;i<=n;i++) {
            c=a+b;
            a=b;
            b=c;                           
        }  
        return c;
    }
     
    /*
     * 斐波那契查找
     */
    public static int fibSearch(int[] arr,int n,int key) {
        int low=1;  //记录从1开始
        int high=n;     //high不用等于fib(k)-1，效果相同
        int mid;
         
        int k=0;
        while(n>fib(k)-1)    //获取k值
            k++;
        int[] temp = new int[fib(k)];   //因为无法直接对原数组arr[]增加长度，所以定义一个新的数组
        System.arraycopy(arr, 0, temp, 0, arr.length); //采用System.arraycopy()进行数组间的赋值
        for(int i=n+1;i<=fib(k)-1;i++)    //对数组中新增的位置进行赋值
            temp[i]=temp[n]; 
         
        while(low<=high) {
            mid=low+fib(k-1)-1;
            if(temp[mid]>key) {
                high=mid-1;
                k=k-1;  //对应上图中的左段，长度F[k-1]-1
            }else if(temp[mid]<key) {
                low=mid+1;
                k=k-2;  //对应上图中的右端，长度F[k-2]-1
            }else {
                if(mid<=n)
                    return mid;
                else
                    return n;       //当mid位于新增的数组中时，返回n    
            }                          
        }
        return 0;
    }
    public static void main(String[] args) {
        int[] arr = {0,1,16,24,35,47,59,62,73,88,99};
        int n=10;
        int key=59;
        System.out.println(fibSearch(arr, n, key));  //输出结果为：6
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

在这里插入图片描述

三种有序表的查找比较

在这里插入图片描述

8.5线性索引查找 306

我母亲年纪大了，经常在家里找不到东西，于是她用一小本子，记录了家里所有小东西放置的位置，比如户口本放在右手床头柜下面抽屉中，钞票放在衣……咳，这个就不提了。

要保证记景全部是按照当中的某个关键字有序，其时间代价是非常高昂的，所以这种数据通常都是按先后顺序存储。

那么对于这样的查找衰，我们如何能够快速查找到需要的数据呢?办法就是一一索引。

数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与宫对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。

索引按照结向可以分为线性索引、树形索引和多级索引。我们这里就只介绍线性索引技术。所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。我们重点介绍三种线性索引：稠密索引、分块索引和倒排索引。

8.5.1稠密索引 307

从这件事就可以看出，家中的物品尽管是无序的，但是如果有一个小本子记录，寻找起来也是非常容易，而这小本子就是索引。

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项，如图
在这里插入图片描述
对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。

索引项有序也就意味着，我们要查找关键字时，可以用到折半、插值、斐被那契等有序查找算法，大大提高了效率，比如图 8-5-2 中，我要查找关键字是 18 的记录，如果直接从右侧的数据表中查找，那只能顺序查找，需要查找 6 次才可以查到结果. 而如果是从左侧的索引表中查找，只需两次折半查找就可以得到 18 对应的指针，最终查找到结果。

这显然是稠密索引优点，但是如果数据集非常大，比如上亿，那也就意味着索引也得同样的数据集长度规模，对于内存有限的计算机来说，可能就需要反复去访问磁盘，查找性能反而大大下降了。

8.5.2分块索引 308

稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。

分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件:
• 块内无序，即每一块内的记录不要求有序。当然，你如果能够让块内有序对查找来说更理想，不过这就要付出大量时间和空间的代价，因此通常我们不要求块内有序。
• 块间有序，例如，要求第二块所有记录的关键字均要大于第一块中所有记景的关键字，第三块的所有记录的关键字均要大于第二块的所有记录关键字……因为只有块间有序，才有可能在查找时带来放率。

对于分块有序的数据集，将每块对应一个索引项，这种索引方法叫做分块索引。如图 8-5-4 所示，我们定义的分块索引的索引项结构分三个数据项:
• 最大关键码，它存储每一块中的最大关键字，这样的好处就是可以使得在它之后的下一块中的最小关键字也能比这一块最大的关键字要大i
• 存储了块中的记录个数，以便于循环时使用;
• 用于指向块首数据元素的指针，便于开始对这一块中记景进行遍历。
在这里插入图片描述
在分块索引表中查找，就是分两步进行:
1 . 在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的，因此很容易利用折半、插值等算法得到结果。例如，在图 8-5-4 的数据集中查找 62 ，我们可以很快可以从左上角的索引表中由 57<62<96 得到 62 在第三个块中。
2 . 根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找。

我们再来分析一下分块索引的平均查找长度。设 n 个记录的数据集被平均分成 m块，每个块中有 t 条记录，显然 n=mXt，或者说 m=n/t。
在这里插入图片描述

8.5.3倒排索引 311

索引项的通用结构是:
• 次关键码.例如上面的"英文单词";
• 记录号表，例如上面的"文章编号"。

其中记录号表存储具有相同次关键字的所有记录的记录号 (可以是指向记录的指针或者是该记录的主关键字)。这样的索引方法就是倒排索引 (invened index) 。

倒排索引源于实际应用中需要根据属性(或字段、次关键码)的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。

倒排索引的优点显然就是查找记录非常快，基本等于生成索引表后，查找时都不用去读取记录，就可以得到结果。但它的缺点是这个记录号不定长，比如上倒有 7 个单词的文章编号只有一个，而 “book”、“friend”、 “good” 有两个文章编号，若是对多篇文章所有单词建立倒排索引，那每个单词都将对应相当多的文章编号，维护比较困难，插入和删除操作都需要作相应的处理。

当然，现实中的搜索技术非常复杂，比如我们不仅要知道某篇文章有要搜索的关键字，还想知道这个关键字在文章中的哪些地方出现，这就需要我们对记录号表做一些改良。再比如，文章编号上亿，如果都用长数字也没必要，可以进行压缩，比如三篇文章的编号是 “112，115，119” ，我们可以记录成 “112， +3， +4” ，即只记录差值，这样每个关键字就只占用一两个字节。甚至关键字也可以压缩，比如前一条记录的关键字是 “and” 而后一条是 “android” ，那么后面这个可以改成 "❤️，roid♂，这样也可以起到压缩数据的作用。再比如搜索时，尽管告诉你有几千几万条查找到的记录，但其实真正显示给你看的，就只是当中的前 10 或者 20 条左右数据，只有在点击下一页时才会获得后面的部分索引记录，这也可以大大提高了整体搜索的效率。

8.6二叉排序树 313

后来老虎来了，一人拼命地跑，另一人则急中生智，爬到了树上。而老虎是不会爬树的，结果……。爬树者改变了跑的思想，这一改变何等重要，捡回了自己的一条命。

假设查找的数据集是普通的顺序存储，那么插入操作就是将记录放在表的末端，给表记录数加一即可，删除操作可以是删除后，后面的记录向前移，也可以是要删除的元素与最后一个元素互换，表记录数减一，反正整个数据集也没有什么顺序，这样的效率也不错。应该说，插入和删除对于顺序存储结构来说，效率是可以接受的，但这样的表由于无序造成查找的效率很低，前面我们有讲解，这就不在啰嗦。

如果查找的数据集是有序线性表 ，并且是顺序存储的，查找可以用折半、插值、斐波那契等查找算法来实现，可惜，因为有序，在插入和删除操作上，就需要耗费大量的时间。

有没有一种即可以使得插入和删除效率不错，又可以比较高效率地实现查找的算法呢?

这种需要在查找时插入或删除的查找表称为动态查找表。我们现在就来看着什么样的结构可以实现动态查找表的高效率。

如果在复杂的问题面前，我们束手无策的话，不妨先从最最简单的情况入手。现在我们的目标是插入和查找同样高效。假设我们的数据集开始只有一个数{62}，然后现在需要将 88 插入数据集，于是数据集成了{62，88}，还保持着从小到大有序。再查找有没有 58，没有则插入，可此时要想在线性表的顺序存储中有序，就得移动 62 和 88 的位置，如图 8-6-2 左图，可不可以不移动呢?嗯，当然是可以，那就是二叉树结构。当我们用二叉树的方式时，首先我们将第一个数 62 定为根结点， 88 因为比 62 大，因此让它做 62 的右子树， 58 困比 62 小，所以成为它的左子树。此时 58 的插入并投有影响到 62 与 88 的关系，如图
在这里插入图片描述

这样我们就得到了一棵二叉树，并且当我们对官进行中序遍历时，就可以得到一个有序的序列{35.37，47.51，58，62，73，88，93.99} ，所以我们通常称它为二叉排序树。

二叉排序树 (Binary Sort Tree)，又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。
• 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值;
• 若它的右子树不空，则右子树上所有结点的值均大于宫的根结点的值;
• 它的左、右子树也分别为二叉排序树。

从二叉排序树的定义也可以知道，宫前提是二叉树，然后它采用了递归的定义方法，再者，宫的结点间满足一定的次序关系，左子树结点一定比其双亲结点小，右子树结点一定比其双亲结点大。

构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。

8.6.1二叉排序树查找操作 316

首先我们提供一个二叉树的结构。

package BST;
 
/**
 * 二叉排序树（二叉查找树）
 * 若是泛型，则要求满足T extends Comparable<T> static问题
 * @author Yongh
 *
 */
class Node {
    int data;
    Node lChild, rChild;
 
    public Node(int data) {
        this.data = data;
        lChild = null;
        rChild = null;
    }
}
 
public class BSTree {
    private Node root;
 
    public BSTree() {
        root = null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

然后我们来看看二叉排序树的查找是如何实现的。

采用递归的查找算法

/*
 * 查找
 */
public boolean SearchBST(int key) {
    return SearchBST(key, root);
}
 
private boolean SearchBST(int key, Node node) {
    if (node == null)//用来判断当前二叉树是否到叶子结点，
        return false;
    if (node.data == key) {
        return true;
    } else if (node.data < key) {
        return SearchBST(key, node.rChild);
    } else {
        return SearchBST(key, node.lChild);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

采用非递归的查找算法

/*
 * 查找，非递归
 */
public boolean SearchBST2(int key) {
    Node p = root;
    while (p != null) {
        if (p.data > key) {
            p = p.lChild;
        } else if (p.data < key) {
            p = p.rChild;
        } else {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

8.6.2二叉排序树插入操作 318

有了二叉排序树的查找函数，那么所谓的二叉排序树的插入，其实也就是将关键字放到树中的合适位置而已，来看代码。

思路：与查找类似，但需要一个父节点来进行赋值。

采用非递归的插入算法：

/*
 * 插入，自己想的，非递归
 */
public boolean InsertBST(int key) {
    Node newNode = new Node(key);
    if (root == null) {
        root = newNode;
        return true;
    }
    Node f = null; // 指向父结点
    Node p = root; // 当前结点的指针
    while (p != null) {
        if (p.data > key) {
            f = p;
            p = p.lChild;
        } else if (p.data < key) {
            f = p;
            p = p.rChild;
        } else {
            System.out.println("树中已有相同数据，不再插入！");
            return false;
        }
    }
    if (f.data > key) {
        f.lChild = newNode;
    } else if (f.data < key) {
        f.rChild = newNode;
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

采用递归的插入算法：

/*
 * 插入，参考别人博客，递归
 * 思路：把null情况排除后用递归，否则无法赋值
 */
public boolean InsertBST2(int key) {
    if (root == null) {
        root = new Node(key);
        return true;
    }
    return InsertBST2(key, root);
}
 
private boolean InsertBST2(int key, Node node) {
    if (node.data > key) {
        if (node.lChild == null) {
            node.lChild = new Node(key);
            return true;
        } else {
            return InsertBST2(key, node.lChild);
        }
    } else if (node.data < key) {
        if (node.rChild == null) {
            node.rChild = new Node(key);
            return true;
        } else {
            return InsertBST2(key, node.rChild);
        }
    } else {
        System.out.println("树中已有相同数据，不再插入！");
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

发现以下的插入方法比较好（如果没有要求返回值必须为boolean格式的话）：（推荐使用此类方法）

/*
 * 插入操作
 */
public void insert(int key) {
    root = insert(root, key);
}
 
private Node insert(Node node, int key) {
    if (node == null) {
        // System.out.println("插入成功！");
        // 也可以定义一个布尔变量来保存插入成功与否
        return new Node(key);
    }
    if (key == node.data) {
        System.out.println("数据重复，无法插入！");
    } else if (key < node.data) {
        node.lChild=insert(node.lChild, key);
    } else {
        node.rChild=insert(node.rChild, key);
    }
    return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

8.6.3二叉排序树删除操作 320

我们已经介绍了二叉排序树的查找与插入算法，但是对于二叉排序树的删除，就不是那么容易，我们不能因为删除了结点，而让这棵树变得不满足二叉排序树的特性，所以删除需要考虑多种情况.
在这里插入图片描述

在这里插入图片描述

根据我们对删除结点三种情况的分析:
• 叶子结点;
• 仅有左或右子树的结点:
• 左右子树都有的结点，我们来看代码，下面这个算法是递归方式对二叉排序树 T查找 key. 查找到时删除。

思路：

（1）删除叶子结点

直接删除；

（2）删除仅有左或右子树的结点

子树移动到删除结点的位置即可；

（3）删除左右子树都有的结点

找到删除结点p的直接前驱（或直接后驱）s，用s来替换结点p，然后删除结点s，如下图所示。

首先找到删除结点位置及其父结点

/*
 * 删除操作，先找到删除结点位置及其父结点
 * 因为需要有父结点，所以暂时没想到递归的方法（除了令Node对象带个parent属性）
 */
public boolean deleteBST(int key) {
    if (root == null) {
        System.out.println("空表，删除失败");
        return false;
    }
    Node f = null; // 指向父结点
    Node p = root; // 指向当前结点
    while (p != null) {
        if (p.data > key) {
            f = p;
            p = p.lChild;
        } else if (p.data < key) {
            f = p;
            p = p.rChild;
        } else {
            delete(p, f);
            return true;
        }
    }
    System.out.println("该数据不存在");
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

再根据上述思路进行结点p的删除：（需注意删除结点为根节点的情况）

/*
 * 删除结点P的操作
 * 必须要有父结点,因为Java无法直接取得变量p的地址（无法使用*p=(*p)->lChild）
 */
private void delete(Node p, Node f) {// p为删除结点，f为其父结点
    if (p.lChild == null) { // 左子树为空，重接右子树
        if (p == root) { // 被删除结点为根结点时，无法利用f，该情况不能忽略
            root = root.rChild;
            p = null;
        } else {
            if (f.data > p.data) { // 被删结点为父结点的左结点，下同
                f.lChild = p.rChild;
                p = null; // 释放结点别忘了
            } else {// 被删结点为父结点的右结点，下同
                f.rChild = p.rChild;
                p = null;
            }
        }
    } else if (p.rChild == null) { // 右子树为空，重接左子树
        if (p == root) { // 被删除结点为根结点
            root = root.lChild;
            p = null;
        } else {
            if (f.data > p.data) {
                f.lChild = p.lChild;
                p = null;
            } else {
                f.rChild = p.lChild;
                p = null;
            }
        }
    } else { // 左右子树都不为空,删除位置用前驱结点替代
        Node q, s;
        q = p;
        s = p.lChild;
        while (s.rChild != null) { // 找到待删结点的最大前驱s
            q = s;
            s = s.rChild;
        }
        p.data = s.data; // 改变p的data就OK
        if (q != p) {
            q.rChild = s.lChild;//重接q的右子树
        } else {
            q.lChild = s.lChild;//重接q的左子树
        }
        s = null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

在这里插入图片描述

8.6.4二叉排序树总结 327

package BST;
 
/**
 * 二叉排序树（二叉查找树）
 * 若是泛型，则要求满足T extends Comparable<T> static问题
 * @author Yongh
 *
 */
class Node {
    int data;
    Node lChild, rChild;
 
    public Node(int data) {
        this.data = data;
        lChild = null;
        rChild = null;
    }
}
 
public class BSTree {
    private Node root;
 
    public BSTree() {
        root = null;
    }
 
    /*
     * 查找
     */
    public boolean SearchBST(int key) {
        return SearchBST(key, root);
    }
 
    private boolean SearchBST(int key, Node node) {
        if (node == null)
            return false;
        if (node.data == key) {
            return true;
        } else if (node.data < key) {
            return SearchBST(key, node.rChild);
        } else {
            return SearchBST(key, node.lChild);
        }
    }
 
    /*
     * 查找，非递归
     */
    public boolean SearchBST2(int key) {
        Node p = root;
        while (p != null) {
            if (p.data > key) {
                p = p.lChild;
            } else if (p.data < key) {
                p = p.rChild;
            } else {
                return true;
            }
        }
        return false;
    }
 
    /*
     * 插入，自己想的，非递归
     */
    public boolean InsertBST(int key) {
        Node newNode = new Node(key);
        if (root == null) {
            root = newNode;
            return true;
        }
        Node f = null; // 指向父结点
        Node p = root; // 当前结点的指针
        while (p != null) {
            if (p.data > key) {
                f = p;
                p = p.lChild;
            } else if (p.data < key) {
                f = p;
                p = p.rChild;
            } else {
                System.out.println("数据重复，无法插入！");
                return false;
            }
        }
        if (f.data > key) {
            f.lChild = newNode;
        } else if (f.data < key) {
            f.rChild = newNode;
        }
        return true;
    }
 
    /*
     * 插入，参考别人博客，递归
     * 思路：类似查找，
     *       但若方法中的node为null的话，将无法插入新数据，需排除null的情况
     */
    public boolean InsertBST2(int key) {
        if (root == null) {
            root = new Node(key);
            return true;
        }
        return InsertBST2(key, root);
    }
 
    private boolean InsertBST2(int key, Node node) {
        if (node.data > key) {
            if (node.lChild == null) { // 有null的情况下，才有父结点
                node.lChild = new Node(key);
                return true;
            } else {
                return InsertBST2(key, node.lChild);
            }
        } else if (node.data < key) {
            if (node.rChild == null) {
                node.rChild = new Node(key);
                return true;
            } else {
                return InsertBST2(key, node.rChild);
            }
        } else {
            System.out.println("数据重复，无法插入！");
            return false;
        }
    }
 
    /*
     * 这样的插入是错误的（node无法真正被赋值）
     */
    /*
    private boolean InsertBST2(int key, Node node) {
        if(node!=null) {
            if (node.data > key)
                return InsertBST2(key, node.lChild);
            else if (node.data < key)
                return InsertBST2(key, node.rChild);
            else
                return false;//重复
        }else {
            node=new Node(key);
            return true;
        }          
    }
    */
 
    /*
     * 删除操作，先找到删除结点位置及其父结点
     * 因为需要有父结点，所以暂时没想到递归的方法（除了令Node对象带个parent属性）
     */
    public boolean deleteBST(int key) {
        if (root == null) {
            System.out.println("空表，删除失败");
            return false;
        }
        Node f = null; // 指向父结点
        Node p = root; // 指向当前结点
        while (p != null) {
            if (p.data > key) {
                f = p;
                p = p.lChild;
            } else if (p.data < key) {
                f = p;
                p = p.rChild;
            } else {
                delete(p, f);
                System.out.println("删除成功！");
                return true;
            }
        }
        System.out.println("该数据不存在");
        return false;
    }
 
    /*
     * 删除结点P的操作
     * 必须要有父结点,因为Java无法直接取得变量p的地址（无法使用*p=(*p)->lChild）
     */
    private void delete(Node p, Node f) {// p为删除结点，f为其父结点
        if (p.lChild == null) { // 左子树为空，重接右子树
            if (p == root) { // 被删除结点为根结点，该情况不能忽略
                root = root.rChild;
                p = null;
            } else {
                if (f.data > p.data) { // 被删结点为父结点的左结点，下同
                    f.lChild = p.rChild;
                    p = null; // 释放结点别忘了
                } else {// 被删结点为父结点的右结点，下同
                    f.rChild = p.rChild;
                    p = null;
                }
            }
        } else if (p.rChild == null) { // 右子树为空，重接左子树
            if (p == root) { // 被删除结点为根结点
                root = root.lChild;
                p = null;
            } else {
                if (f.data > p.data) {
                    f.lChild = p.lChild;
                    p = null;
                } else {
                    f.rChild = p.lChild;
                    p = null;
                }
            }
        } else { // 左右子树都不为空,删除位置用前驱结点替代
            Node q, s;
            q = p;
            s = p.lChild;
            while (s.rChild != null) { // 找到待删结点的最大前驱s
                q = s;
                s = s.rChild;
            }
            p.data = s.data; // 改变p的data就OK
            if (q != p) {
                q.rChild = s.lChild;
            } else {
                q.lChild = s.lChild;
            }
            s = null;
        }
    }
 
    /*
     * 中序遍历
     */
    public void inOrder() {
        inOrder(root);
        System.out.println();
    }
 
    public void inOrder(Node node) {
        if (node == null)
            return;
        inOrder(node.lChild);
        System.out.print(node.data + " ");
        inOrder(node.rChild);
    }
 
    /*
     * 测试代码
     */
    public static void main(String[] args) {
        BSTree aTree = new BSTree();
        BSTree bTree = new BSTree();
        int[] arr = { 62, 88, 58, 47, 35, 73, 51, 99, 37, 93 };
        for (int a : arr) {
            aTree.InsertBST(a);
            bTree.InsertBST2(a);
        }
        aTree.inOrder();
        bTree.inOrder();
        System.out.println(aTree.SearchBST(35));
        System.out.println(bTree.SearchBST2(99));
        aTree.deleteBST(47);
        aTree.inOrder();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258

35 37 47 51 58 62 73 88 93 99
35 37 47 51 58 62 73 88 93 99
true
true
删除成功!
35 37 51 58 62 73 88 93 99

小结（自己编写时的注意点）：

查找：操作简单，注意递归的方法没有循环while (p!=null)，而是并列的几个判断；

插入：非递归时，要有父结点；递归时，要注意排除null的情况；

删除：记住要分两步，第一步找结点位置时也要把父结点带上；第二步删除结点时，要令p=null，还要注意proot的情况以及qp的情况。

总之，二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合造的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为 1 次，即根结点就是要找的结点，最多也不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。

例如{62,88.58.47.35.73.51.99.37.93}这样的数组，我们可以构建如图 8-6-18 左图的二叉排序树。但如果数组元素的次序是从小到大有序，如{35.37.47.51.58.62.73.88. 93.99} ，则二叉排序树就成了极端的右斜树，注意它依然是一棵二叉排序树，如圈 8-6-18 的右圈。此时，同样是查找结点 99，左图只需要两次比较，而右图就需要 10 次比较才可以得到结果，二者差异很大。

在这里插入图片描述
也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，均为Lhg2nJ吐，那么查找的时间复杂也就为 O(hgn)，近似于折半查找，事实上，图 8-6-18 的左图也不够平衡，明显的左重右轻。

不平衡的最坏情况就是像图 8-6-18 右图的斜树，查找时间复杂度为 O(n)，这等同于顺序查找。

因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树。这样我们就引申出另一个问题，如何让二叉排序树平衡的问题。

8.7平衡二叉树（avl树） 328

平板就是一个世界，当诱惑降临，人心中的平衡被打破，世界就会混乱，最后留下的只有孤独寂寞失败。这种单调的机械化的社会，禁不住诱惑的侵蚀，最容易被侵蚀的，恰恰是最空虚的心灵。

平衡二叉树 (Self-Balancing Binary Search Tree或Height-Balanced Binary Search Tree) ，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于 1。

它是一种高度平衡的二叉排序树。那什么叫做高度平衡呢?意思是说，要么它是一棵空树，要么它的左子树和右子树都是平衡二叉树，旦左子树和右子树的深度之差的绝对值不超过 1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子 BF (Balance Factor) ，那么平衡二叉树上所有结点的平衡因乎只可能是一1、 0 和 1. 只要二叉树上有一个结点的平衡园子的绝对值大于 1 ，则该二叉树就是不平衡的。

考查我们对平衡二叉树的定义的理解，它的前提首先是一棵二叉排序树
在这里插入图片描述

距离插入结点最近的，且平衡困子的绝对值大于 1 的结点为根的子树，我们称为最小不平衡子树。图 8-7-3，当新插入结点 37 时，距离它最近的平衡因子绝对值超过 1 的结点是 58 (即它的左子树高度 2 减去右子树高度的，所以从 58 开始以下的子树为最小不平衡子树。
在这里插入图片描述

8.7.1平衡二叉树实现原理 330

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每当插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

在这里插入图片描述

所谓的平衡二叉树，其实就是在二叉排序树创建过程中保证官的平衡性，一旦发现有不平衡的情况，马上处理，这样就不会造成不可收拾的情况出现。通过刚才这个例子，你会发现，当最小不平衡子树根结点的平衡因子 BF 是大于 1 时，就右旋，小于一1 时就左旋，如上例中结点 1、 5、 6、 7 的插入等。插入结点后，最小不平衡子树的 BF 与它的子树的 BF 符号相反时，就需要对结点先进行一次旋转以使得符号相同后，再反向旋转一次才能够完成平衡操作，如上例中结点 9、 8 的插入时.

8.7.2平衡二叉树实现算法 334

首先是需要改进二叉排序树的结点结构，增加一个 bf用来存储平衡因子

private class AVLnode {
    int data; // 结点数据
    int bf; // 平衡因子,左高记为1，右高记为-1，平衡记为0
    AVLnode lChild, rChild; // 左右孩子
 
    public AVLnode(int data) {
        this.data = data;
        bf = 0;
        lChild = null;
        rChild = null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

然后，对于右旋操作，我们的代码如下。
根据之前提到的基本思想，为调整最小不平衡树，首先要了解两种最基本的操作：左旋操作和右旋操作。

基本操作（左/右旋操作）
（1）右旋

如下图中左边的最小不平衡二叉树，进行右旋操作即可变为右边中的平衡二叉树。
在这里插入图片描述

/*
 * 右旋
 * 返回新的根结点
 */
public AVLnode rRotate(AVLnode p) {
    AVLnode l = p.lChild;
    p.lChild = l.rChild;//l指向p的左子树根节点
    l.rChild = p;//l的右子树挂接为p的左子树
    return l;
}
1
2
3
4
5
6
7
8
9
10

在这里插入图片描述

（2）左旋操作

同上所述，左旋操作的图示及代码，如下所示。
在这里插入图片描述

/*
 * 左旋
 * 返回新的根结点
 */
public AVLnode lRotate(AVLnode p) {
    AVLnode r = p.rChild;
    p.rChild = r.lChild;//r的左子树挂接为p的右子树
    r.lChild = p;//p作为r的左孩子
    return r;
}
1
2
3
4
5
6
7
8
9
10

左/右平衡旋转
对于最小不平衡子树，若其左子树深度比右子树大2（下面称为左斜的不平衡树），需进行左平衡旋转操作。若右子树深度大，则需进行右平衡旋转操作。

（1）左平衡旋转：

左斜的不平衡树有几种形式，下面分开讨论

L结点的BF值为1时

直接对根结点P右旋即可

情况(1)：如下图所示，右旋根结点P。平衡后，P结点的BF值为0，其左结点L的BF值也为0。

在这里插入图片描述

L结点的BF值为-1时

都是先对L结点左旋，再对P结点右旋。根据平衡后P结点和L结点的BF值不同，可以分出下面三种情况：

情况(2)：如下图所示，先左旋L结点，再右旋P结点。平衡后，P结点的BF值为-1，L结点的BF值为0，LR结点的BF值为0。

在这里插入图片描述

（注：示意图中，小三角形表示的子树比大三角形表示的子树深度少1，下同）

情况(3)：如下图所示，先左旋L结点，再右旋P结点。平衡后，P结点的BF值为0，L结点的BF值为1，LR结点的BF值为0。

在这里插入图片描述

情况(4)：如下图所示，先左旋L结点，再右旋P结点。平衡后，P结点的BF值为0，L结点的BF值为0，LR结点的BF值为0。

在这里插入图片描述

L结点的BF值为0时

最小不平衡子树也可能出现下面这种情况（插入时不会出现，但删除操作过程中可能出现），《大话》一书中没有讨论到这种情况。

情况(5)：如下图所示，直接右旋P结点。平衡后，L结点的BF值为-1，LR结点的BF值为1。

在这里插入图片描述
综上所述，左平衡旋转一共可能出现5种情况，以下为左平衡旋转操作的代码：

/*
 * 左平衡旋转(左子树高度比右子树高2时(左斜)执行的操作)
 * 返回值为新的根结点
 */
public AVLnode leftBalance(AVLnode p) {
    AVLnode l = p.lChild;//l指向t的左子树根节点
    switch (l.bf) {//检查t的左子树的平衡度，并作相应平衡处理
    case 1: // 情況(1)新结点插在t的左孩子的左子树上，要做单右旋处理
        p.bf = 0;
        l.bf = 0;
        return rRotate(p);
    case -1://新结点插在t的左孩子的右子树上，要做双旋处理
        AVLnode lr = l.rChild;//lr指向t的左孩子的右子树跟
        switch (lr.bf) {//修改t及其左孩子的平衡因子
        case 1: // 情況(2)
            p.bf = -1;
            l.bf = 0;
            break; // break别漏写了
        case -1: // 情況(3)
            p.bf = 0;
            l.bf = 1;
            break;
        case 0: // 情況(4)
            p.bf = 0;
            l.bf = 0;
            break;
        }
        lr.bf = 0;
        // 设置好平衡因子bf后，先左旋
        p.lChild = lRotate(l);// 不能用l=leftBalance(l);
        // 再右旋
        return rRotate(p);
    case 0: // 这种情况书中没有考虑到，情况(5)
        l.bf = -1;
        p.bf = 1;
        return rRotate(p);
    }
    // 以下情况应该是不会出现的，所有情况都已经包括，除非程序还有问题
    System.out.println("bf超出范围，请检查程序！");
    return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

在这里插入图片描述

我们前面例子中的新增结点 9 和 8 就是典型的右平衡旋转，并且双旋完成平衡的例子

（2）右平衡旋转：

与左平衡的分析类似，也可以分为五种情况，不再赘述，下面直接给出代码：

/*
 * 右平衡旋转(右子树高度比左子树高2时执行的操作)
 * 返回值为新的根结点
 */
public AVLnode rightBalance(AVLnode p) {
    AVLnode r = p.rChild;
    switch (r.bf) {
    case -1:
        p.bf = 0;
        r.bf = 0;
        return lRotate(p);
    case 1:
        AVLnode rl = r.lChild;
        switch (rl.bf) {
        case 1:
            r.bf = -1;
            p.bf = 0;
            break;
        case -1:
            r.bf = 0;
            p.bf = 1;
            break;
        case 0:
            r.bf = 0;
            p.bf = 0;
            break;
        }
        rl.bf = 0;
        p.rChild = rRotate(r);
        return lRotate(p);
    case 0:
        p.bf = -1;
        r.bf = 1;
        return lRotate(p);
    }
    // 以下情况应该是不会出现的，所有情况都已经包括，除非程序还有问题
    System.out.println("bf超出范围，请检查程序！");
    return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

插入操作的主函数
二叉平衡树是一种二叉排序树，所以其操作与二叉排序树相同，但为了保持平衡，需要对平衡度进行分析。

引入一个变量taller来衡量子树是否长高，若子树长高了，就必须对平衡度进行分析：如果不平衡，就进行上面所说的左右平衡旋转操作。

具体的Java实现代码如下：

/*
 * 插入操作
 * 要多定义一个taller变量
 */
boolean taller;// 树是否长高
 
public void insert(int key) { 
    root = insert(root, key);
}
 
private AVLnode insert(AVLnode tree, int key) {// 二叉查找树的插入操作一样，但多了树是否长高的判断（树没长高就完全类似BST二叉树），要记得每次对taller赋值
    if (tree == null) {
        taller = true;
        return new AVLnode(key);
    }
    if (key == tree.data) {
        System.out.println("数据重复，无法插入！");
        taller = false;
        return tree;
    } else if (key < tree.data) {
        tree.lChild = insert(tree.lChild, key);
        if (taller == true) { // 左子树长高了，要对tree的平衡度分析
            switch (tree.bf) {
            case 1: // 原本左子树比右子树高，需要左平衡处理
                taller = false; // 左平衡处理，高度没有增加
                return leftBalance(tree);
            case 0: // 原本左右子树等高，现因左子树增高而增高
                tree.bf = 1;
                taller = true;
                return tree;
            case -1: // 原本右子树比左子树高，现左右子树相等
                tree.bf = 0;
                taller = false;
                return tree;
            }
        }
    } else if (key > tree.data) {
        tree.rChild = insert(tree.rChild, key);
        if (taller == true) { // 右子树长高了，要对tree的平衡度分析
            switch (tree.bf) {
            case 1: // 原本左子树高，现等高
                tree.bf = 0;
                taller = false;
                return tree;
            case 0: // 原本等高，现右边增高了
                tree.bf = -1;
                taller = true;
                return tree;
            case -1: // 原本右子树高，需右平衡处理
                taller = false;
                return rightBalance(tree);
            }
        }
    }
    return tree;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

在这里插入图片描述

AVL树的完整代码
AVL树的完整代码如下（含测试代码）：

package AVLTree;
 
/**
 * AVL树
 * @author Yongh
 *
 */
public class AVLTree {
 
    private AVLnode root;
 
    private class AVLnode {
        int data; // 结点数据
        int bf; // 平衡因子,左高记为1，右高记为-1，平衡记为0
        AVLnode lChild, rChild; // 左右孩子
 
        public AVLnode(int data) {
            this.data = data;
            bf = 0;
            lChild = null;
            rChild = null;
        }
    }
 
    /*
     * 右旋
     * 返回新的根结点
     */
    public AVLnode rRotate(AVLnode p) {
        AVLnode l = p.lChild;
        p.lChild = l.rChild;
        l.rChild = p;
        return l;
    }
 
    /*
     * 左旋
     * 返回新的根结点
     */
    public AVLnode lRotate(AVLnode p) {
        AVLnode r = p.rChild;
        p.rChild = r.lChild;
        r.lChild = p;
        return r;
    }
 
    /*
     * 左平衡旋转(左子树高度比右子树高2时(左斜)执行的操作)
     * 返回值为新的根结点
     */
    public AVLnode leftBalance(AVLnode p) {
        AVLnode l = p.lChild;
        switch (l.bf) {
        case 1: // 情況(1)
            p.bf = 0;
            l.bf = 0;
            return rRotate(p);
        case -1:
            AVLnode lr = l.rChild;
            switch (lr.bf) {
            case 1: // 情況(2)
                p.bf = -1;
                l.bf = 0;
                break; // break别漏写了
            case -1: // 情況(3)
                p.bf = 0;
                l.bf = 1;
                break;
            case 0: // 情況(4)
                p.bf = 0;
                l.bf = 0;
                break;
            }
            lr.bf = 0;
            // 设置好平衡因子bf后，先左旋
            p.lChild = lRotate(l);// 不能用l=leftBalance(l);
            // 再右旋
            return rRotate(p);
        case 0: // 这种情况书中没有考虑到，情况(5)
            l.bf = -1;
            p.bf = 1;
            return rRotate(p);
        }
        // 以下情况应该是不会出现的，所有情况都已经包括，除非程序还有问题
        System.out.println("bf超出范围，请检查程序！");
        return p;
    }
 
    /*
     * 右平衡旋转(右子树高度比左子树高2时执行的操作)
     * 返回值为新的根结点
     */
    public AVLnode rightBalance(AVLnode p) {
        AVLnode r = p.rChild;
        switch (r.bf) {
        case -1:
            p.bf = 0;
            r.bf = 0;
            return lRotate(p);
        case 1:
            AVLnode rl = r.lChild;
            switch (rl.bf) {
            case 1:
                r.bf = -1;
                p.bf = 0;
                break;
            case -1:
                r.bf = 0;
                p.bf = 1;
                break;
            case 0:
                r.bf = 0;
                p.bf = 0;
                break;
            }
            rl.bf = 0;
            p.rChild = rRotate(r);
            return lRotate(p);
        case 0:
            p.bf = -1;
            r.bf = 1;
            return lRotate(p);
        }
        // 以下情况应该是不会出现的，所有情况都已经包括，除非程序还有问题
        System.out.println("bf超出范围，请检查程序！");
        return p;
    }
 
    /*
     * 插入操作
     * 要多定义一个taller变量
     */
    boolean taller;// 树是否长高
 
    public void insert(int key) { 
        root = insert(root, key);
    }
 
    private AVLnode insert(AVLnode tree, int key) {// 二叉查找树的插入操作一样，但多了树是否长高的判断（树没长高就完全类似BST二叉树），要记得每次对taller赋值
        if (tree == null) {
            taller = true;
            return new AVLnode(key);
        }
        if (key == tree.data) {
            System.out.println("数据重复，无法插入！");
            taller = false;
            return tree;
        } else if (key < tree.data) {
            tree.lChild = insert(tree.lChild, key);
            if (taller == true) { // 左子树长高了，要对tree的平衡度分析
                switch (tree.bf) {
                case 1: // 原本左子树比右子树高，需要左平衡处理
                    taller = false; // 左平衡处理，高度没有增加
                    return leftBalance(tree);
                case 0: // 原本左右子树等高，现因左子树增高而增高
                    tree.bf = 1;
                    taller = true;
                    return tree;
                case -1: // 原本右子树比左子树高，现左右子树相等
                    tree.bf = 0;
                    taller = false;
                    return tree;
                }
            }
        } else if (key > tree.data) {
            tree.rChild = insert(tree.rChild, key);
            if (taller == true) { // 右子树长高了，要对tree的平衡度分析
                switch (tree.bf) {
                case 1: // 原本左子树高，现等高
                    tree.bf = 0;
                    taller = false;
                    return tree;
                case 0: // 原本等高，现右边增高了
                    tree.bf = -1;
                    taller = true;
                    return tree;
                case -1: // 原本右子树高，需右平衡处理
                    taller = false;
                    return rightBalance(tree);
                }
            }
        }
        return tree;
    }
 
    /*
     * 前序遍历
     */
    public void preOrder() {
        preOrderTraverse(root);
        System.out.println();
    }
 
    private void preOrderTraverse(AVLnode node) {
        if (node == null)
            return;
        System.out.print(node.data+" ");
        preOrderTraverse(node.lChild);
        preOrderTraverse(node.rChild);
    }
 
    /*
     * 中序遍历
     */
    public void inOrder() {
        inOrderTraverse(root);
        System.out.println();
    }
 
    private void inOrderTraverse(AVLnode node) {
        if (node == null)
            return;
        inOrderTraverse(node.lChild);
        System.out.print(node.data+" ");
        inOrderTraverse(node.rChild);
    }
     
    /*
     * 测试代码
     */
    public static void main(String[] args) {
        AVLTree aTree = new AVLTree();
        int[] arr = { 3, 2, 1, 4, 5, 6, 7, 10, 9, 8 };
        for (int i : arr) {
            aTree.insert(i);
        }
        System.out.print("前序遍历结果：");
        aTree.preOrder();
        System.out.print("中序遍历结果：");
        aTree.inOrder();
         
        AVLTree bTree = new AVLTree();
        int[] arr2 = { 3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9 };
        for (int i : arr2) {
            bTree.insert(i);
        }
        System.out.print("前序遍历结果：");
        bTree.preOrder();
        System.out.print("中序遍历结果：");
        bTree.inOrder();       
    }
 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243

前序遍历结果：4 2 1 3 7 6 5 9 8 10
中序遍历结果：1 2 3 4 5 6 7 8 9 10
前序遍历结果：7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16
中序遍历结果：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

测试代码中的两个AVL树如下图所示：
在这里插入图片描述

后记

如果不用平衡因子BF，而是子树的高度来进行分析，讨论的情况就比较少，可参考这篇博客：AVL树(三)之 Java的实现

节点

1.1 节点定义

public class AVLTree<T extends Comparable<T>> {
    private AVLTreeNode<T> mRoot;    // 根结点

    // AVL树的节点(内部类)
    class AVLTreeNode<T extends Comparable<T>> {
        T key;                // 关键字(键值)
        int height;         // 高度
        AVLTreeNode<T> left;    // 左孩子
        AVLTreeNode<T> right;    // 右孩子

        public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.height = 0;
        }
    }
    
    ......
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

AVLTree是AVL树对应的类，而AVLTreeNode是AVL树节点，它是AVLTree的内部类。AVLTree包含了AVL树的根节点，AVL树的基本操作也定义在AVL树中。AVLTreeNode包括的几个组成对象:
(01) key – 是关键字，是用来对AVL树的节点进行排序的。
(02) left – 是左孩子。
(03) right – 是右孩子。
(04) height – 是高度。

1.2 树的高度

/*
 * 获取树的高度
 */
private int height(AVLTreeNode<T> tree) {
    if (tree != null)
        return tree.height;

    return 0;
}

public int height() {
    return height(mRoot);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

关于高度，有的地方将"空二叉树的高度是-1"，而本文采用维基百科上的定义：树的高度为最大层次。即空的二叉树的高度是0，非空树的高度等于它的最大层次(根的层次为1，根的子节点为第2层，依次类推)。

1.3 比较大小

/*
 * 比较两个值的大小
 */
private int max(int a, int b) {
    return a>b ? a : b;
}
1
2
3
4
5
6

旋转

如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡。这种失去平衡的可以概括为4种姿态：LL(左左)，LR(左右)，RR(右右)和RL(右左)。下面给出它们的示意图：
在这里插入图片描述
上图中的4棵树都是"失去平衡的AVL树"，从左往右的情况依次是：LL、LR、RL、RR。除了上面的情况之外，还有其它的失去平衡的AVL树，如下图：

上面的两张图都是为了便于理解，而列举的关于"失去平衡的AVL树"的例子。总的来说，AVL树失去平衡时的情况一定是LL、LR、RL、RR这4种之一，它们都由各自的定义：

(1) LL：LeftLeft，也称为"左左"。插入或删除一个节点后，根节点的左子树的左子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。
例如，在上面LL情况中，由于"根节点(8)的左子树(4)的左子树(2)还有非空子节点"，而"根节点(8)的右子树(12)没有子节点"；导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

(2) LR：LeftRight，也称为"左右"。插入或删除一个节点后，根节点的左子树的右子树还有非空子节点，导致"根的左子树的高度"比"根的右子树的高度"大2，导致AVL树失去了平衡。
例如，在上面LR情况中，由于"根节点(8)的左子树(4)的左子树(6)还有非空子节点"，而"根节点(8)的右子树(12)没有子节点"；导致"根节点(8)的左子树(4)高度"比"根节点(8)的右子树(12)"高2。

(3) RL：RightLeft，称为"右左"。插入或删除一个节点后，根节点的右子树的左子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。
例如，在上面RL情况中，由于"根节点(8)的右子树(12)的左子树(10)还有非空子节点"，而"根节点(8)的左子树(4)没有子节点"；导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

(4) RR：RightRight，称为"右右"。插入或删除一个节点后，根节点的右子树的右子树还有非空子节点，导致"根的右子树的高度"比"根的左子树的高度"大2，导致AVL树失去了平衡。
例如，在上面RR情况中，由于"根节点(8)的右子树(12)的右子树(14)还有非空子节点"，而"根节点(8)的左子树(4)没有子节点"；导致"根节点(8)的右子树(12)高度"比"根节点(8)的左子树(4)"高2。

如果在AVL树中进行插入或删除节点后，可能导致AVL树失去平衡。AVL失去平衡之后，可以通过旋转使其恢复平衡，下面分别介绍"LL(左左)，LR(左右)，RR(右右)和RL(右左)"这4种情况对应的旋转方法。

2.1 LL的旋转

LL失去平衡的情况，可以通过一次旋转让AVL树恢复平衡。如下图：

在这里插入图片描述

图中左边是旋转之前的树，右边是旋转之后的树。从中可以发现，旋转之后的树又变成了AVL树，而且该旋转只需要一次即可完成。
对于LL旋转，你可以这样理解为：LL旋转是围绕"失去平衡的AVL根节点"进行的，也就是节点k2；而且由于是LL情况，即左左情况，就用手抓着"左孩子，即k1"使劲摇。将k1变成根节点，k2变成k1的右子树，“k1的右子树"变成"k2的左子树”。

LL的旋转代码

/*
 * LL：左左对应的情况(左单旋转)。
 *
 * 返回值：旋转后的根节点
 */
private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2) {
    AVLTreeNode<T> k1;

    k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;

    k2.height = max( height(k2.left), height(k2.right)) + 1;
    k1.height = max( height(k1.left), k2.height) + 1;

    return k1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.2 RR的旋转

理解了LL之后，RR就相当容易理解了。RR是与LL对称的情况！RR恢复平衡的旋转方法如下：

在这里插入图片描述
图中左边是旋转之前的树，右边是旋转之后的树。RR旋转也只需要一次即可完成。

RR的旋转代码

/*
 * RR：右右对应的情况(右单旋转)。
 *
 * 返回值：旋转后的根节点
 */
private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1) {
    AVLTreeNode<T> k2;

    k2 = k1.right;
    k1.right = k2.left;
    k2.left = k1;

    k1.height = max( height(k1.left), height(k1.right)) + 1;
    k2.height = max( height(k2.right), k1.height) + 1;

    return k2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.3 LR的旋转

LR失去平衡的情况，需要经过两次旋转才能让AVL树恢复平衡。如下图：
在这里插入图片描述
第一次旋转是围绕"k1"进行的"RR旋转"，第二次是围绕"k3"进行的"LL旋转"。

LR的旋转代码

/*
 * LR：左右对应的情况(左双旋转)。
 *
 * 返回值：旋转后的根节点
 */
private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3) {
    k3.left = rightRightRotation(k3.left);

    return leftLeftRotation(k3);
}
1
2
3
4
5
6
7
8
9
10

2.4 RL的旋转

RL是与LR的对称情况！RL恢复平衡的旋转方法如下：
在这里插入图片描述
第一次旋转是围绕"k3"进行的"LL旋转"，第二次是围绕"k1"进行的"RR旋转"。

RL的旋转代码

/*
 * RL：右左对应的情况(右双旋转)。
 *
 * 返回值：旋转后的根节点
 */
private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1) {
    k1.right = leftLeftRotation(k1.right);

    return rightRightRotation(k1);
}
1
2
3
4
5
6
7
8
9
10

插入

插入节点的代码

/* 
 * 将结点插入到AVL树中，并返回根节点
 *
 * 参数说明：
 *     tree AVL树的根结点
 *     key 插入的结点的键值
 * 返回值：
 *     根节点
 */
private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
    if (tree == null) {
        // 新建节点
        tree = new AVLTreeNode<T>(key, null, null);
        if (tree==null) {
            System.out.println("ERROR: create avltree node failed!");
            return null;
        }
    } else {
        int cmp = key.compareTo(tree.key);

           if (cmp < 0) {    // 应该将key插入到"tree的左子树"的情况
            tree.left = insert(tree.left, key);
            // 插入节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.left) - height(tree.right) == 2) {
                if (key.compareTo(tree.left.key) < 0)
                    tree = leftLeftRotation(tree);
                else
                    tree = leftRightRotation(tree);
            }
        } else if (cmp > 0) {    // 应该将key插入到"tree的右子树"的情况
            tree.right = insert(tree.right, key);
            // 插入节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.right) - height(tree.left) == 2) {
                if (key.compareTo(tree.right.key) > 0)
                    tree = rightRightRotation(tree);
                else
                    tree = rightLeftRotation(tree);
            }
        } else {    // cmp==0
            System.out.println("添加失败：不允许添加相同的节点！");
        }
    }

    tree.height = max( height(tree.left), height(tree.right)) + 1;

    return tree;
}

public void insert(T key) {
    mRoot = insert(mRoot, key);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

删除

删除节点的代码

/* 
 * 删除结点(z)，返回根节点
 *
 * 参数说明：
 *     tree AVL树的根结点
 *     z 待删除的结点
 * 返回值：
 *     根节点
 */
private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z) {
    // 根为空 或者 没有要删除的节点，直接返回null。
    if (tree==null || z==null)
        return null;

    int cmp = z.key.compareTo(tree.key);
    if (cmp < 0) {        // 待删除的节点在"tree的左子树"中
        tree.left = remove(tree.left, z);
        // 删除节点后，若AVL树失去平衡，则进行相应的调节。
        if (height(tree.right) - height(tree.left) == 2) {
            AVLTreeNode<T> r =  tree.right;
            if (height(r.left) > height(r.right))
                tree = rightLeftRotation(tree);
            else
                tree = rightRightRotation(tree);
        }
    } else if (cmp > 0) {    // 待删除的节点在"tree的右子树"中
        tree.right = remove(tree.right, z);
        // 删除节点后，若AVL树失去平衡，则进行相应的调节。
        if (height(tree.left) - height(tree.right) == 2) {
            AVLTreeNode<T> l =  tree.left;
            if (height(l.right) > height(l.left))
                tree = leftRightRotation(tree);
            else
                tree = leftLeftRotation(tree);
        }
    } else {    // tree是对应要删除的节点。
        // tree的左右孩子都非空
        if ((tree.left!=null) && (tree.right!=null)) {
            if (height(tree.left) > height(tree.right)) {
                // 如果tree的左子树比右子树高；
                // 则(01)找出tree的左子树中的最大节点
                //   (02)将该最大节点的值赋值给tree。
                //   (03)删除该最大节点。
                // 这类似于用"tree的左子树中最大节点"做"tree"的替身；
                // 采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。
                AVLTreeNode<T> max = maximum(tree.left);
                tree.key = max.key;
                tree.left = remove(tree.left, max);
            } else {
                // 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1)
                // 则(01)找出tree的右子树中的最小节点
                //   (02)将该最小节点的值赋值给tree。
                //   (03)删除该最小节点。
                // 这类似于用"tree的右子树中最小节点"做"tree"的替身；
                // 采用这种方式的好处是：删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。
                AVLTreeNode<T> min = maximum(tree.right);
                tree.key = min.key;
                tree.right = remove(tree.right, min);
            }
        } else {
            AVLTreeNode<T> tmp = tree;
            tree = (tree.left!=null) ? tree.left : tree.right;
            tmp = null;
        }
    }

    return tree;
}

public void remove(T key) {
    AVLTreeNode<T> z; 

    if ((z = search(mRoot, key)) != null)
        mRoot = remove(mRoot, z);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

完整的实现代码
AVL树的实现文件(AVRTree.java)

/**
 * Java 语言: AVL树
 *
 * @author skywang
 * @date 2013/11/07
 */

public class AVLTree<T extends Comparable<T>> {
    private AVLTreeNode<T> mRoot;    // 根结点

    // AVL树的节点(内部类)
    class AVLTreeNode<T extends Comparable<T>> {
        T key;                // 关键字(键值)
        int height;         // 高度
        AVLTreeNode<T> left;    // 左孩子
        AVLTreeNode<T> right;    // 右孩子

        public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
            this.key = key;
            this.left = left;
            this.right = right;
            this.height = 0;
        }
    }

    // 构造函数
    public AVLTree() {
        mRoot = null;
    }

    /*
     * 获取树的高度
     */
    private int height(AVLTreeNode<T> tree) {
        if (tree != null)
            return tree.height;

        return 0;
    }

    public int height() {
        return height(mRoot);
    }

    /*
     * 比较两个值的大小
     */
    private int max(int a, int b) {
        return a>b ? a : b;
    }

    /*
     * 前序遍历"AVL树"
     */
    private void preOrder(AVLTreeNode<T> tree) {
        if(tree != null) {
            System.out.print(tree.key+" ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

    public void preOrder() {
        preOrder(mRoot);
    }

    /*
     * 中序遍历"AVL树"
     */
    private void inOrder(AVLTreeNode<T> tree) {
        if(tree != null)
        {
            inOrder(tree.left);
            System.out.print(tree.key+" ");
            inOrder(tree.right);
        }
    }

    public void inOrder() {
        inOrder(mRoot);
    }

    /*
     * 后序遍历"AVL树"
     */
    private void postOrder(AVLTreeNode<T> tree) {
        if(tree != null) {
            postOrder(tree.left);
            postOrder(tree.right);
            System.out.print(tree.key+" ");
        }
    }

    public void postOrder() {
        postOrder(mRoot);
    }

    /*
     * (递归实现)查找"AVL树x"中键值为key的节点
     */
    private AVLTreeNode<T> search(AVLTreeNode<T> x, T key) {
        if (x==null)
            return x;

        int cmp = key.compareTo(x.key);
        if (cmp < 0)
            return search(x.left, key);
        else if (cmp > 0)
            return search(x.right, key);
        else
            return x;
    }

    public AVLTreeNode<T> search(T key) {
        return search(mRoot, key);
    }

    /*
     * (非递归实现)查找"AVL树x"中键值为key的节点
     */
    private AVLTreeNode<T> iterativeSearch(AVLTreeNode<T> x, T key) {
        while (x!=null) {
            int cmp = key.compareTo(x.key);

            if (cmp < 0)
                x = x.left;
            else if (cmp > 0)
                x = x.right;
            else
                return x;
        }

        return x;
    }

    public AVLTreeNode<T> iterativeSearch(T key) {
        return iterativeSearch(mRoot, key);
    }

    /* 
     * 查找最小结点：返回tree为根结点的AVL树的最小结点。
     */
    private AVLTreeNode<T> minimum(AVLTreeNode<T> tree) {
        if (tree == null)
            return null;

        while(tree.left != null)
            tree = tree.left;
        return tree;
    }

    public T minimum() {
        AVLTreeNode<T> p = minimum(mRoot);
        if (p != null)
            return p.key;

        return null;
    }
     
    /* 
     * 查找最大结点：返回tree为根结点的AVL树的最大结点。
     */
    private AVLTreeNode<T> maximum(AVLTreeNode<T> tree) {
        if (tree == null)
            return null;

        while(tree.right != null)
            tree = tree.right;
        return tree;
    }

    public T maximum() {
        AVLTreeNode<T> p = maximum(mRoot);
        if (p != null)
            return p.key;

        return null;
    }

    /*
     * LL：左左对应的情况(左单旋转)。
     *
     * 返回值：旋转后的根节点
     */
    private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2) {
        AVLTreeNode<T> k1;

        k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;

        k2.height = max( height(k2.left), height(k2.right)) + 1;
        k1.height = max( height(k1.left), k2.height) + 1;

        return k1;
    }

    /*
     * RR：右右对应的情况(右单旋转)。
     *
     * 返回值：旋转后的根节点
     */
    private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1) {
        AVLTreeNode<T> k2;

        k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;

        k1.height = max( height(k1.left), height(k1.right)) + 1;
        k2.height = max( height(k2.right), k1.height) + 1;

        return k2;
    }

    /*
     * LR：左右对应的情况(左双旋转)。
     *
     * 返回值：旋转后的根节点
     */
    private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3) {
        k3.left = rightRightRotation(k3.left);

        return leftLeftRotation(k3);
    }

    /*
     * RL：右左对应的情况(右双旋转)。
     *
     * 返回值：旋转后的根节点
     */
    private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1) {
        k1.right = leftLeftRotation(k1.right);

        return rightRightRotation(k1);
    }

    /* 
     * 将结点插入到AVL树中，并返回根节点
     *
     * 参数说明：
     *     tree AVL树的根结点
     *     key 插入的结点的键值
     * 返回值：
     *     根节点
     */
    private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
        if (tree == null) {
            // 新建节点
            tree = new AVLTreeNode<T>(key, null, null);
            if (tree==null) {
                System.out.println("ERROR: create avltree node failed!");
                return null;
            }
        } else {
            int cmp = key.compareTo(tree.key);

               if (cmp < 0) {    // 应该将key插入到"tree的左子树"的情况
                tree.left = insert(tree.left, key);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (height(tree.left) - height(tree.right) == 2) {
                    if (key.compareTo(tree.left.key) < 0)
                        tree = leftLeftRotation(tree);
                    else
                        tree = leftRightRotation(tree);
                }
            } else if (cmp > 0) {    // 应该将key插入到"tree的右子树"的情况
                tree.right = insert(tree.right, key);
                // 插入节点后，若AVL树失去平衡，则进行相应的调节。
                if (height(tree.right) - height(tree.left) == 2) {
                    if (key.compareTo(tree.right.key) > 0)
                        tree = rightRightRotation(tree);
                    else
                        tree = rightLeftRotation(tree);
                }
            } else {    // cmp==0
                System.out.println("添加失败：不允许添加相同的节点！");
            }
        }

        tree.height = max( height(tree.left), height(tree.right)) + 1;

        return tree;
    }

    public void insert(T key) {
        mRoot = insert(mRoot, key);
    }

    /* 
     * 删除结点(z)，返回根节点
     *
     * 参数说明：
     *     tree AVL树的根结点
     *     z 待删除的结点
     * 返回值：
     *     根节点
     */
    private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z) {
        // 根为空 或者 没有要删除的节点，直接返回null。
        if (tree==null || z==null)
            return null;

        int cmp = z.key.compareTo(tree.key);
        if (cmp < 0) {        // 待删除的节点在"tree的左子树"中
            tree.left = remove(tree.left, z);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.right) - height(tree.left) == 2) {
                AVLTreeNode<T> r =  tree.right;
                if (height(r.left) > height(r.right))
                    tree = rightLeftRotation(tree);
                else
                    tree = rightRightRotation(tree);
            }
        } else if (cmp > 0) {    // 待删除的节点在"tree的右子树"中
            tree.right = remove(tree.right, z);
            // 删除节点后，若AVL树失去平衡，则进行相应的调节。
            if (height(tree.left) - height(tree.right) == 2) {
                AVLTreeNode<T> l =  tree.left;
                if (height(l.right) > height(l.left))
                    tree = leftRightRotation(tree);
                else
                    tree = leftLeftRotation(tree);
            }
        } else {    // tree是对应要删除的节点。
            // tree的左右孩子都非空
            if ((tree.left!=null) && (tree.right!=null)) {
                if (height(tree.left) > height(tree.right)) {
                    // 如果tree的左子树比右子树高；
                    // 则(01)找出tree的左子树中的最大节点
                    //   (02)将该最大节点的值赋值给tree。
                    //   (03)删除该最大节点。
                    // 这类似于用"tree的左子树中最大节点"做"tree"的替身；
                    // 采用这种方式的好处是：删除"tree的左子树中最大节点"之后，AVL树仍然是平衡的。
                    AVLTreeNode<T> max = maximum(tree.left);
                    tree.key = max.key;
                    tree.left = remove(tree.left, max);
                } else {
                    // 如果tree的左子树不比右子树高(即它们相等，或右子树比左子树高1)
                    // 则(01)找出tree的右子树中的最小节点
                    //   (02)将该最小节点的值赋值给tree。
                    //   (03)删除该最小节点。
                    // 这类似于用"tree的右子树中最小节点"做"tree"的替身；
                    // 采用这种方式的好处是：删除"tree的右子树中最小节点"之后，AVL树仍然是平衡的。
                    AVLTreeNode<T> min = maximum(tree.right);
                    tree.key = min.key;
                    tree.right = remove(tree.right, min);
                }
            } else {
                AVLTreeNode<T> tmp = tree;
                tree = (tree.left!=null) ? tree.left : tree.right;
                tmp = null;
            }
        }

        return tree;
    }

    public void remove(T key) {
        AVLTreeNode<T> z; 

        if ((z = search(mRoot, key)) != null)
            mRoot = remove(mRoot, z);
    }

    /* 
     * 销毁AVL树
     */
    private void destroy(AVLTreeNode<T> tree) {
        if (tree==null)
            return ;

        if (tree.left != null)
            destroy(tree.left);
        if (tree.right != null)
            destroy(tree.right);

        tree = null;
    }

    public void destroy() {
        destroy(mRoot);
    }

    /*
     * 打印"二叉查找树"
     *
     * key        -- 节点的键值 
     * direction  --  0，表示该节点是根节点;
     *               -1，表示该节点是它的父结点的左孩子;
     *                1，表示该节点是它的父结点的右孩子。
     */
    private void print(AVLTreeNode<T> tree, T key, int direction) {
        if(tree != null) {
            if(direction==0)    // tree是根节点
                System.out.printf("%2d is root\n", tree.key, key);
            else                // tree是分支节点
                System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");

            print(tree.left, tree.key, -1);
            print(tree.right,tree.key,  1);
        }
    }

    public void print() {
        if (mRoot != null)
            print(mRoot, mRoot.key, 0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409

AVL树的测试程序(AVLTreeTest.java)

/**
 * Java 语言: AVL树
 *
 * @author skywang
 * @date 2013/11/07
 */

public class AVLTreeTest {
    private static int arr[]= {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};

    public static void main(String[] args) {
        int i;
        AVLTree<Integer> tree = new AVLTree<Integer>();

        System.out.printf("== 依次添加: ");
        for(i=0; i<arr.length; i++) {
            System.out.printf("%d ", arr[i]);
            tree.insert(arr[i]);
        }

        System.out.printf("\n== 前序遍历: ");
        tree.preOrder();

        System.out.printf("\n== 中序遍历: ");
        tree.inOrder();

        System.out.printf("\n== 后序遍历: ");
        tree.postOrder();
        System.out.printf("\n");

        System.out.printf("== 高度: %d\n", tree.height());
        System.out.printf("== 最小值: %d\n", tree.minimum());
        System.out.printf("== 最大值: %d\n", tree.maximum());
        System.out.printf("== 树的详细信息: \n");
        tree.print();

        i = 8;
        System.out.printf("\n== 删除根节点: %d", i);
        tree.remove(i);

        System.out.printf("\n== 高度: %d", tree.height());
        System.out.printf("\n== 中序遍历: ");
        tree.inOrder();
        System.out.printf("\n== 树的详细信息: \n");
        tree.print();

        // 销毁二叉树
        tree.destroy();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

== 依次添加: 3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9
== 前序遍历: 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16
== 中序遍历: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
== 后序遍历: 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7
== 高度: 5
== 最小值: 1
== 最大值: 16
== 树的详细信息:
is root
is 7’s left child
is 4’s left child
is 2’s left child
is 2’s right child
is 4’s right child
is 6’s left child
is 7’s right child
is 13’s left child
is 11’s left child
is 9’s left child
is 9’s right child
is 11’s right child
is 13’s right child
is 15’s left child
is 15’s right child

== 删除根节点: 8
== 高度: 5
== 中序遍历: 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16
== 树的详细信息:
is root
is 7’s left child
is 4’s left child
is 2’s left child
is 2’s right child
is 4’s right child
is 6’s left child
is 7’s right child
is 13’s left child
is 11’s left child
is 9’s right child
is 11’s right child
is 13’s right child
is 15’s left child
is 15’s right child

在这里插入图片描述

8.8多路查找树（b树） 341

要观察一个公司是否严谨，看他们如何开会就知道了。如果开会时每一个人都只是带一张嘴，即兴发言，这肯定是一家不严谨的公司。

多路查找树 (muitl-way search tree) ，其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之问存在某种特定的排序关系。

在这里，每一个结点可以存储多少个元素，以及它的孩子数的多少是非常关键的。为此，我们讲解宫的 4 种特殊形式: 2-3 树、 2-3-4 树、 B 树和 B+树。

8.8.1 2-3树 343

2-3 树是这样的一棵多路查找树;其中的每一个结点都具有两个孩子 (我们称它为 2 结点) 或三个孩子 (我们称它为 3 结点)。

一个 2 结点包含一个元素和两个孩子(或没有孩子) ，且与二叉排序树类似，左子树包含的元素小子该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同的是，这个 2 结点要么没有孩子，要有就有两个，不能只有一个孩子。

一个 3 结点包含一小一大两个元素和三个孩子(或没有孩子) ，一个 3 结点要么没有孩子，要么具有 3 个孩子。如果某个 3 结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。

并且 2-3 树中所有的叶子都在同一层次上。如图 8-8-2 所示，就是一棵有效的2-3 树。

事实上， 2-3 树复杂的地方就在于新结点的插入和已有结点的删除。毕竟，每个结点可能是 2 结点也可能是 3 结点，要保证所有叶子都在同一层次，是需要进行一番复杂操作的。

在这里插入图片描述

8.8.2 2-3-4树 348

有了 2-3 树的讲解， 2-3-4树就很好理解了，它其实就是 2-3 树的概念扩展，包括了 4 结点的使用。一个 4 结点包含小中大三个元素和四个孩子 (或没有孩子) ，一个 4结点要么没有孩子，要么具有 4 个孩子。如果某个 4 结点有孩子的话，左子树包含小于最小元素的元素; 第二子树包含大于最小元素，小于第二元素的元素;第三子树包含大于第二元素，小于最大元素的元素i 右子树包含大于最大元素的元素。

在这里插入图片描述

8.8.3b树 349

B 树 (B-tree)一种平衡的多路查找树， 2-3 树和 2-3-4 树都是 B 树的特例。结点最大的孩子数目称为B 树的阶 (order) ，因此， 2-3 树是 3 阶 B 树， 2-3-4 树是 4 阶 B树。
在这里插入图片描述
左侧灰色方块表示当前结点的元素个数。

在 B 树上查找的过程是-个顺时针查找结点和在结点中查找关键字的交叉过程。

比方说，我们要查找数字 7，首先从外存(比如硬盘中)读取得到根结点 3、 5、 8 三个元素，发现 7 不在当中，但在 5 和 8 之间，因此就通过 A2 再读取外存的 6、 7 结点，查找到所要的元素。

至于 B 树的插入和删除，方式是与 2-3 树和 2-3-4 树相类似的，只不过阶数可能会很大而已。

我们在本节的开头提到，如果内存与外存交换数据次数频繁，会造成了时间效率上的瓶颈，那么 B 树结构怎么就可以做到减少次数呢?

我们的外存，比如硬盘，是将所有的信息分割成相等大小的页面，每次硬盘读写的都是一个或多个完整的页面，对于一个硬盘来说，一页的长度可能是 211 到 214 个字节。

在一个典型的 B 树应用中，要处理的硬盘数据量很大，因此无法一次全部装入内存。因此我们会对 B 树进行调整，使得 B 树的阶数(或结点的元素)与硬盘存储的页面大小相匹配。比如说一棵 B 树的阶为 1001 (即 1 个结点包含 1000 个关键字) ，高度为 2，它可以储存超过 10 亿个关键字，我们只要让根结点持久地保留在内存中，那么在这棵树上，寻找某一个关键字至多需要两次硬盘的读取即可。这就好比我们普通人数钱都是一张一张的数，而银行职员数钱则是五张、十张，甚至几十张一数，速度当然是比常人快了不少。

通过这种方式，在有限内存的情况下，每一次磁盘的访问我们都可以获得最大数量的数据。由于 B 树每结点可以具有比二叉树多得多的元素，所以与二叉树的操作不同，它们减少了必须访问结点和数据块的数盟，从而提高了性能。可以说， B 树的数据结构就是为内外存的数据交互准备的。
在这里插入图片描述

8.8.4b+树 351

尽管前面我们已经讲了 B 树的诸多好处，但其实它还是有缺陷的。对于树结构来说，我们都可以通过中序遍历来顺序查找树中的元素，这一切都是在内存中进行。
在这里插入图片描述
为了说明这个解决的办法，我举个例子。一个优秀的企业尽管可能有非常成熟的树状组织结构，但是这并不意味着员工也很满意，恰恰相反，由于企业管理更多考虑的是企业的利益，这就容易忽略员工的各种诉求，造成了管理者与员工之间的矛盾。正因为此，工会就产生了，工会原意是指基于共同利益而自发组织的社会团体。这个共同利益团体诸如为同一雇主工作的员工，在某一产业领域的个人。工会组织成立的主要作用，可以与雇主谈判工资薪水、工作时限和工作条件等。这样，其实在整个企业的运转过程中，除了正规的层级管理外，还有一个代表员工的团队在发挥另外的作用。

在这里插入图片描述

8.9散列表查找（哈希表）概述 353

你很想学太极拳，听说学校有个叫张三丰的人打得特别好，于是到学校学生处找人，工作人员拿出学生名单，最终告诉你，学校没这个人，并说张三丰几百年前就已经在武当山作古了。

看一个实际需求，google公司的一个上机题:
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址…),当输入该员工的id时,要求查找到该员工的所有信息.
要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
15 111 % 15
在这里插入图片描述

google公司的一个上机题:
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,名字,住址…),当输入该员工的id时,要求查找到该员工的所有信息.
要求:
不使用数据库,速度越快越好=>哈希表(散列)
添加时，保证按照id从低到高插入 [课后思考：如果id不是从低到高插入，但要求各条链表仍是从低到高，怎么解决?]
使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息]
思路分析并画出示意图
代码实现[增删改查(显示所有员工，按id查询)]
在这里插入图片描述

package com.zcr.search;

import java.util.Scanner;

/**
 * @author zcr
 * @date 2019/7/8-9:06
 */
public class HashTableDemo {

    public static void main(String[] args) {

        //创建哈希表
        HashTable hashTable =new HashTable(7);

        //通过简单菜单测试
        String key = "";
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add：添加雇员");
            System.out.println("list：显示雇员");
            System.out.println("exit：退出系统");
            System.out.println("find：查找雇员");
            key = scanner.next();
            switch (key) {
                case "add":
                    System.out.println("输入id");
                    int id = scanner.nextInt();
                    System.out.println("输入名字");
                    String name = scanner.next();
                    //创建雇员
                    Emp emp = new Emp(id,name);
                    hashTable.add(emp);
                    break;
                case "list":
                    hashTable.list();
                    break;
                case "find":
                    System.out.println("请输入要查找的id");
                    id = scanner.nextInt();
                    hashTable.findEmpById(id);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }

    }
}

//表示一个雇员
class Emp {
    public int id;
    public String name;
    public Emp next;//默认为空

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

//创建一个EmpLinkedList，表示链表
class EmpLikedList {
    //头指针，指向第一个Emp，因此我们这个链表的head是直接指向第一个Emp的（没有头结点）
    private Emp head;//默认为空

    //添加雇员到链表
    //1.假定添加雇员的时候就是加在链表的最后
    //2.即id是自增长，id的分配总是从小到大
    public void add(Emp emp) {
        //如果是添加第一个雇员
        if (head == null) {
            head = emp;
            return;
        }
        //如果不是添加第一个雇员，则使用一个辅助指针，帮助定位到最后
        Emp curEmp = head;
        while (true) {
            if (curEmp.next == null) {//说明到链表最后
                break;
            }
            curEmp = curEmp.next;
        }
        //退出时，直接将emp加到最后
        curEmp.next = emp;
    }

    //遍历链表的雇员信息
    public void list(int no) {
        if (head == null) {//说明链表为空
            System.out.println("第"+(no+1)+"条链表为空");
            return;
        }
        System.out.print("第"+(no+1)+"条链表的信息为：");
        Emp curEmp = head;//辅助指针
        while (true) {
            System.out.printf("=> id = %d name = %s \t",curEmp.id,curEmp.name);
            if (curEmp.next == null) {//说明到链表最后
                break;
            }
            curEmp = curEmp.next;//后移，遍历
        }
        System.out.println();
    }

    //根据id查找雇员
    //如果查找到，就返回Emp，如果没有找到，就返回null
    public Emp findEmpById(int id) {
        //判断链表是否为空
        if (head == null) {
            System.out.println("链表为空");
            return null;
        }
        //辅助指针
        Emp curEmp = head;
        while (true) {
            if (curEmp.id == id) {//找到了
                break;//这时curEmp就指向要查找的雇员
            }
            //退出
            if (curEmp.next == null) {//说明遍历当前链表没有找到该雇员
                curEmp = null;
                break;
            }
            curEmp = curEmp.next;//后移
        }
        return curEmp;
    }


}

//创建哈希表，用来管理多条链表
class HashTable {
    private EmpLikedList[] empLikedListArray;
    private int size;//表示共有多少条链表

    //构造器
    public HashTable(int size) {
        //初始化哈希表
        this.size = size;
        empLikedListArray = new EmpLikedList[size];
        //留一个坑！！
        //这时不要忘了分别初始化每一条链表
        for (int i = 0; i < size; i++) {
            empLikedListArray[i] = new EmpLikedList();
        }
    }

    //添加雇员
    public void add(Emp emp) {
        //根据员工的id得到该员工应当添加到哪条链表
        int empLinkedListNO = hashFun(emp.id);
        //将雇员加入到对应的链表中
        empLikedListArray[empLinkedListNO].add(emp);
    }

    //遍历所有的链表，遍历哈希表
    public void list() {
        for (int i = 0; i < size; i++) {
            empLikedListArray[i].list(i);
        }
    }

    //根据输入的id查找雇员
    public void findEmpById(int id) {
        //使用散列函数确定到哪条链表查找

        int empLinkedListNO = hashFun(id);
        Emp emp = empLikedListArray[empLinkedListNO].findEmpById(id);
        if (emp != null){
            System.out.printf("在第%d条链表中找到该雇员id=%d\n",empLinkedListNO+1,id);
        } else {
            System.out.println("在哈希表中没有找到该雇员");
        }
    }

    //编写散列函数，使用一个简单取模法
    public int hashFun(int id) {
        return id % size;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

在这里插入图片描述

8.9.1散列表查找定义 354

学生处的老师找张三车，那就是顺序表查找，依赖的是姓名关键字的比较。而通过爱好运动的同学询问时，没有遍历，没有比较，就凭他们"欲找太极’张三卒’，必在体育馆当中"的经验，直接告诉你位置。

也就是说，我们只需要通过某个函数 f，使得存储位置=f (关键字）

那样我们可以通过查找关键字不需要比较就可获得需要的记录的存储位置。这就是一种新的存储技术一一散列技术。

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f (key)。查找时，根据这个确定的对应关系找到给定值 key 的映射 f (key) ，若查找集合中存在这个记录，则必定在 f (key) 的位置上。

这里我们把这种对应关系 f 称为散列函数，又称为哈希 (Hash) 函数。

按这个思想， 采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表 (Hash Table) 。

那么关键字对应的记录存储位置我们称为散列地址。

8.9.2散列表查找步骤 355

整个散列过程其实就是两步。
( 1) 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录。就像张三丰我们就让他在体育锚，那如果是’爱因斯坦’我们让他在图书馆，如果是 e居里夫人\那就让她在化学实验室，如果是 e 巴顿将军’，这个打仗的将军一一我们可以让他到网吧。总之，不管什么记录，我们都需要用同一个散列函数计算出地址再存储。

在这里插入图片描述
(2) 当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散到地址访问该记录。说起来很简单，在哪存的，上哪去找，由于存取用的是同一个散列函数，因此结果当然也是相同的。

所以说，散列技术既是一种存储方法，也是一种查找方法。然而它与线性表、树、图等结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，可以用连线圈示表示出来，而散列技术的记录之间不存在什么逻辑关系，它只与关键字有关联。因此，散列主要是面向查找的存储结构。

散列技术最适合的求解问题是查找与给定值相等的记录。对于查找来说，简化了比较过程，效率就会大大提高。但万事有利就有弊，散列技术不具备很多常规数据结构的能力。

比如那种同样的关键字，它能对应很多记景的情况，却不适合用散列技术。一个班级几十个学生，他们的性别有男有女，你用关键字"男’去查找，对应的有许多学生的记录，这显然是不合适的。只有如用班级学生的学号或者身份证号来散列存储，此时一个号码唯一对应一个学生才比较合适。

同样散列表也不适合范围查找，比如查找一个班级 18~22 岁的同学，在散列表中设法进行。想获得表中记录的排序也不可能，像最大值、最小值等结果也都无法从散列表中计算出来。

我们说了这么多，散到函数应该如何设计?这个我们需要重点来讲解，总之设计一个简单、均匀、存储利用率高的散列函数是散列技术中最关键的问题。
在这里插入图片描述

8.10散列函数的构造方法 356

那么什么才算是好的散列函数呢?这里我们有两个原则可以参考。
1.计算简单
你说设计一个算法可以保证所有的关键字都不会产生冲突，但是这个算法需要很复杂的计算，会耗费很多时间，这对于需要频繁地查找来说，就会大大降低查找的效率了。因此散列函数的计算时间不应该超过其他查找技术与关键字比较的时间。
2. 散列地址分布均匀
我们刚才也提到冲突带来的问题，最好的办法就是尽量让散列地址均匀地分布在存储空间中，这样可以保证存储空间的有效利用，并减少为处理冲突而耗费的时间。
接下来我们就要介绍几种常用的散列函数构造方法。估计设计这些方法的前辈们当年可能是从事阎谍工作，因为这些方法都是将原来数字按某种规律变成另一个数字而已。

8.10.1直接定址法 357

也就是说，我们可以取关键字的某个线性函数值为散列地址，即
f ( key ) =a x key+b (a、 b 为常数)

这样的散列函数优点就是简单、均匀，也不会产生冲突，但问题是这需要事先知道关键字的分布情况，适合查找表较小且连续的情况。由于这样的限制，在现实应用中，此方法虽然简单，但却并不常用。

8.10.2数字分析法 358

在这里插入图片描述

8.10.3平方取中法 359

这个方法计算很简单，假设关键字是 1234，那么它的平方就是 1522756，再抽取中间的 3 位就是 227 ，用做散列地址。再比如关键字是 4321，那么包的平方就是 18671041，抽取中间的 3 位就可以是 671 ，也可以是 710，用做散列地址。平方取中法比较适合子不知道关键字的分布，而位数又不是很大的情况。

8.10.4折叠法 359

折叠法是将关键字从左到右分割成位数相等的几部分(注意最后一部分位数不够时可以短些) ，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
比如我们的关键字是 9876543210 ，散列表表长为三位，我们将它分为四组， 9871654132110，然后将它们叠加求和 987+654+321+0=1962，再求后 3 位得到散列地址为 962。
有时可能这还不能够保证分布均匀，不妨从一端向另一端来回折叠后对齐相加。比如我们将 987 和 321 反转，再与 654 和 0 相加，变成 789+654+123+0=1566，此时散列地址为 566.
折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。

8.10.5除留余数法 359

在这里插入图片描述

，若散列表表长为 m，通常 p 为小于或等于表长(最好接近 m) 的最小质数或不包含小子 20 质因子的合数。

8.10.6随机数法 360

选择一个随机数，取关键字的随机函数值为它的散列地址。也就是 f (key) =random (key)。这里 random 是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

有同学问，那如果关键字是字符串如何处理?其实无论是英文字符，还是中文字符，也包括各种各样的符号，它们都可以转化为某种数字来对待，比如 ASCII 码或者 Unicoæ 码等，因此也就可以使用上面的这些方法。

总之，现实中，应该视不同的情况采用不同的散列函数。我们只能给出一些考虑的因素来提供参考:

计算散列地址所需的时间。
关键字的长度。
散列袤的大小。
关键字的分布情况。
记录查找的频率。综合这些因素，才能决策选择哪种散到函数吏合适。

8.11处理散列冲突的方法 360

我们每个人都希望身体健康，虽然疾病可以预防，但不可避免，没有任何人可以说，生下来到现在没有生过一次病。

我们设计得再好的散到函数也不可能完全避免冲突，么当我们在使用散列函数后发现两个关键字 keYl习t:keyz，但是却有 f (keYl) = f (keyz) ，即有冲突时，怎么办呢?我们可以从生活中找寻思路。试想一下，当你观望很久很久，终于看上一套房打算要买了，正准备下订金，人家告诉你，这房子已经被人买走了，你怎么办?
对呀，再找别的房子呗!这其实就是一种处理冲突的方法一一开放定址法。

8.11.1开放定址法 361

在这里插入图片描述

我们把这种解决冲突的开放定址法称为线性探测法。

从这个例子我们也看到，我们在解决冲突的时候，还会碰到如 48 和 37 这种本来都不是同义词却需要争夺一个地址的情况，我们称这种现象为堆积。很显然，堆积的出现，使得我们需要不断处理冲突，无论是存入还是查找效率都会大大降低。

在这里插入图片描述

8.11.2再散列函数法 363

在这里插入图片描述

8.11.3链地址法 363

思路还可以再换一换，为什么有冲突就要换地方呢，我们直接就在原地想办法不可以吗?于是我们就有了链地址法。

将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。对于关键字集合{12，67，S6，16，25.37， 22,29,lS,47,48,34} ，我们用前面同样的 12 为除数，进行除留余数法，可得到如图 8-11-1 结构，此时，已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链裴增加结点的问题。
在这里插入图片描述

8.11.4公共溢出区法 364

这个方法其实就更加好理解，你不是冲突吗?好吧，凡是冲突的都跟我走，我给你们这些冲突找个地儿待着。这就如同孤儿院收留所有无家可归的孩子一样，我们为所有冲突的关键字建立了一个公共的溢出区来存放.
就前面的例子而言，我们共有三个关键字{37，48，34}与之前的关键字位置有冲突，那么就将芭们存储到溢出表中，如图 8-11-2 所示.

在这里插入图片描述
在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功i 如果不相等，则到溢出表去进行j帧序查找。如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。

8.12散列表查找实现 365

8.12.1散列表查找算法实现 365

接下来建立一个简单的散列表，其散列函数采用上述的除留余数法，处理冲突的方法采用开放定址法下的线性探测法。

首先是需要定义一个散列表的结构以及一些相关的常数。其中 HashTable 就是散列表结构。结构当中的 elem 为一个动态数组。

Java代码如下：

package HashTable;
 
/**
 * 散列表
 * @author Yongh
 *
 */
public class HashTable {
    int[] elem;//数据元素存储基址，动态分配数据
    int count;//当前数据元素个数
    private static final int Nullkey = -32768;
 
    public HashTable(int count) {
        this.count = count;
        elem = new int[count];
        for (int i = 0; i < count; i++) {
            elem[i] = Nullkey; // 代表位置为空
        }
    }
 
    /*
     * 散列函数
     * 为了插入时计算地址，我们需要定义散列函数，散列函数可以根据不同情况更改 算法。
     */
    public int hash(int key) {
        return key % count; // 除留余数法
    }
 
    /*
     * 插入操作
     */
    public void insert(int key) {
        int addr = hash(key); // 求散列地址
        while (elem[addr] != Nullkey) { // 位置非空，有冲突
            addr = (addr + 1) % count; // 开放地址法的线性探测
        }
        elem[addr] = key;
    }
 
    /*
     * 查找操作
     * 查找的代码与插入的代码非常类似，只需做一个不存在关键字的判断而已。
     */
    public boolean search(int key) {
        int addr = hash(key); // 求散列地址
        while (elem[addr] != key) {
            addr = (addr + 1) % count; // 开放地址法的线性探测
            if (addr == hash(key) || elem[addr] == Nullkey) { // 循环回到原点或者到了空地址
                System.out.println("要查找的记录不存在！");
                return false;
            }
        }
        System.out.println("存在记录:" + key + ",位置为：" + addr);
        return true;
    }
 
    public static void main(String[] args) {
        int[] arr = { 12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34 };
        HashTable aTable = new HashTable(arr.length);
        for (int a : arr) {
            aTable.insert(a);
        }
        for (int a : arr) {
            aTable.search(a);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

存在记录:12,位置为：0
存在记录:67,位置为：7
存在记录:56,位置为：8
存在记录:16,位置为：4
存在记录:25,位置为：1
存在记录:37,位置为：2
存在记录:22,位置为：10
存在记录:29,位置为：5
存在记录:15,位置为：3
存在记录:47,位置为：11
存在记录:48,位置为：6
存在记录:34,位置为：9

代码中重点可以看：插入操作是如何处理冲突以及查找操作是如何判断记录是否存在的。

8.12.2散列表查找性能分析 367

最后，我们对散列表查拢的性能作一个简单分析。如果没有冲突，散列查找是我们本章介绍的所有查找中效率最高的，因为色的时间复杂度为 O(1)。可惜，我说的只是"如果"，没有冲突的散列只是一种理想，在实际的应用中，冲突是不可避免的。那么散列查找的平均查找长度取决于哪些因素呢?
1.散到函数是否均匀
散列函数的好坏直接影响着出现冲突的频繁程度，不过，由于不同的散列函数对同一组随机的关键字，产生冲突的可能性是相同的，因此我们可以不考虑它对平均查找长度的影响。

2.处理冲突的方法
相同的关键字、相同的散列函数，但处理冲突的方法不同，会使得平均查找长度不同。比如线性探测处理冲突可能会产生堆积，显然就没有二次探测法好，而链地址法处理冲突不会产生任何堆积，因而具有更佳的平均查找性能。

3.散到袤的装填因子
所谓的装填因子α=填入表中的记录个数/散列表长度。 α标志着散列袤的装满的程度。当填入表中的记录越多， α就越大，产生冲突的可能性就越大。比如我们前面的例子，如图 8-11-5 所示，如果你的散列表长度是 12 ，而填人表中的记录个数为 11，那么此时的装填因子α=11/12=0.9167，再填人最后一个关键字产生冲突的可能性就非常之大。也就是说，散列袤的平均查找长度取决于装模困子，而不是取决于查找集合中的记录个数。

不管记录个数 n 有多大，我们总可以选择一个合适的装填因子以便将平均查找长度限定在一个范围之内，此时我们散列查找的时间复杂度就真的是 0(1)了。为了做到这一点，通常我们都是将散列袤的空间设置得比查找集合大，此时虽然是浪费了一定的空间，但换来的是查找效率的大大提升，总的来说，还是非常值得的。

8.13总结回顾 368

我们这一章全都是围绕一个主题"查找’来作文章的。

首先我们耍弄清楚查找表、记录、关键字、主关键字、静态查找表、动态查找表等这些概念。

然后，对于顺序表查找来说，尽管很土 (简单) ，但它却是后面很多查找的基础，注意设置"哨兵"的技巧，可以使得本已经很难提升的简单算法里还是提高了性能。

有序查找，我们着重讲了折半查找的思想，包在性能上比原来的顺序查找有了质的飞跃，自 O(n)变成了 O(logn)。之后我们又讲解了另外两种优秀的有序查找: 插值查找和斐被那契查找，三者各有优缺点，望大家要仔细体会。

线性索引查找，我们讲解了稠密索引、分块索引和倒排索引。索引技术被广泛的用于文件检索、数据库和搜索引擎等技术领域，是进一步学习这些技术的基础。

二叉排序树是动态、查找最重要的数据结构，它可以在兼顾查找性能的基础上，让插入和删除也变得效率较高。不过为了达到最优的状态，二叉排序树最好是构造成平衡的二叉树才最佳。因此我们就需要再学习关于平衡二叉树 (AVL 树)的数据结构，了解 A叽树是如何处理平衡’性的问题。这部分是本章重点，需要认真学习掌握。

B 树这种数据结构是针对内存与外存之间的存取而专门设计的。由于内外存的查找性能更多取决于读取的次数，因此在设计中要考虑 B 树的平衡和层次。我们讲解时是先通过最最简单的 B 树 (2-3 树)来理解如何构建、插入、删除元素的操作，再通过 2-3-4 树的深化，最终来理解 8 树的原理。之后，我们还介绍了 b树的设计思想。

散列表是一种非常高效的查找数据结构，在原理上也与前面的查找不尽相同，它回避了关键字之间反复比较的烦琐，而是直接一步到位查找结果。当然，这也就带来了记录之间没有任何关联的弊端。应该说，散列表对于那种查找性能要求高，记录之间关系无要求的数据有非常好的适用性。在学习中要注意的是散列函数的选择和处理冲突的方法。

8.14结尾语 369

如果我是个喜欢汽车的人，时常搜汽车信息。那么当我在搜索框中输入“甲壳虫”、“美洲虎”等关键词时，不要让动物和人物成为搜索的头条。

第9章排序 373

在这里插入图片描述

9.1开场白 374

假如我想买一台iphone4的手机，于是上了某电子商务网站去搜索。可搜索后发现，有8863个相关的物品，如此之多，这叫我如何选择。我其实是想买便宜一点的，但是又怕遇到骗子，想找信誉好的商家，如何做？

在这里插入图片描述

排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。
排序的分类：

内部排序:
指将需要处理的所有数据都加载到内部存储器中进行排序。
外部排序法：
数据量过大，无法全部加载到内存中，需要借助外部存储进行
排序。
常见的排序算法分类(见右图):

度量一个程序(算法)执行时间的两种方法
事后统计的方法这种方法可行, 但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快。
事前估算的方法通过分析某个算法的时间复杂度来判断哪个算法更优.

时间频度
基本介绍
时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。[举例说明]

举例说明-基本案例
比如计算1-100所有数字之和, 我们设计两种算法：
在这里插入图片描述
忽略常数项

结论:
2n+20 和 2n 随着n 变大，执行曲线无限接近, 20可以忽略
3n+10 和 3n 随着n 变大，执行曲线无限接近, 10可以忽略

忽略低次项
在这里插入图片描述

结论:
2n^2+3n+10 和 2n^2 随着n 变大, 执行曲线无限接近, 可以忽略 3n+10
n^2+5n+20 和 n^2 随着n 变大,执行曲线无限接近, 可以忽略 5n+20

忽略系数
在这里插入图片描述

结论:
随着n值变大，5n^2+7n 和 3n^2 + 2n ，执行曲线重合, 说明这种情况下, 5和3可以忽略。
而n^3+5n 和 6n^3+4n ，执行曲线分离，说明多少次方式关键

时间复杂度

一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。

T(n) 不同，但时间复杂度可能相同。如：T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的T(n) 不同，但时间复杂度相同，都为O(n²)。
计算时间复杂度的方法：

用常数1代替运行时间中的所有加法常数 T(n)=n²+7n+6 => T(n)=n²+7n+1
修改后的运行次数函数中，只保留最高阶项 T(n)=n²+7n+1 => T(n) = n²
去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²)

常见的时间复杂度

常数阶O(1)
对数阶O(log2n)
线性阶O(n)
线性对数阶O(nlog2n)
平方阶O(n^2)
立方阶O(n^3)
k次方阶O(n^k)
指数阶O(2^n)

说明：
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) ，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低
从图中可见，我们应该尽可能避免使用指数阶的算法
在这里插入图片描述

常见的时间复杂度

常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)
在这里插入图片描述
上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。

常见的时间复杂度
对数阶O(log2n)
在这里插入图片描述
说明：在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2n也就是说当循环 log2n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(log2n) 。 O(log2n) 的这个2 时间上是根据代码变化的，i = i * 3 ，则是 O(log3n) .
在这里插入图片描述

常见的时间复杂度
线性阶O(n)
在这里插入图片描述
说明：这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度

常见的时间复杂度
线性对数阶O(nlogN)
在这里插入图片描述
说明：线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)

常见的时间复杂度
平方阶O(n²)
在这里插入图片描述
说明：平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)，这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(nn)，即 O(n²) 如果将其中一层循环的n改成m，那它的时间复杂度就变成了 O(mn)

常见的时间复杂度
立方阶O(n³)、K次方阶O(n^k)

说明：参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似

平均时间复杂度和最坏时间复杂度
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
平均时间复杂度和最坏时间复杂度是否一致，和算法有关(如图:)。
在这里插入图片描述

算法空间复杂度
基本介绍
类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况
在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.

9.2排序的基本概念与分类 375

比如我们某些大学为了选拔在主科上更优秀的学生，要求对所有学生的所有科目总分倒序排名，并且在同样总分的情况下将语数外总分做倒序排名。这就是对总分和语数外总分两个次关键字的组合排序。
在这里插入图片描述
从这个例子也可看出，多个关键字的排序最终都可以转化为单个关键字的排序，因此，我们这里主要讨论的是单个关键字的排序。

9.2.1排序的稳定性 376

在这里插入图片描述

9.2.2内排序与外排序 377

根据在排序过程中待排序的记录是否全部被放置在内存中，排序分为:内排序和外排序。

内排序是在排序整个过程中，待排序的所有记录全部被就置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。我们这里主要就介绍内排序的多种方法。

对于内排序来说，排序算法的性能主要是受 3 个方面影响:

1.时间性能
排序是数据处理中经常执行的一种操作，往往属于系统的核心部分，因此排序算法的时间开销是衡量其好坏的最重要的标志。在内排序中，主要进行两种操作:比较和移动。
比较指关键字之间的比较，这是要做排序最起码的操作。
移动指记录从一个位置移动到另一个位置，事实上，移动可以通过改变记录的存储方式来予以避免(这个我们在讲解具体的算法时再谈)。总之，高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。

2.辅助空间
评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。

3.算法的复杂性
注意这里指的是算法本身的复杂度，而不是指算法的时间复杂度。显然算法过于复杂也会影响排序的性能。
根据排序过程中借助的主要操作，我们把内排序分为:插入排序、交换排序、选择排序和归并排序。可以说，这些都是比较成熟的排序技术，已经被广泛地应用于许许多多的程序语言或数据库当中，甚至它们都已经封装了关于排序算法的实现代码。因此，我们学习这些排序算法的目的更多并不是为了去在现实中编程排序算法，而是通过学习来提高我们编写算法的能力，以便于去解决更多复杂和灵活的应用性问题。
本章一共要讲解七种排序的算法，按照算法的复杂度分为两大类，冒泡排序、简单选择排序和直接插入排序属于简单算法，而希尔排序、堆排序、归并排序、快速排序属于改进算法。后面我们将依次讲解。

9.2.3排序用到的结构与函数 378

为了讲清楚排序算法的代码，我先提供一个用于排序用的顺序表结构，此结构也将用于之后我们要讲的所有排序算法。
在这里插入图片描述

9.3冒泡排序 378

基本介绍

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，在进行)
在这里插入图片描述
冒泡排序应用实例

我们举一个具体的案例来说明冒泡法。我们将五个无序的数：3, 9, -1, 10, -2 使用冒泡排序法将其排成一个从小到大的有序数列。
在这里插入图片描述

5个数有4个数已经定下来了，所以只需要4趟就好。一共进行数组大小-1次排序；每一趟排序的次数在逐渐地减少；

package com.zcr.sort;

import javafx.scene.input.DataFormat;


import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author zcr
 * @date 2019/7/6-22:54
 */
public class BubbleSort {

    public static void main(String[] args) {
        //int arr[] = {3,9,-1,10,20};

        //int temp = 0;//临时变量

        /*//为了容易理解，我们把冒泡排序的过程给展示出来
        //第一趟排序，就是将最大的那个数排在最后
        for (int i = 0; i < arr.length - 1; i++) {//一共比较数组大小-1-0次
            //如果前面的数比后面的大，则交换
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] =temp;
            }
        }
        System.out.println("第一趟排序后的数组：");
        System.out.println(Arrays.toString(arr));

        //第二趟排序，就是将第二大的数排在倒数第二位
        for (int i = 0; i < arr.length - 1 - 1; i++) {//一共比较数组大小-1-1次
            //如果前面的数比后面的大，则交换
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] =temp;
            }
        }
        System.out.println("第二趟排序后的数组：");
        System.out.println(Arrays.toString(arr));

        //第三趟排序，就是将第三大的数排在倒数第三位
        for (int i = 0; i < arr.length - 1 - 2; i++) {//一共比较数组大小-1-2次
            //如果前面的数比后面的大，则交换
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] =temp;
            }
        }
        System.out.println("第三趟排序后的数组：");
        System.out.println(Arrays.toString(arr));

        //第四趟排序，就是将第四大的数排在倒数第四位
        for (int i = 0; i < arr.length - 1 - 3; i++) {//一共比较数组大小-1-3次
            //如果前面的数比后面的大，则交换
            if (arr[i] > arr[i + 1]) {
                temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] =temp;
            }
        }
        System.out.println("第四趟排序后的数组：");
        System.out.println(Arrays.toString(arr));*/

        //一共要进行数组长度-1趟排序
        //冒泡排序
        /*for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 -i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] =temp;
                }
            }
            System.out.println("第"+ (i+1) +"趟排序后的数组：");
            System.out.println(Arrays.toString(arr));
        }
*/
        //时间复杂度O(n2)

        //冒泡排序的优化
        /*boolean flag = false;//表示是否进行过交换
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 -i; j++) {
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] =temp;
                }
            }
            System.out.println("第"+ (i+1) +"趟排序后的数组：");
            System.out.println(Arrays.toString(arr));

            if (!flag) {//在这一趟排序中，一次交换都没有发生过
                break;
            } else {
                flag = false;//重置flag,进行下次判断
            }
        }*/

        //测试冒泡排序
        /*System.out.println(Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("排序后的数组：");
        System.out.println(Arrays.toString(arr));*/

        //测试一下冒泡排序的速度，事前O(n2)，事后
        //创建一个8万个随机数的数组
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int)Math.random() * 80000;//会生成一个0~80000的随机数
        }
        //System.out.println(Arrays.toString(arr));
        /*Date date1 = new Date();
        SimpleDateFormat df1 = new SimpleDateFormat("yyyy-MM-dd HH-mm-ss");
        String date1str = df1.format(date1);
        System.out.println("排序前的时间是："+date1str);
        bubbleSort(arr);
        Date date2 = new Date();
        String date2str = df1.format(date1);
        System.out.println("排序后的时间是："+date2str);*/
        long l1 = System.currentTimeMillis();
        bubbleSort(arr);
        long l2  = System.currentTimeMillis();
        System.out.println(l2 - l1);



    }

    //将前面的冒泡排序算法，封装成一个方法
    public static void bubbleSort(int[] arr) {
        int temp = 0;//临时变量
        boolean flag = false;//表示是否进行过交换
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 -i; j++) {//一共比较数组大小-1-i次
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] =temp;
                }
            }
            //System.out.println("第"+ (i+1) +"趟排序后的数组：");
            //System.out.println(Arrays.toString(arr));

            if (!flag) {//在这一趟排序中，一次交换都没有发生过
                break;
            } else {
                flag = false;//重置flag,进行下次判断
            }
        }

    }
    
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

无论你学习哪种编程语言，在学到循环和数组时，通常都会介绍一种排序算法，而这个算法一般就是冒泡排序。并不是它的名称很好听，而是说这个算法的思路最简单，最容易理解。
下面为交换元素的swap()方法代码，后面代码中将直接使用。

public void swap(int[] a, int i, int j) {
    int temp;
    temp = a[j];
    a[j] = a[i];
    a[i] = temp;
}
1
2
3
4
5
6

9.3.1最简单排序实现 379

冒泡排序 (Bubble Sort) 一种交换排序，基本思想是:两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止.冒泡的实现在细节上可以有很多种变化，我们将分别就 3 种不同的冒泡实现代码，来讲解冒泡排序的思想。这里，我们就先来看看比较容易理解的一段。
基本思想：将相邻的元素两两比较，根据大小关系交换位置，直到完成排序。

对n个数组成的无序数列，进行n轮排序，每轮按两两比较的方法找出最小（或最大）的一个。下图表示某数列的第一轮排序。

在这里插入图片描述

初级版本
根据基本思想，可以写出初级版本的冒泡排序如下：

public void bubbleSort0(int[] a) {
    if(a==null) return;
    // 代表第i轮排序
    for (int i = 1; i < a.length; i++) {//第几趟
        for (int j = a.length - 1; j >= i; j--) {//j从后往前循环
            if (a[j] > a[j + 1]) {//若前者大于后者（注意这里是与上一算法的差异）
                swap(a, j, j+1);//交换
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

在这里插入图片描述
当 i=2 时，变量 j 由 8 反向循环到 2，逐个比较，在将关键字 2 交换到第二位置的同时，也将关键字 4 和 3 有所提升。

9.3.2冒泡排序算法 380

第一次优化版本
　　当数据基本有序时，可能前几轮循环就完成了排序，后面的循环就没有必要继续进行了，如下图所示：
　　。试想一下，如果我们待排序的序列是{2.1，3.4.5.6几8.9}，也就是说，除了第一和第二的关键字需要交换外，别的都已经是正常的顺序。当 i=l 时，交换了 2 和 1 ，此时序列已经有序，但是算法仍然不依不饶地将 i=2 到 9 以及每个循环中的 j 循环都执行了一遍，尽管并没有交换数据，但是之后的大量比较还是大大地多余了
在这里插入图片描述
对这种情况，可以在代码中增加一个标记，用于标记每轮循环时代码是否已经有序，在每轮循环开始前，如果有序的话就没有必要继续进行比较了。具体Java代码如下：

public void bubbleSort1(int[] a) {
    if(a==null) return;
    boolean isSorted = false; // false代表数据无序，需要排序
    for (int i = 0; i < a.length && !isSorted; i++) { // 数据无序时还要继续循环！则有序的时候就直接退出不循环了！
        isSorted = true; // 假设这轮循环开始时已经有序
        for (int j = a.length - 1; j > i; j--) {
            if (a[j] < a[j - 1]) {
                swap(a, i, j);
                isSorted = false; // 有发生交换，说明这轮循环还是无序的
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

9.3.3冒泡排序优化 382

第二次优化版本
　　当数列的前半部分有序而后半部分无序时，每轮循环没必要再对有序部分进行排序，例如，数列为{1，2，3，4，9，5，8，7}时，在一次循环后知道1，2，3，4已经有序，后面的循环就没必要对这些数字进行排序了。

此时，关键点在于对有序区的界定：如果知道有序区的边界，那么每次循环就只需要比较到该边界即可。在每次循环的最后，记录下最后一次元素交换的位置，该位置就是有序区的边界了。具体Java代码如下：

public void bubbleSort2(int[] a) {
    if(a==null) return;
    int lastExchangeIndex = 0; // 用于记录每轮循环最后一次交换的位置
    int sortBorder = 0; // 有序数组的边界，每次比较只要比较到这里就可以
    boolean isSorted = false;
    for (int i = 0; i < a.length && !isSorted; i++) {
        isSorted = true;
        for (int j = a.length - 1; j > sortBorder; j--) {
            if (a[j] < a[j - 1]) {
                swap(a, i, j);
                isSorted = false;
                lastExchangeIndex = j; // 本轮最后一次交换位置（不断更新）
            }
        }
        sortBorder = lastExchangeIndex; // 边界更新为最后一次交换位置
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

完整Java代码
（含测试代码）

import java.util.Arrays;
 
/**
 *
 * @Description 冒泡排序(从小到大）
 *
 * @author yongh
 * @date 2018年9月13日 下午3:21:38
 */
public class BubbleSort {
 
    /**
     * 初级版本
     */
    public void bubbleSort0(int[] a) {
        if(a==null) return;
        // 代表第i轮排序
        for (int i = 0; i < a.length; i++) {
            for (int j = a.length - 1; j > i; j--) {
                if (a[j] < a[j - 1]) {
                    swap(a, i, j);
                }
            }
        }
    }
 
    /**
     * 优化版本
     * 添加一个标记isSorted
     */
    public void bubbleSort1(int[] a) {
        if(a==null) return;
        boolean isSorted = false; // false代表数据无序，需要排序
        for (int i = 0; i < a.length && !isSorted; i++) { // 数据无序时还要继续循环
            isSorted = true; // 假设这轮循环开始时已经有序
            for (int j = a.length - 1; j > i; j--) {
                if (a[j] < a[j - 1]) {
                    swap(a, i, j);
                    isSorted = false; // 有发生交换，说明这轮循环还是无序的
                }
            }
        }
    }
 
    /**
     * 进一步优化版本
     */
    public void bubbleSort2(int[] a) {
        if(a==null) return;
        int lastExchangeIndex = 0; // 用于记录每轮循环最后一次交换的位置
        int sortBorder = 0; // 有序数组的边界，每次比较只要比较到这里就可以
        boolean isSorted = false;
        for (int i = 0; i < a.length && !isSorted; i++) {
            isSorted = true;
            for (int j = a.length - 1; j > sortBorder; j--) {
                if (a[j] < a[j - 1]) {
                    swap(a, i, j);
                    isSorted = false;
                    lastExchangeIndex = j; // 本轮最后一次交换位置（不断更新）
                }
            }
            sortBorder = lastExchangeIndex; // 边界更新为最后一次交换位置
        }
    }
     
    /**
     * 交换代码
     */
    public void swap(int[] a, int i, int j) {
        int temp;
        temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }
     
    //=========测试代码=======
    public void test1() {
        int[] a = null;
        bubbleSort2(a);
        System.out.println(Arrays.toString(a));
    }
 
 
    public void test2() {
        int[] a = {};
        bubbleSort2(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test3() {
        int[] a = { 1 };
        bubbleSort2(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test4() {
        int[] a = { 3, 3, 3, 3, 3 };
        bubbleSort2(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test5() {
        int[] a = { -3, 6, 3, 1, 3, 7, 5, 6, 2 };
        bubbleSort2(a);
        System.out.println(Arrays.toString(a));
    }
     
     
    public static void main(String[] args) {;
        BubbleSort demo = new BubbleSort();    
        demo.test1();
        demo.test2();
        demo.test3();
        demo.test4();
        demo.test5();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

null
[]
[1]
[3, 3, 3, 3, 3]
[3, 3, -3, 5, 2, 7, 1, 6, 6]

9.3.4冒泡排序复杂度分析 383

总结
　　冒泡排序原理近似于气泡在水里慢慢上浮到水面上，实现容易，但也有改进的空间，

改进1：若前几轮已经有序，则后面就没必要继续比较了，因此增加一个isSorted标记，对每轮是否有序进行标记。

改进2：一部分有序，则没必要继续对有序区比较，增加一个sortBorder来定义有序区边界，每次比较到该边界即可。该边界由每轮循环中最后一次元素交换的位置得到。

时间复杂度：O(n^2)

在这里插入图片描述

9.4简单选择排序 384

还有一种做股票的人，他们很少出手，只是在不断观察和判断，等时机一到，果断买进或卖出。他们因为冷静和沉着，以及交易的次数少，而最终收益颇丰。

基本介绍
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

选择排序思想:
选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]_{arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]}arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]_{arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]}arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

选择排序思路分析图:
101, 34, 119, 1

在这里插入图片描述

选择排序应用实例:
有一群牛 , 颜值分别是 101, 34, 119, 1 请使用选择排序从低到高进行排序 [101, 34, 119, 1]
说明: 测试效率的数据 80000，看耗时

package com.zcr.sort;

import java.util.Arrays;

/**
 * @author zcr
 * @date 2019/7/7-8:59
 */
public class SelectSort {

    public static void main(String[] args) {
        //int[] arr = {101,34,119,1};

        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int)(Math.random() * 80000);//会生成一个0~80000的随机数
        }

        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));
        long l1 = System.currentTimeMillis();
        selectSort(arr);
        long l2  = System.currentTimeMillis();
        System.out.println(l2 - l1);
        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));

    }

    //选择排序
    public static void selectSort(int[] arr) {

        //使用逐步推导的方式。可以把一个复杂的算法拆分成简单的问题，然后逐步解决。最后综合
        //第一轮
        //原始数组：101,34,119,1
        //第一轮排序：1,34,119,101
        /*int minIndex = 0;
        int min = arr[minIndex];
        for (int i = 0 + 1; i < arr.length; i++) {//从下标为1的开始一直到最后（下标为0的为最小值）
            if (min > arr[i]) {//说明我们假定的最小值并不是最小
                min = arr[i];//重置最小值
                minIndex = i;//重置最小的的下标值
            }
        }
        //将最小值放在arr[0]，把arr[0]放在最小值的位置
        if (minIndex != 0){
            arr[minIndex] = arr[0];//把arr[0]放在最小值的位置
            arr[0] = min;//将最小值放在arr[0]
        }
        System.out.println("第一轮后：");
        System.out.println(Arrays.toString(arr));//1,34,119,101

        //第二轮
        minIndex = 1;
        min = arr[1];
        for (int i = 1 + 1; i < arr.length; i++) {//从下标为2的 开始一直到最后（下标为1的为最小值）
            if (min > arr[i]) {//说明我们假定的最小值并不是最小
                min = arr[i];//重置最小值
                minIndex = i;//重置最小的的下标值
            }
        }
        //将最小值放在arr[0]，把arr[0]放在最小值的位置
        if (minIndex != 1){
            arr[minIndex] = arr[1];//把arr[0]放在最小值的位置
            arr[1] = min;//将最小值放在arr[0]
        }
        System.out.println("第二轮后：");
        System.out.println(Arrays.toString(arr));//1,34,119,101

        //第三轮
        minIndex = 2;
        min = arr[2];
        for (int i = 2 + 1; i < arr.length; i++) {//从下标为3的开始一直到最后（下标为2的为最小值）
            if (min > arr[i]) {//说明我们假定的最小值并不是最小
                min = arr[i];//重置最小值
                minIndex = i;//重置最小的的下标值
            }
        }
        //将最小值放在arr[0]，把arr[0]放在最小值的位置
        if (minIndex != 2){
            arr[minIndex] = arr[2];//把arr[0]放在最小值的位置
            arr[2] = min;//将最小值放在arr[0]
        }
        System.out.println("第三轮后：");
        System.out.println(Arrays.toString(arr));//1,34,101，119*/


        //一共要进行数组长度-1趟循环
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {//从下标为i+1的开始一直到最后（下标为i的为最小值）
                if (min > arr[j]) {//说明我们假定的最小值并不是最小
                    min = arr[j];//重置最小值
                    minIndex = j;//重置最小的的下标值
                }
            }
            //将最小值放在arr[0]，把arr[0]放在最小值的位置
            if (minIndex != i){
                arr[minIndex] = arr[i];//把arr[i]放在最小值的位置
                arr[i] = min;//将最小值放在arr[i]
            }
            /*System.out.println("第"+ (i+1) + "轮后：");
            System.out.println(Arrays.toString(arr));*/
        }


    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

冒泡排序的思想就是不断地在交换，通过交换完成最终的排序，这和做股票短线频繁操作的人是类似的。我们可不可以像只有在时机非常明确到来时才出手的股票高手一样，也就是在排序时找到合适的关键字再做交换，并且只移动一次就完成相应关键字的排序定位工作呢?这就是选择排序法的初步思想。
选择排序的基本思想是每一趟在 n一 i+ l(i=1，2，…n一 1)个记录中选取关键字最小的记录作为有序序列的第 i 个记录。我们这里先介绍的是简单选择排序法。

9.4.1简单选择排序算法 384

在这里插入图片描述

之后的数据比较和交换完全雷同，最多经过 8 次交换，就可完成排序工作。

9.4.2简单选择排序复杂度分析 385

在这里插入图片描述

9.5直接插入排序 386

哪怕你是第一次玩扑克牌，只要认识这些数字，理牌的方法都是不用教的。将3和4移动到5的左侧，再将2移动到最左侧，顺序就算是理好了。这里，我们的理牌方法，就是直接插入排序法。

插入排序法介绍:
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

插入排序法思想:
插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

在这里插入图片描述
插入排序法应用实例:
有一群小牛, 考试成绩分别是 101, 34, 119, 1 请从小到大排序

package com.zcr.sort;

import java.util.Arrays;

/**
 * @author zcr
 * @date 2019/7/7-9:53
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {101,34,119,1,-1,89};
        insertSort(arr);
        /*int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int)(Math.random() * 80000);//会生成一个0~80000的随机数
        }

        System.out.println("排序前：");
        //System.out.println(Arrays.toString(arr));
        long l1 = System.currentTimeMillis();
        insertSort(arr);
        long l2  = System.currentTimeMillis();
        System.out.println(l2 - l1);
        System.out.println("排序后：");*/
        System.out.println(Arrays.toString(arr));
    }

    //插入排序
    public static void insertSort(int[] arr) {
        //使用逐步推导的方式讲解

        //第一轮 [34 101] 119 1
        //定义待插入的数
        /*int insertVal = arr[1];
        int insertIndex = 0;//1-1，即arr[1]的前面这个数的下标
        //给insertVal找到插入的位置
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {//保证在找插入位置时不越界，保证待插入的数还没有找到插入位置
            //当前的arr[insertIndex]后移
            arr[insertIndex + 1] = arr[insertIndex];//101 101 119 1
            insertIndex--;//与前面那个数比较
        }
        //当退出while循环时，说明插入的位置找到，insertIndex + 1
        arr[insertIndex + 1] = insertVal;
        System.out.println("第一轮插入后：");
        System.out.println(Arrays.toString(arr));

        //第二轮 [34 101 119 ]  1
        //定义待插入的数
        insertVal = arr[2];
        insertIndex = 1;//2-1，即arr[1]的前面这个数的下标
        //给insertVal找到插入的位置
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {//保证在找插入位置时不越界，保证待插入的数还没有找到插入位置
            //当前的arr[insertIndex]后移
            arr[insertIndex + 1] = arr[insertIndex];//
            insertIndex--;//与前面那个数比较
        }
        //当退出while循环时，说明插入的位置找到，insertIndex + 1
        arr[insertIndex + 1] = insertVal;
        System.out.println("第二轮插入后：");
        System.out.println(Arrays.toString(arr));

        //第二轮 [1 34 101 119]
        //定义待插入的数
        insertVal = arr[3];
        insertIndex = 2;//3-1，即arr[1]的前面这个数的下标
        //给insertVal找到插入的位置
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {//保证在找插入位置时不越界，保证待插入的数还没有找到插入位置
            //当前的arr[insertIndex]后移
            arr[insertIndex + 1] = arr[insertIndex];//
            insertIndex--;//与前面那个数比较
        }
        //当退出while循环时，说明插入的位置找到，insertIndex + 1
        arr[insertIndex + 1] = insertVal;
        System.out.println("第三轮插入后：");
        System.out.println(Arrays.toString(arr));*/

        //进行数组长度-1次（因为第一个为基准，给后面的几个数找位置）
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int insertIndex = i - 1;//i-1，即arr[1]的前面这个数的下标
            //给insertVal找到插入的位置
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {//保证在找插入位置时不越界，保证待插入的数还没有找到插入位置
                //当前的arr[insertIndex]后移
                arr[insertIndex + 1] = arr[insertIndex];//101 101 119 1
                insertIndex--;//与前面那个数比较
            }
            //当退出while循环时，说明插入的位置找到，insertIndex + 1
            //判断是否需要赋值
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertVal;
            }
            //System.out.println("第"+ i +"轮插入后：");
            //System.out.println(Arrays.toString(arr));
        }


    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

9.5.1直接插入排序算法 386

直接插入排序思路：类似扑克牌的排序过程，从左到右依次遍历，如果遇到一个数小于前一个数，则将该数插入到左边所有比自己大的数之前，也就是说，将该数前面的所有更大的数字都后移一位，空出来的位置放入该数。

直接插入排序(如-aight Insertion Sort) 的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增 1 的有序表。
顾名思义，从名称上也可以知道它是一种插入排序的方法。我们来看直接插入排
序法的代码。

public void insertSort(int[] arr) {
    if(arr==null || arr.length<=0)
        return;
    for(int i=1;i<arr.length;i++) {
        if(arr[i]<arr[i-1]) {
            int temp=arr[i];
            int j=i;
            while(j>0 && temp<arr[j-1]) {
                arr[j]=arr[j-1];
                j--;
            }
            arr[j]=temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

空间复杂度：O(1)

时间复杂度：O(n^2)

9.5.2直接插入排序复杂度分析 388

9.6希尔排序 389

不管怎么说，希尔排序算法的发明，使得我们终于突破了慢速排序的时代（超越了时间复杂度为o(n2)），之后，更为高效的排序算法也就相继出现了。

简单插入排序存在的问题
我们看简单的插入排序可能存在的问题.
数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.

希尔排序法介绍
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

希尔排序法基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止

在这里插入图片描述

希尔排序法应用实例:
有一群小牛, 考试成绩分别是 {8,9,1,7,2,3,5,4,6,0} 请从小到大排序. 请分别使用
希尔排序时，对有序序列在插入时采用交换法, 并测试排序速度. 好理解，速度慢
希尔排序时，对有序序列在插入时采用移动法, 并测试排序速度不好理解，速度快

package com.zcr.sort;

import java.util.Arrays;

/**
 * @author zcr
 * @date 2019/7/7-10:35
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        shellSort2(arr);
    }

    //希尔排序
    public static void shellSort(int[] arr) {
        //使用逐步推导的方式编写

        //第一轮
        //因为第一轮排序是将10个数据分成了5组
        /*int temp = 0;
        for (int i = 5;i < arr.length;i++) {
            //遍历各组中所有的元素（共五组，每一组有2个元素）
            for (int j = i - 5; j >= 0 ; j -= 5) {
                //如果当前元素大于加上步长后的那个元素，说明需要交换
                if (arr[j] > arr[j + 5]) {
                    temp = arr[j];
                    arr[j] = arr[j + 5];
                    arr[j + 5] = temp;
                }
            }
        }
        System.out.println("第一轮：");
        System.out.println(Arrays.toString(arr));


        //第二轮
        //因为第二轮排序是将10个数据分成了5/2 = 2组
        for (int i = 2;i < arr.length;i++) {
            //遍历各组中所有的元素（共五组，每一组有2个元素）
            for (int j = i - 2; j >= 0 ; j -= 2) {
                //如果当前元素大于加上步长后的那个元素，说明需要交换
                if (arr[j] > arr[j + 2]) {
                    temp = arr[j];
                    arr[j] = arr[j + 2];
                    arr[j + 2] = temp;
                }
            }
        }
        System.out.println("第二轮：");
        System.out.println(Arrays.toString(arr));

        //第三轮
        //因为第三轮排序是将10个数据分成了2/2 = 1组
        for (int i = 1;i < arr.length;i++) {
            //遍历各组中所有的元素（共五组，每一组有2个元素）
            for (int j = i - 1; j >= 0 ; j -= 1) {
                //如果当前元素大于加上步长后的那个元素，说明需要交换
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println("第三轮：");
        System.out.println(Arrays.toString(arr));*/


        //缩小增量排序，尽量把小的调到前面，大的调到后面，避免移动很多次的情况
        //希尔排序-对有序序列在插入时采用交换法
        int temp = 0;
        int count = 0;
        for (int gap = arr.length / 2;gap > 0;gap /= 2) {
            for (int i = gap;i < arr.length;i++) {
                //遍历各组中所有的元素（共gap组，每一组有个元素）步长gap
                for (int j = i - gap; j >= 0 ; j -= gap) {
                    //如果当前元素大于加上步长后的那个元素，说明需要交换
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            System.out.println("第"+ (++count) +"轮：");
            System.out.println(Arrays.toString(arr));
        }
    }

    //希尔排序-对有序序列在插入时采用移动法
    public static void shellSort2(int[] arr) {

        /*//增量gap，并逐步缩小增量
        for (int gap = arr.length; gap > 0 ; gap /= 2) {
            //从第gap个元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int insertIndex = i;
                int insertVal = arr[insertIndex];
                if (arr[insertIndex] <arr[insertIndex - gap]) {
                    while (insertIndex - gap >= 0 && insertVal < arr[insertIndex - gap]) {
                        //移动
                        arr[insertIndex] = arr[insertIndex - gap];
                        insertIndex -= gap;
                    }
                    //退出while循环后，就给temp找到了插入的位置
                    arr[insertIndex] = insertVal;
                }
            }
            System.out.println("第"+ gap +"轮插入后：");
            System.out.println(Arrays.toString(arr));
        }*/


        //增量gap，并逐步缩小增量
        for (int gap = arr.length; gap > 0 ; gap /= 2) {
            //从第gap个元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int insertVal = arr[i];
                int insertIndex = i - gap;
                给insertVal找到插入的位置
                if (insertVal <arr[insertIndex]) {
                    while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                        //移动
                        arr[insertIndex + gap] = arr[insertIndex];
                        insertIndex -= gap;
                    }
                    //退出while循环后，就给temp找到了插入的位置
                    arr[insertIndex + gap] = insertVal;
                }
            }
            System.out.println("第"+ gap +"轮插入后：");
            System.out.println(Arrays.toString(arr));
        }

            /*//第一趟
            for (int i = 5; i < arr.length; i++) {
                int insertVal = arr[i];
                int insertIndex = i - 5;
                while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                    //移动
                    arr[insertIndex + 5] = arr[insertIndex];
                    insertIndex -= 5;
                }
                //退出while循环后，就给temp找到了插入的位置
                arr[insertIndex + 5] = insertVal;
            }
            System.out.println("第"+ 1 +"轮插入后：");
            System.out.println(Arrays.toString(arr));

            //第二趟
            for (int i = 2; i < arr.length; i++) {
                int insertVal = arr[i];
                int insertIndex = i - 2;
                while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                    //移动
                    arr[insertIndex + 2] = arr[insertIndex];
                    insertIndex -= 2;
                }
                //退出while循环后，就给temp找到了插入的位置
                arr[insertIndex + 2] = insertVal;
            }
            System.out.println("第"+ 2 +"轮插入后：");
            System.out.println(Arrays.toString(arr));

        //第三趟
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int insertIndex = i - 1;
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                //移动
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex -= 1;
            }
            //退出while循环后，就给temp找到了插入的位置
            arr[insertIndex + 1] = insertVal;
        }
        System.out.println("第"+ 3 +"轮插入后：");
        System.out.println(Arrays.toString(arr));*/


        }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185

9.6.1希尔排序原理 391

现在，我要讲解的算法叫希尔排序 (Shell So时，希尔排序是 D.L.Shell 于 1959 年提出来的一种排序算法，在这之前排序算法的时间复杂度基本都是 O(n2)的，希尔排序算法是突破这个时阎复杂度的第一批算法之一。
我们前一节讲的直接插入排序，应该说，它的效率在某些时候是很高的，比如，我们的记录本身就是基本有序的，我仍只需要少量的插入操作，就可以完成整个记录集的排序工作，此时直接插入很高效。还有就是记录数比较少时，直接插入的优势也比较明显。可问题在于，两个条件本身就过于苛刻，现实中记录少或者基本有序都属于特殊情况。
不过别急，有条件当然是好，条件不存在，我们创造条件也是可以去做的。于是科学家希尔研究出了一种排序方法，对直接插入排序改进后可以增加效率。
如何让待排序的记录个数较少呢?很容易想到的就是将原本有大量记录数的记录进行分组。分割成若干个子序列，此时每个子序列待排序的记录个数就比较少了，然后在这些子序列内分别进行直接插入排序，当整个序列都基本有序时，注意只是基本有序时，再对全体记录进行一次直接插入排序。
此时一定有同学开始疑惑了。这不对呀，比如我们现在有序列是{9，1，5，8，3几4瓜 2}，现在将包分成三组，币，1，S}， {8,3,7}, {4，6，2}，哪怕将它们各自排序排好了，变成 {1,S,9} , {3几句， {2人的，再合并它们成{1，5，9，3几8，2凡的，比时，这个序列还是杂乱无序，谈不上基本有序，要排序还是重来一埠直接插入有序，这样做有用吗?需要强调一下，所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间，像{2，1，3，6人7丘8，9}这样可以称为基本有序了。但像{1，S，9，3几8，2人6} 这样的 9 在第三位， 2 在倒数第三位就谈不上基本有序。
问题其实也就在这里，我们分割待排序记录的目的是减少待排序记录的个数，并使整个序列向基本有序发展。而如上面这样分完组后就各自排序的方法达不到我们的要求。因此，我们需要采取跳跃分割的策略:将相距某个‘增量’的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。

9.6.2希尔排序算法 391

9.6.3希尔排序复杂度分析 395

9.7堆排序 396

什么叫堆结构呢？回忆一下我们小时候，特别是男同学，基本都玩过叠罗汉的恶作剧。通常都是先把某个要整的人按倒在地，然后大家就一拥而上扑了上去……后果？后果当然就是一笑了之。
堆排序种的堆指的是数据结构中的堆，而不是内存模型中的堆。

堆：可以看成一棵完全二叉树，每个结点的值都大于等于（小于等于）其左右孩子结点的值，称为大顶堆（小顶堆）。

在这里插入图片描述
大顶堆(左)与小顶堆(右)

堆排序的基本思想：将带排序的序列构造成大顶堆，最大值为根结点。将根结点与最后一个元素交换，对除最大值外的剩下n-1个元素重新构造成大顶堆，可以获得次大的元素。反复执行，就可以得到一个有序序列了。

构造大顶堆的方法：

1.首先复习完全二叉树的性质，层序遍历，当第一个元素索引从0开始时，索引为i的左孩子的索引是 (2i+1)，右孩子的索引是 (2i+2)。

2.设计一个函数heapAdjust()，对于一个序列（除了第一个根结点外，其余结点均满足最大堆的定义），通过这个函数可以将序列调整为正确的大顶堆。

3.正式构造：将带排序的序列看成一棵完全二叉树的层序遍历，我们从下往上，从右往左，依次将每个非叶子结点当作根结点，使用heapAdjust()调整成大顶堆。

具体细节的实现参阅代码，比较清楚，不再赘述。

回到顶部
完整Java代码

9.7.1堆排序算法 398

/**
 *
 * @Description 堆排序
 *
 * @author yongh
 *
 */
public class HeapSort {
    public void heapSort(int[] arr) {
        if(arr==null || arr.length<=0)
            return;
        int len=arr.length;
        for(int i=len/2-1;i>=0;i--) { //从最后一个父结点开始构建最大堆
            heapAdjust(arr,i,len-1);
        }
        for(int i=len-1;i>=0;i--) {
            int temp=arr[0];
            arr[0]=arr[i];
            arr[i]=temp;
            heapAdjust(arr, 0, i-1);
        }
    }
     
     
    /*
     * 功能：调整堆为最大堆
     * [i……j]中，除了i之外，部分子树都满足最大堆定义
     */
    private void heapAdjust(int[] arr, int start, int end) {
        int temp=arr[start];
        int child=2*start+1;
        while(child<=end) {
            if(child+1<=end && arr[child+1]>arr[child])  //记得child+1<=end的判断
                child++;  //较大的孩子
            if(arr[child]<=temp)
                break;
            arr[start]=arr[child];
            start=child;
            child=child*2+1;
        }
        arr[start]=temp;   
        }
     
    // =========测试代码=======
    public void test1() {
        int[] a = null;
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test2() {
        int[] a = {};
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test3() {
        int[] a = { 1 };
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test4() {
        int[] a = { 3, 3, 3, 3, 3 };
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test5() {
        int[] a = { -3, 6, 3, 1, 3, 7, 5, 6, 2 };
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public static void main(String[] args) {
        HeapSort demo = new HeapSort();
        demo.test1();
        demo.test2();
        demo.test3();
        demo.test4();
        demo.test5();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

9.7.2堆排序复杂度分析 405

构建堆的时间复杂度为O(n)；每次调整堆的时间为O(logn)，共要调整n-1次，所以重建堆的时间复杂度为O(nlogn)。

因此总体来说，堆排序的复杂度为O(nlogn)。不过由于记录的比较和交换是跳跃式进行的，因此堆排序是不稳定的排序方法。

基数排序

基数排序(桶排序)介绍:

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用

基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法

基数排序(Radix Sort)是桶排序的扩展

基数排序是1887年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序基本思想
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
这样说明，比较难理解，下面我们看一个图文解释，理解基数排序的步骤

基数排序图文说明
将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序。
第1轮排序 [按照个位排序]:
说明：事先准备10个数组(10个桶)， 0-9 分别对应位数的 0-9

在这里插入图片描述

基数排序代码实现

要求：将数组 {53, 3, 542, 748, 14, 214 } 使用基数排序, 进行升序排序
思路分析：前面的图文已经讲明确
代码实现：看老师演示

基数排序的说明:
基数排序是对传统桶排序的扩展，速度很快.
基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。
基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的]
有负数的数组，我们不用基数排序来进行排序, 如果要支持负数，参考: https://code.i-harness.com/zh-CN/q/e98fa9

package com.zcr.sort;

import java.util.Arrays;

/**
 * @author zcr
 * @date 2019/7/7-17:24
 */
public class RadixSort {

    public static void main(String[] args) {
        int arr[] = {53,3,542,748,14,214};
        radixSort(arr);
    }

    //基数排序
    public static void radixSort(int[] arr) {
        //第一轮（针对每个元素的个位进行排序处理）

        //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
        //为了防止在放数的时候数据溢出，每个一维数组的大小为arrr.length
        int[][] bucket = new int[10][arr.length];//经典的用空间换时间的算法

        //为了记录每个桶中实际存放了多少个数据，我们定义一个一维数据来记录各个桶每次放入的数据个数
        //可以这样理解，bucketElementCount[0]，记录的就是bucket[0]桶的放入数据的个数
        int[] bucketElementCounts = new int[10];
        int index = 0;

        //第一轮
        /*for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个位
            int digitOfElement = arr[j] % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            //digitOfElement 哪个桶 ？
            //bucketElementCounts[digitOfElement] 桶中的哪个下标？
            bucketElementCounts[digitOfElement]++;
        }
        //按照这个桶的顺序（一维数组的下标依次取出数据，放入到原来的数组）
        index = 0;
        //遍历每一桶，并将桶中的数据放入到原数组
        for (int k = 0; k < bucketElementCounts.length; k++) {//或者是bucket.length
            //如果桶中有数据，我们才放入到原数组中
            if (bucketElementCounts[k] != 0){
                //循环该桶即第k个桶（即第k个一维数组），放入 
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    //取出元素放入到arr中
                    arr[index++] = bucket[k][l];
                }
            }
            //第一轮处理后要将每个bucketElementCounts[k]置0
            bucketElementCounts[k] = 0;
        }
        System.out.println("第一轮对个数的排序处理arr = "+ Arrays.toString(arr));

        //第二轮
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个位
            int digitOfElement = arr[j] /10 % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            //digitOfElement 哪个桶 ？
            //bucketElementCounts[digitOfElement] 桶中的哪个下标？
            bucketElementCounts[digitOfElement]++;
        }
        //按照这个桶的顺序（一维数组的下标依次取出数据，放入到原来的数组）
        index = 0;
        //遍历每一桶，并将桶中的数据放入到原数组
        for (int k = 0; k < bucketElementCounts.length; k++) {//或者是bucket.length
            //如果桶中有数据，我们才放入到原数组中
            if (bucketElementCounts[k] != 0){
                //循环该桶即第k个桶（即第k个一维数组），放入
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    //取出元素放入到arr中
                    arr[index++] = bucket[k][l];
                }
            }
            //第二轮处理后要将每个bucketElementCounts[k]置0
            bucketElementCounts[k] = 0;
        }
        System.out.println("第二轮对个数的排序处理arr = "+ Arrays.toString(arr));

        //第三轮
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的个位
            int digitOfElement = arr[j] / 100;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            //digitOfElement 哪个桶 ？
            //bucketElementCounts[digitOfElement] 桶中的哪个下标？
            bucketElementCounts[digitOfElement]++;
        }
        //按照这个桶的顺序（一维数组的下标依次取出数据，放入到原来的数组）
        index = 0;
        //遍历每一桶，并将桶中的数据放入到原数组
        for (int k = 0; k < bucketElementCounts.length; k++) {//或者是bucket.length
            //如果桶中有数据，我们才放入到原数组中
            if (bucketElementCounts[k] != 0){
                //循环该桶即第k个桶（即第k个一维数组），放入
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    //取出元素放入到arr中
                    arr[index++] = bucket[k][l];
                }
            }
            //第三轮处理后要将每个bucketElementCounts[k]置0
            bucketElementCounts[k] = 0;
        }
        System.out.println("第三轮对个数的排序处理arr = "+ Arrays.toString(arr));

*/
        //一共进行多少轮？有多少位进行多少轮
        //先得到数组中最大的数的位数
        int max = arr[0];//假设第一个数就是最大数
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }
        //得到最大数是几位数
        int maxLength = (max + "").length();

        //这里我们使用循环
        for (int i = 0 , n = 1; i < maxLength; i++,n *= 10) {
            //针对每一轮的对应的位数进行排序处理，个位、十位、百位、千位、...
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的对应位的数值
                int digitOfElement = arr[j] / n % 10;
                //放入到对应的桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                //digitOfElement 哪个桶 ？
                //bucketElementCounts[digitOfElement] 桶中的哪个下标？
                bucketElementCounts[digitOfElement]++;
            }
            //按照这个桶的顺序（一维数组的下标依次取出数据，放入到原来的数组）
            index = 0;
            //遍历每一桶，并将桶中的数据放入到原数组
            for (int k = 0; k < bucketElementCounts.length; k++) {//或者是bucket.length
                //如果桶中有数据，我们才放入到原数组中
                if (bucketElementCounts[k] != 0){
                    //循环该桶即第k个桶（即第k个一维数组），放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出元素放入到arr中
                        arr[index++] = bucket[k][l];
                    }
                }
                //第i+1轮处理后要将每个bucketElementCounts[k]置0
                bucketElementCounts[k] = 0;
            }
            System.out.println("第"+(i + 1)+"轮数的排序处理arr = "+ Arrays.toString(arr));

        }


    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

9.8归并排序 406

即使你是你们班级第一、甚至年级第一名，如果你没有上分数线，则说明你的成绩排不到全省前1万名，你也就基本失去了当年上本科的机会了。

归并排序介绍:

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
在这里插入图片描述

说明:
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程。

归并排序思想示意图2-合并相邻有序子序列:
再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤
在这里插入图片描述

归并排序的应用实例:
给你一个数组, val arr = Array(9,8,7,6,5,4,3,2,1), 请使用归并排序完成排序。

package com.zcr.sort;

import java.util.Arrays;

/**
 * @author zcr
 * @date 2019/7/7-16:41
 */
public class MergetSort {

    public static void main(String[] args) {
        int[] arr = {8,4,5,7,1,3,6,2};
        int[] temp = new int[arr.length];
        mergeSort(arr,0,arr.length - 1,temp);
        System.out.println("归并排序后="+ Arrays.toString(arr));
    }

    //分 + 合方法
    public static void mergeSort(int[] arr,int left,int right,int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            //向左递归分解
            mergeSort(arr,left,mid,temp);
            //向右递归分解
            mergeSort(arr,mid + 1,right,temp);
            //每分解一次合并
            merge(arr,left,mid,right,temp);
        }
    }


    //合并的方法
    /**
     *
     * @param arr 排序的原始数组
     * @param left 左边有序序列的初始索引
     * @param middle 中间索引
     * @param right 右边索引
     * @param temp 做中转的数组
     */
    public static void merge(int[] arr,int left,int middle,int right,int[] temp) {
        System.out.println("xxxx");
        int i = left;//初始化i，左边有序序列的初始索引
        int j = middle + 1;//初始化j，右边有序序列的初始索引
        int t = 0;//指向temp数组的当前索引

        //先把左右两边的数据（已经有序）按照规则填充到temp数组中，直到左右两边有一边全部处理完毕
        while (i <= middle && j <= right) {
            if (arr[i] <= arr[j]) {//如果左边的有序序列的当前元素，小于等于，右边有序序列的当前元素
                temp[t] = arr[i];//将左边的当前元素拷贝到temp数组中
                t++;
                i++;
            } else {
                temp[t] = arr[j];
                t++;
                j++;
            }
        }
        //把有剩余数据的一方依次全部填充到temp数组中
        while (i <= middle){//说明左边的有序序列还有剩余的元素
            temp[t] = arr[i];
            t++;
            i++;
        }
        while (j <= right){//说明右边的有序序列还有剩余的元素
            temp[t] = arr[j];
            t++;
            j++;
        }
        //将temp数组重新全部拷贝到arr数组中
        //注意，并不是每次都拷贝所有
        t = 0;
        int tempLeft = left;
        System.out.println("tempLeft=" + tempLeft + "right=" + right);
        while (tempLeft <= right) {//第一次合并时，tempLeft=0,right=1//第一次合并时，tempLeft=2,right=3//第一次合并时，tempLeft=0,right=3
            arr[tempLeft] = temp[t];//最后一次合并时，tempLeft=0,right=7
            tempLeft++;
            t++;
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

有几个数据，就会merge数据个数-1次

9.8.1归并排序算法 407

public class MergeSort {
    public void mergeSort(int[] arr) {
        if(arr==null || arr.length<=0)
            return;
        mSort(arr,0,arr.length-1);
    }
  
    private  void mSort(int[] arr, int start, int end) {
        if(start==end)
            return;
        int mid=(start+end)/2;
        mSort(arr,start,mid);
        mSort(arr, mid+1, end);
        merge(arr,start,mid,end);
    }
  
    private void merge(int[] arr, int start, int mid, int end) {
        int[] temp=new int[end-start+1];    //存放排序号数据的临时区域
        int k=0;        //临时区域的指针
        int i=start;    //第一个有序区的指针
        int j=mid+1;    //第二个有序区的指针
          
        while(i<=mid && j<=end) {
            if(arr[i]<=arr[j])
                temp[k++]=arr[i++];
            else
                temp[k++]=arr[j++];
        }
        while(i<=mid)
            temp[k++]=arr[i++];
        while(j<=end)
            temp[k++]=arr[j++];
          
        for(k=0;k<=end-start;k++)
            arr[k+start]=temp[k];
    }
      
    //==========测试代码=================
    public void test1() {
        int[] a = null;
        mergeSort(a);
        System.out.println(Arrays.toString(a));
    }
  
    public void test2() {
        int[] a = {};
        mergeSort(a);
        System.out.println(Arrays.toString(a));
    }
  
    public void test3() {
        int[] a = { 1 };
        mergeSort(a);
        System.out.println(Arrays.toString(a));
    }
  
    public void test4() {
        int[] a = { 3, 3, 3, 3, 3 };
        mergeSort(a);
        System.out.println(Arrays.toString(a));
    }
  
    public void test5() {
        int[] a = { -3, 6, 3, 1, 3, 7, 5, 6, 2 };
        mergeSort(a);
        System.out.println(Arrays.toString(a));
    }
    public static void main(String[] args) {
        MergeSort demo =new MergeSort();
        demo.test1();
        demo.test2();
        demo.test3();
        demo.test4();
        demo.test5();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

9.8.2归并排序复杂度分析 413

时间复杂度：O(nlogn)。假设序列有n个数，遍历一次时间复杂度为O(n)，遍历次数为二叉树的深度log(2)n，所以时间复杂度为O(nlogn)。

归并排序是一种比较占用内存，但效率高且稳定的算法。

9.8.3非递归实现归并排序 413

正文

归并排序可以采用递归方法（见：归并排序），但递归方法会消耗深度位O(longn)的栈空间，使用归并排序时，应该尽量使用非递归方法。本文实现了java版的非递归归并排序。

更多：数据结构与算法合集

回到顶部
思路分析
　　递归排序的核心是merge(int[] arr, int start, int mid, int end)函数，讲[start_{mid-1]和[mid}end]部分的数据合并，递归代码是使用递归得到mid，一步步分解数组。

非递归时，我们直接定义要合并的小数组长度从1开始，在较小的长度数组都合并完成后，令长度*2，继续进行合并，直到合并完成。

public class MergeSort2 {
    public void mergeSort(int[] arr) {
        if(arr==null || arr.length<=0)
            return;
        int width = 1;
        while(width<arr.length) {
            mergePass(arr,width);
            width*=2;
        }
    }
     
    private void mergePass(int[] arr,int width) {
        int start=0;
        while(start+2*width-1<arr.length) {
            int mid=start+width-1;
            int end=start+2*width-1;
            merge(arr,start,mid,end);
            start=start+2*width;
        }
        //剩余无法构成完整的两组也要进行处理
        if(start+width-1<arr.length)
            merge(arr, start, start+width-1, arr.length-1);
    }
     
    private void merge(int[] arr, int start, int mid, int end) {
        int i=start;
        int j=mid+1;
        int[] temp = new int[end-start+1];
        int index=0;
        while(i<=mid && j<=end) {
            if(arr[i]<=arr[j])
                temp[index++]=arr[i++];
            else
                temp[index++]=arr[j++];
        }
        while(i<=mid)
            temp[index++]=arr[i++];
        while(j<=end)
            temp[index++]=arr[j++];
         
        for(int k=start;k<=end;k++)
            arr[k]=temp[k-start];
    }
     
    //==========测试代码=================
    public void test1() {
        int[] a = null;
        mergeSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test2() {
        int[] a = {};
        mergeSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test3() {
        int[] a = { 1 };
        mergeSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test4() {
        int[] a = { 3, 3, 3, 3, 3 };
        mergeSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test5() {
        int[] a = { -3, 6, 3, 1, 3, 7, 5, 6, 2 };
        mergeSort(a);
        System.out.println(Arrays.toString(a));
    }
     
    public static void main(String[] args) {
        MergeSort2 demo =new MergeSort2();
        demo.test1();
        demo.test2();
        demo.test3();
        demo.test4();
        demo.test5();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

9.9快速排序 417

终于我们的高手要登场了，将来你工作后，你的老板让你写个排序算法，而你会的算法中竟然没有快速排序，我想你还是不要声张，偷偷去把快速排序算法找来敲进电脑，这样至少你不至于被大伙儿取笑。

快速排序法介绍:
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
在这里插入图片描述
快速排序法应用实例:
要求: 对 [-9,78,0,23,-567,70] 进行从小到大的排序，要求使用快速排序法。【测试8w和800w】
说明[验证分析]:
如果取消左右递归，结果是 -9 -567 0 23 78 70
如果取消右递归,结果是 -567 -9 0 23 78 70
如果取消左递归,结果是 -9 -567 0 23 70 78
在这里插入图片描述

package com.zcr.sort;

import java.util.Arrays;

/**
 * @author zcr
 * @date 2019/7/7-12:21
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {-9,78,0,23,-567,70,-1,900,4561};
        quickSort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }

    //快速排序
    public static void quickSort(int[] arr,int left,int right) {
        int  l = left;
        int r = right;
        int temp = 0;//临时变量
        int pivot = arr[(left + right) / 2];//中轴
        while (l < r) {//循环的目的是让比pivot小的值放到左边，比它大的值放到右边
            while (arr[l] < pivot) {//循环的目的是在左边一直找，找到大于等于pivot的值才退出
                l++;
            }
            while (arr[r] > pivot) {//循环的目的是在右边一直找，找到小于等于pivot的值才退出
                r--;
            }
            if (l >= r) {//说明pivot的左右两边的值已经按照左边全部是小于它，右边全部是大于它的顺序排好了
                break;
            }
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            //如果交换完后，发现这个值arr[l] == pivot，r--
            if (arr[l] == pivot){
                r--;
            }
            //如果交换完后，发现这个值arr[r] == pivot，l++
            if (arr[r] == pivot){
                l++;
            }
        }

        //如果l== r，必须让l++,r--，否则会出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if (left < r) {
            quickSort(arr,left,r);
        }

        //向右递归
        if (right > l) {
            quickSort(arr,l,right);
        }


    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

9.9.1快速排序算法 417

import java.util.Arrays;
 
/**
 *
 * @Description 快速排序
 *
 * @author yongh
 * @date 2018年9月14日 下午2:39:00
 */
public class QuickSort {
    public void quickSort(int[] a) {
        if (a == null)
            return;
        qSort(a, 0, a.length - 1);
    }
     
    /**
     * 递归调用
     */
    public void qSort(int[] a, int low, int high) {
        int pivot;
        if (low >= high)
            return;
        pivot = partition(a, low, high);  //将数列一分为二
        qSort(a, low, pivot - 1);   //对低子表排序
        qSort(a, pivot + 1, high);  //对高子表排序
    }
 
    /**
     * 对数组a中下标从low到high的元素，选取基准元素pivotKey，
     * 根据与基准比较的大小，将各个元素排到基准元素的两端。
     * 返回值为最后基准元素的位置
     */
    public int partition(int[] a, int low, int high) {
        int pivotKey = a[low];  //用第一个元素作为基准元素
        while (low < high) { //两侧交替向中间扫描
            while (low < high && a[high] >= pivotKey)
                high--;
            swap(a, low, high);  //比基准小的元素放到低端
            while (low < high && a[low] <= pivotKey)
                low++;
            swap(a, low, high);  //比基准大的元素放到高端
        }
        return low;     //返回基准元素所在位置
    }
 
    public void swap(int[] a, int i, int j) {
        int temp;
        temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }
 
    // =========测试代码=======
    public void test1() {
        int[] a = null;
        quickSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test2() {
        int[] a = {};
        quickSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test3() {
        int[] a = { 1 };
        quickSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test4() {
        int[] a = { 3, 3, 3, 3, 3 };
        quickSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public void test5() {
        int[] a = { -3, 6, 3, 1, 3, 7, 5, 6, 2 };
        quickSort(a);
        System.out.println(Arrays.toString(a));
    }
 
    public static void main(String[] args) {
        QuickSort demo = new QuickSort();
        demo.test1();
        demo.test2();
        demo.test3();
        demo.test4();
        demo.test5();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

9.9.2快速排序复杂度分析 421

快速排序时间性能取决于递归深度，而空间复杂度是由递归造成的栈空间的使用。递归的深度可以用递归树来描述，如{50，10，90，30，70，40，80，60，20}的递归树如下：
在这里插入图片描述
最优情况：

最优情况下，每次选取的基准元素都是元素中间值，partition()方法划分均匀，此时根据二叉树的性质4可以知道，排序n个元素，其递归树的深度为[log2n]+1，所以仅需要递归log2n次。

将排序n个元素的时间记为T(n)，则有以下推断：
在这里插入图片描述

所以最优情况下的时间复杂度为：O(nlogn)；同样根据递归树的深度，最优空间复杂度为O(logn)。

最坏情况：

递归树为一棵斜树，需要n-1次调用，所以最坏空间复杂度为O(logn)。在第i次调用中需要n-1次的关键字比较，所以比较次数为：Σ(n-i)=(n-1)+……+2+1=n(n-1)/2，所以最坏时间复杂度为O(n^2）。

平均情况：
在这里插入图片描述

平均时间复杂度：O(nlogn)，平均空间复杂度O(logn)。

9.9.3快速排序优化 422

快速排序优化
　1.优化选取枢纽

基准应尽量处于序列中间位置，可以采取“三数取中”的方法，在partition()方法开头加以下代码，使得a[low]为三数的中间值：

// 三数取中,将中间元素放在第一个位置
if (a[low] > a[high])
    swap(a, low, high);
if (a[(low + high) / 2] > a[high])
    swap(a, (low + high) / 2, high);
if (a[low] < a[(low + high) / 2])
    swap(a, (low + high) / 2, low);
　　
1
2
3
4
5
6
7
8

2.优化不必要的交换

两侧向中间扫描时，可以将交换数据变为替换：

while (low < high) { // 两侧交替向中间扫描
    while (low < high && a[high] >= pivotKey)
        high--;
    a[low] = a[high];
    // swap(a, low, high); //比基准小的元素放到低端
    while (low < high && a[low] <= pivotKey)
        low++;
    a[high] = a[low];
    // swap(a, low, high); //比基准大的元素放到高端
}
a[low]=pivotKey;  //在中间位置放回基准值
1
2
3
4
5
6
7
8
9
10
11

3.优化小数组时的排序方案

当数组非常小时，采用直接插入排序（简单排序中性能最好的方法）

4.优化递归操作

qSort()方法中，有两次递归操作，递归对性能有较大影响。因此，使用while循环，在第一次递归后，变量low就没有用处了，可将pivot+1赋值给low，下次循环中，partition(a, low, high)的效果等同于qSort(a, pivot + 1, high)，从而可以减小堆栈的深度，提高性能。

// pivot = partition(a, low, high); // 将数列一分为二
// qSort(a, low, pivot - 1); // 对低子表排序
// qSort(a, pivot + 1, high); // 对高子表排序
 
//优化递归操作
while (low < high) {
    pivot = partition(a, low, high); // 将数列一分为二
    qSort(a, low, pivot - 1); // 对低子表排序
    low = pivot + 1;
}
1
2
3
4
5
6
7
8
9
10

9.10总结回顾 428

目前还没有十全十美的排序算法，有优点就会有缺点，即使是快速排序法，也只是在整体性能上优越，它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。
1.BubbleSort
2.SelectSort
3.InsertSort

4.ShellSort
5.QuickSort
6.MergeSort

7.RadixSort

在这里插入图片描述

9.11结尾语 430

如果你有梦想的话，就要去捍卫它。当别人做不到的时候，他们就想要告诉你，你也不能。如果你想要些什么，就得去努力争取。就这样！
附录参考文献 435

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/418825