public class DataStruct {
    public static void main(String[] args){
        DataStruct dataStruct = new DataStruct();
        int[]  arr = {3,1,8,5,9,6,2,4};
      //  dataStruct.insertion_sort(arr,arr.length);
      //  dataStruct.shellSort(arr,arr.length);
      //  dataStruct.bubbleSort(arr);
       // dataStruct.mergeSort(arr,0,arr.length-1);
          dataStruct.heapSort(arr,arr.length);
      //  dataStruct.quikSort(arr,0,arr.length-1);
      //  dataStruct.heapSort2(arr,arr.length - 1);
          dataStruct.print(arr);

    }


    public void print(int[] arr){
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println(" ");
    }

    //插入排序
    /*
    * 先选择从坐标1开始  每选择一个i值  就把0到i值区间排序  
*我们找到对应的位置  把比target大的值向前移动一个位置  在进行插入
    * */
    public void insertion_sort(int arr[], int length){
        int i,j;
        for (i = 1; i < length; i++){
            int tmp = arr[i];
            for (j = i; j > 0 && tmp < arr[j-1]; j--){
                arr[j] = arr[j-1];
            }
            arr[j] = tmp;
        }
    }

    //希尔排序
    /**
     *这个是插入排序的修改版，根据步长由长到短分组，进行排序，直到步长为1为止，属于插入排序的一种。
     * 先由步长分组  每一组使用我们的插入排序
     */

    public void shellSort(int arr[], int length){
        for (int gap = length / 2; gap > 0; gap /= 2){

            for (int i = gap; i < length; i++){
                int tmp = arr[i];
                int j;
                for (j = i; j >= gap &&  arr[j - gap] > tmp; j -= gap){
                    arr[j] = arr[j-gap];
                }
                arr[j] = tmp;
            }
        }

    }

    //冒泡排序
    //相对优雅的冒泡  有一个值来提前判断要不要停止排序
    public void bubbleSort(int[] arr) {
        boolean swapp = true;

        for (int j = 1; j < arr.length; j++) {
            swapp = false;
            for (int i = 0; i < arr.length - j; i++) {
                if (arr[i] > arr[i + 1]) {
                    arr[i] += arr[i + 1];
                    arr[i + 1] = arr[i] - arr[i + 1];
                    arr[i] -= arr[i + 1];
                    swapp = true;
                }
            }
            if (swapp == false) break;
        }

    }

    //归并排序
    /*
    *用二分的手法  直接先分后后和
    * */
    public void mergeSort(int arr[], int l, int r){  //归并也是双闭合
        if (r > l){
            int mid = l +  (r - l) / 2;
            mergeSort(arr,l,mid);
            mergeSort(arr,mid+1,r);
            merge(arr,l,mid,r);

        }
    }

    public void merge(int[] arr,int l, int mid,int r){ // l ~ mid  mid+1 ~ r
        int i = 0;
        int j = 0;

        int n1 = mid - l + 1; //先拿到n1 的数量
        int n2 =  r - mid;      //先分别取两数组长度

        int[] left = new int[n1];
        int[] right = new int[n2];

        for (int x = 0; x < left.length; x++)
            left[x] = arr[x + l];
        for (int x = 0; x < right.length; x++)
            right[x] = arr[x + mid + 1];

        int t = l;
        while (i < left.length && j < right.length){
            if (left[i] < right[j])
                arr[t++] = left[i++];
            else
                arr[t++] = right[j++];

        }
        while (i < left.length)
            arr[t++] = left[i++];
        while (j < right.length)
            arr[t++] = right[j++];

    }

    public void swap(int[] nums, int index1, int index2){
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;

    }

    //堆排序   最大堆的最大元素在根节点   堆中每个父节点比子节点大
    /**
     *  这里我们的堆排序的起始点从  0 开始  
所以他的左子节点的序号是 2 * i +1 右结点的序号是  2  * i + 2
     *  如果从起始点从1 开始的话  我们的左子节点为  2 * i   右节点为 2 * 1;
     *
     */

    public void heapify(int arr[], int len, int index){  
//index 代表 parent  建立堆  不符合递归调用
        int value = arr[index];

        for (int j = 2 * index + 1; j < len; j = j * 2 + 1){
            if (j < len -1 && arr[j] < arr[j + 1]) j++;  //比较左右结点大小  找出最大的
            if (value > arr[j]) break;
            arr[index] = arr[j];
            index = j; //记录下来 value 应该放置的位置
        }
        arr[index] = value;

    }


    public  void heapSort(int arr[], int n) {
        // 建立堆
        for (int i = arr.length / 2 - 1 ; i >= 0; i--)  //调整为堆
            heapify(arr, arr.length, i);


        // 一个个从堆顶取出元素
        for (int i = arr.length-1; i>= 0; i--)
        {
            System.out.print(arr[0] + "  ");
            swap(arr,0,i);      //取
            heapify(arr, i, 0);     //取完之后需要重建堆
        }
        System.out.println("\n");

    }

    //起始结点从 1 开始  len为数组长度
    public void heapify2(int arr[], int len, int index) {
        int largestIndex = index;
        int left = 2 * index;
        int right = 2 * index + 1;

        if (len >= left && arr[left] > arr[largestIndex]) {
            largestIndex = left;
        }

        if (len >= right && arr[right] > arr[largestIndex])
            largestIndex = right;

        if (index != largestIndex) {
            swap(arr, largestIndex, index);

            heapify2(arr, len, largestIndex);
        }
    }


    //注意边界条件  从0 开始是 n /2   1 开始是n / 2 - 1  这是从1 开始
    public  void heapSort2(int[] arr , int len){
        for (int i = len / 2 ; i >= 1; i--)
            heapify2(arr,len,i);


             //取堆顶
        for (int i = len; i >= 1; i--){
            System.out.print(arr[1] +"  ");
            swap(arr,1,i);
            heapify2(arr,i-1,1);
        }
        System.out.println("\n");


    }


        public void quikSort(int[] nums,int  begin, int end){  //左闭右闭   快排必须双闭合
        if (end > begin){
            int index = qSort(nums,begin,end);

            quikSort(nums,begin,index-1);
            quikSort(nums,index+1,end);
        }

    }

    public int qSort(int[] nums,int begin, int end){
        int value = nums[begin];
        while (begin < end) {
            while (begin < end && nums[end] >= value)
                end--;
            if (begin < end)
                nums[begin++] = nums[end];
            while (begin < end && nums[begin] <= value)
                begin++;
            if (begin < end)
                nums[end--] = nums[begin];
        }
        nums[begin] = value;
        return begin;
    }

}

二叉搜索树, 平衡二叉树(AVL) 红黑树 B树(平衡多路搜索树) B+树(在B树上改造)

二叉搜索树

二叉排序树（Binary Sort Tree），又称[二叉查找树（Binary Search Tree），亦称[二叉搜索树]
二叉搜索树，主要特点是左节点比根节点小，右节点比根节点大，并且左右子树都是二叉搜索树。缺点是在极端情况下，比如插入都是有序的，就会出现退化的情况有序序列树退化成链表。
左小右大

image.png

二叉平衡树 AVL

在二叉搜索树的基础加上一规则
左子树的深度和右子树的深度只差 不大于1

红黑树

红黑树红黑树让树尽可能平衡，就是为了降低树的高度。红黑树会比AVL树多一层,但是它具有稳定的优点.
特点:

• 每个节点要么是红色，要么是黑色。
• 根节点必须是黑色
• 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
• 对于每个节点，从该点至null（树尾端）的任何路径，都含有相同个数的黑色节点。

image.png

B树

树是一种平衡多路搜索树，他的每个节点可以拥大于等于2个子节点，M路的B树最多能拥有M个子节点，一个节点中有 m 个子节点则存在 m-1 个记录，记录按照递增次序进行排列，叶节点都在同一层上。B树之所以多路(也就是每个节点上可存多个记录）是为了降低高度，路数越多，树高度越低，查询性能也高。但也不能是无限的，否则就退化成有序数组了。

image.png

B+树

B+树是在B树基础上进行改造，他的数据都在叶子结点，同时叶子结点之间还加了指针形成一个链表。

image.png

Q0.数据库索引有哪些，优缺点？

hash索引和B+树索引
hash索引等值查询效率高，但是不能排序，因此不能进行范围查询
B+树索引数据有序，能够进行范围查询

Q1.为什么不用二叉查找树作为数据库索引？

二叉查找树，查找到指定数据，效率其实很高logn。但是数据库索引文件有可能很大，关系型数据存储了上亿条数据，索引文件大则上G，不可能全部放入内存中，
而是需要的时候换入内存，方式是磁盘页。一般来说树的一个节点就是一个磁盘页。如果使用二叉查找树，那么每个节点存储一个元素，查找到指定元素，需要进行大量的磁盘IO，效率很低。
而B树解决了这个问题，通过单一节点包含多个data，大大降低了树的高度，大大减少了磁盘IO次数。

Q2.B树和二叉查找树的性能对比？

B树包括B+树的设计思想都是尽可能的降低树的高度，以此降低磁盘IO的次数，因为一个索引节点就表示一个磁盘页，页的换入换出次数越多，表示磁盘IO次数越多，越低效。
B树算法减少定位数据所在的节点时所经历的磁盘IO次数，从而加快存取速度。
假设一个节点可以容纳100个值，那么3层的B树可以容纳100万个数据。（根节点100值，第二层可以存储99个节点（k-1），也就是99100 个值，第三层可以存储
（99100-1）*100）结果是近似100万个数据。而如果使用二叉查找树，则需要将近20层，也就是进行20次磁盘IO，性能差距如此之大。
如mongoDB数据库使用，单次查询平均快于Mysql（但侧面来看Mysql至少平均查询耗时差不多）。

Q3.B+对比B树的优点？

因为B树的每个节点除了存储指向子节点的索引之外，还有data域，因此单一节点存储的指向子节点的索引并不是很多，树高度较高，磁盘IO次数较多，
而B+树单一节点存储的指向子节点的索引更多，B+树空间利用率高，因此B+树高度更低，磁盘IO次数更少，性能更好。
因为B树的中间节点存储了数据，所以整个树的每一层都有可能查找到要查找的数据，查询性能不稳定，
而B+树所有的data都存储在叶子节点，且叶子节点位于同一层，因此查询性能稳定。
B树如果想要进行范围查找，需要频繁的进行二叉树的中序遍历，进行范围查找比较复杂，
B+树要查找的元素都位于叶子节点，且连接形成有序链表，便于范围查找。

Q4.B树，B+树使用场景。

B树主要用于文件系统，和部分数据库索引，如文档型数据库mongodb
B+树主要用于mysql数据库索引。

Q5.为什么数据库索引不用红黑树而用B+树？

红黑树当插入删除元素的时候会进行频繁的变色与旋转（左旋，右旋），来保证红黑树的性质，浪费时间。
但是当数据量较小，数据完全可以放入内存中，不需要进行磁盘IO，这时候，红黑树时间复杂度比B+树低。
比如TreeSet TreeMap 和HashMap （jdk1.8）就是使用红黑树作为底层数据结构。

总结

• AVL树是二叉搜索树的优化,左右深度不大于1.,但出现极端情况就为成为链表
• 红黑树为了解决AVL树的极端情况情况,虽然多在AVL树多加一层搜索,但是可以保持稳定性,让节点尽可能均匀分布.红黑树不太适合由于写操作多的环境,旋转太耗时.
• B树一般用于文件的存储.类似我们的文件系统,不需要在同层的节点建立指针,B树的搜索时间复杂度为NlogN.
  优点,可以优化树的深度,假如一个节点存100个数据,而三层可以容纳接近100万个数据.B树可以用于稀疏的数据.
• B+树可以有了B树的优点,还能在同层的节点之中搜索.
• 数据库的索引右B+树索引和哈希索引,哈希索引用于快速查找,B+树由于范围搜索.B+树适合用于稠密的数据

这是一篇说B树 B+树的文章
https://blog.csdn.net/u013411246/article/details/81088914