图灵之旅--二叉树堆排序

树型结构

概念

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成的有层次关系的集合

特点:

有一个特殊结点,叫作根结点,根节点没有前驱结点
除根结点,其余结点被分成M(M>0)个互不相交的集合T1,T2,…Tm,其中每个集合T又是一棵与树类似的子树,每棵子树的根结点有且只有一个前驱,可以有0或多个后继
树是递归定义
注意:树形结构中,子树之间不能有交际,否则不是树形结构
树:
子树是不相交的
除了根结点外,每个结点有且仅有一个父结点
一棵N个结点的树有N-1条边

结点的度：一个结点含有子树的个数称为该结点的度；
树的度：一棵树中，所有结点度的最大值称为树的度；
叶子结点或终端结点：度为0的结点称为叶结点；
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；
根结点：一棵树中，没有双亲结点的结点；
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
树的高度或深度：树中结点的最大层次；
非终端结点或分支结点：度不为0的结点；
兄弟结点：具有相同父结点的结点互称为兄弟结点；
堂兄弟结点：双亲在同一层的结点互为堂兄弟；
结点的祖先：从根到该结点所经分支上的所有结点；
子孙：以某结点为根的子树中任一结点都称为该结点的子孙。
森林：由m（m>=0）棵互不相交的树组成的集合称为森林

树的表示形式

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等

二叉树

概念

一棵二叉树是结点的一 个有限集合,该集合:

1. 或者为空
2. 或者是由一个根节点加上两棵左子树和右子树的二叉树组成

特点:

1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是序树

特殊的二叉树

1. 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

二叉树性质

1. 根结点的层数是1,则一棵非空二叉树的第i层上最多有2^(i-1)(i>0)个结点
2. 只有根结点的二叉树的深度为1,则深度为k的二叉树的最大结点数是2^k-1(k>=0)
3. 对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0=n2+1;
4. 具有n个结点的完全二叉树,如果按照上至下从左至右的顺序对所有结点从0开始编号,则对于序号为i的结点有:

若i>0,双亲序号:(i-1)/2;i=0,i为根结点编号,无双亲结点
若2i+1<n,左孩子序号:2i+1,否则无左孩子
若2i+2<n,右孩子序号:2i+2,否则无右孩子

5. 具有n个结点的完全二叉树的深度k为log2(n+1)上取整

二叉树的存储

二叉树的存储结构分为：顺序存储和类似于链表的链式存储。

二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式

// 孩子表示法
class Node {
  int val; // 数据域
  Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
  Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
  int val; // 数据域
  Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
  Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
  Node parent;   // 当前节点的根节点
}

二叉树的遍历

前中后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加1)。 遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。
在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L代表根节点的左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：
NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—>根的左子树—>根的右子树。
LNR：中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树。
LRN：后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点。

给你一个前序遍历序列和后序遍历序列不能创建一个二叉树,因为前序和后序确定的是根,不能确定左右

public class BinaryTree {
    public static class TreeNode {
        public char val;
        public int res;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
        public TreeNode(int res) {
            this.res = res;
        }
    }
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        TreeNode root = A;
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        E.right = H;
        C.left = F;
        C.right = G;
        return root;
    }
    // 前序遍历
    void preOrder(TreeNode root) {
        if(root==null) {
            return;
        }
        System.out.print(root.val+" ");

        preOrder(root.left);
        preOrder(root.right);
    }
    // 中序遍历
    void inOrder(TreeNode root) {
        if(root==null) {
            return;
        }

        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    // 后序遍历
    void postOrder(TreeNode root) {
        if(root==null) {
            return;
        }

        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");

    }

    public int nodeSize;
    // 获取树中节点的个数
    int size(TreeNode root) {
        if(root==null) {
            return 0;
        }
        return size(root.left)+size(root.right)+1;
    }
    // 获取叶子节点的个数
    public int leafNode;
    int getLeafNodeCount(TreeNode root) {
        if(root==null) {
            return 0;
        }
        if((root.left==null)&&(root.right==null)){
            return 1;
        }
        return  getLeafNodeCount(root.left) +
                getLeafNodeCount(root.right);
    }
    // 子问题思路-求叶子结点个数
// 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root,int k) {
        if(root==null) {
            return 0;
        }
        if(k==1) {
            return 1;
        }

        return getKLevelNodeCount(root.left,k-1) +
                getKLevelNodeCount(root.right,k-1);
    }
    // 获取二叉树的高度
    int getHeight(TreeNode root) {
        if(root==null) {
            return 0;
        }

        return 1+(Math.max(getHeight(root.left), getHeight(root.right)));
    }
    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        if(root==null) {
            return null;
        }
        if(root.val==val) {
            return root;
        }
        if(find(root.left,val)!=null) {
            return find(root.left,val);
        };
        if(find(root.right,val)!=null) {
            return find(root.right,val);
        };
        return null;
    }
    //层序遍历
    public Queue<TreeNode> queue = new LinkedList<>();
    void levelOrderQueue(TreeNode root) {
        if(root==null) {
            return;
        }
        if(root.left!=null) {
            queue.offer(root.left);
        }
        if(root.right!=null) {
            queue.offer(root.right);
        }
        System.out.print(queue.poll().val+" ");
        levelOrderQueue(queue.peek());
    }
}

优先级队列(堆)

概念

队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队
列时，可能需要优先级高的元素先出队列
要实现上述功能,该数据结构要有两个基本操作,一个是返回最高级优先级对象,一个是添加新的对象,这种数据结构就是优先级队列

优先级队列的模拟实现

JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整

堆的性质

1. 堆中的某个结点的值总是不大于或者不小于父结点的值
2. 堆总是一棵完全二叉树

概念

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大
堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
小根堆: 根结点比左右结点都小,但是左右结点谁更小没有关系,只考虑根结点和左右结点的关系
大根堆: 根结点比左右孩子都大,左右结点的大小无所谓
存储的时候放在数组中
数组中能不能存储一个非完全二叉树?
完全二叉树中,数组存储它的层序遍历结果,如果是存放在一个非完全二叉树中会出现浪费空间的结果

堆的存储方式

在堆的概念中,堆是一颗完全二叉树,因此可以按照层序遍历的规则来进行顺序的存储

注意:对于非完全二叉树,则不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间必须存储空结点,导致空间利用率降低

如何实现代码实现优先级队列,一定要看作大根堆或者小根堆

将元素存储到数组中后。假设i为节点在数组中的下标，则有：
如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

一个普通二叉树转换成一个大根堆或者小根堆,对于大根堆而言,调整过程:
1.对最后一棵子树进行调整
2.然后找到左右结点的最大值和根结点比较,大的话就和根结点的值进行交换
3. 如果得知根结点的下标,那么下一棵子树就是该下标-1
4. 一直调整到0下标这棵树为止

问题:

1. 每棵子树调整的时候,结束位置怎么确定?
   根据数组长度,如下(之前的结论):
   如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
   如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子
   根据父结点下标和数组长度判断左右孩子是否存在的方法进行判断,用于向下调整的方法

2. 最后一棵子树的根结点下标怎么确实?
   已知最后一个结点的下标是数组长度-1,而已知一个结点的下标求父亲结点,就是该下标-1再除以2((index-1)/2=fatherIndex)

堆的创建

import java.util.Arrays;

public class Heap {
    public int[] elements;
    //堆当中有效的数据个数
    public int usedSize;
    public Heap() {
        elements = new int[20];
    }

    /**
     * 初始化数组
     */
    public void initArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            elements[i] = arr[i];
            usedSize++;
        }
    }

    /**
     * 创建大根堆
     */
    public void createHeap() {
        for (int i = (usedSize-2)/2; i >= 0 ; i--) {
            adjustDown(i,usedSize);
        }
    }

    /**
     * 向下调整
     * @param parent
     * @param len
     */
    private void adjustDown(int parent, int len) {
        //孩子结点的下标初始化为左孩子的结点的下标
        int child = parent*2 +1;
        //要交换至少你要存在左孩子才能进行交换
        //交换之后,child这个变量代表要交换的那个孩子的下标
        //如果存在左右孩子的话,就比较哪个孩子的值大
        //如果只存在左孩子的话,那么没得选,只能是左孩子下标
        //因为是完全二叉树,所以,存在右孩子必然存在左孩子
        //但是存在左孩子不一定存在右孩子
        while(child<len) {
            //保证右孩子存在,不然可能会导致数组越界
            //右孩子存在且比左孩子大,则要更新child变量
            //child始终是左右孩子最大的那个下标
            if(child+1<len&&
              elements[child]<elements[child+1]) {
                child++;
            }
            //左右孩子最大值大于父结点的值,数值进行交换
            //父结点,孩子结点进行更新,继续向下进行调整
            if(elements[child]>elements[parent]) {
                swap(parent,child);
                parent = child;
                child = parent*2+1;
            }else {
                //如果孩子下标合法,但是父结点比他们最大值还大
                //跳出即可,因为下面的子树本来就调整完了,下面
                //子树的最大值肯定小于父结点的值,那么父结点
                //的值都小于父结点的父亲的值的话,下面没必要进行
                //调整了
                break;
            }
        }
    }
    //判断是否满
    private boolean isFull() {
        return usedSize==elements.length;
    }
    //扩容
    private void enLarger() {
        elements = Arrays.copyOf(elements,elements.length*2);
    }
    private void swap(int parent,int child) {
        int tmp = elements[parent];
        elements[parent] = elements[child];
        elements[child] = tmp;
    }

    /**
     * 对于大根堆来说,如果新的数据比父结点的值小,那么就没必要进行向上调整,
     * 因为父结点的父结点的值一定比父结点大,新的数据比父结点都小,所以一定比
     * 父结点的父结点的值小,但是如果新的数据比父结点的值大,就要交换,新的数据在左结点
     * 或者右节点都只需要和父结点比较,因为即便新数据在右节点,父结点的左节点一定比
     * 父结点小,所以只考虑和父结点的数据进行比较大小即可
     * @param val
     */
    public void insertHeap(int val) {
        if(isFull()) {
            elements = Arrays.copyOf(elements,elements.length*2);
        }
        usedSize++;
        int child = usedSize-1;
        int parent = (child-1)/2;
        elements[child] = val;
        while (child!=0) {
            if(elements[parent]<elements[child]) {
                swap(parent,child);
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }
}

插入操作是利用向上建堆的方法来进行插入的,但是向上建堆的时间复杂度比较大,所以不推荐
向下建堆是从n-1层开始逐层建堆,而向上建堆从最后一层第n层开始调整,而最后一次的结点数目接近总结点数的一半,时间复杂度较大
建堆的时间复杂度是O(N)

堆常用接口介绍

PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的

注意:

1. 使用时必须导入PriorityQueue所在的包，即：

import java.util.PriorityQueue;

2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常
3. 不能插入null对象，否则会抛出NullPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5. 插入和删除元素的时间复杂度为
6. PriorityQueue底层使用了堆数据结构
7. PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素

PriorityQueue常用接口介绍

优先级队列的构造

构造器 功能介绍
PriorityQueue() 创建一个空的优先级队列，默认容量是11
PriorityQueue(int initialCapacity)
创建一个初始容量为initialCapacity的优先级队列，注意：
initialCapacity不能小于1，否则会抛IllegalArgumentException异常
PriorityQueue(Collection<? extends E> c) 用一个集合来创建优先级队列

        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.offer(1);
        priorityQueue.offer(2);
        priorityQueue.offer(3);

        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());

默认是小堆,大堆需要用户自己实现

class IntCompare implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
public class Test {

    public static void main(String[] args) {
        IntCompare intCompare = new IntCompare();
        PriorityQueue priorityQueue = new PriorityQueue(intCompare);
        priorityQueue.offer(1);
        priorityQueue.offer(2);
        priorityQueue.offer(3);

        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());

    }
}

插入/删除/获取优先级最高的元素

函数名 功能介绍
boolean offer(E e)
插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时
间复杂度 ，注意：空间不够时候会进行扩容
E peek() 获取优先级最高的元素，如果优先级队列为空，返回null
E poll() 移除优先级最高的元素并返回，如果优先级队列为空，返回null
int size() 获取有效元素的个数
void clear() 清空
boolean isEmpty() 检测优先级队列是否为空，空返回true

优先级队列的扩容说明：
如果容量小于64时，是按照oldCapacity的2倍方式扩容的
如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容

堆的应用

PriorityQueue的实现

用堆作为底层结构封装优先级队列

堆排序

1. 建堆
   升序：建大堆
   降序：建小堆
2. 利用堆删除思想来进行排序

    public void heapSort() {
        int end = usedSize-1;
        while (end!=0) {
            swap(0,end);
            adjustDown(0,end--);
        }
    }

Top-k问题

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

1. 用数据集合中前K个元素来建堆
   前k个最大的元素，则建小堆
   前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
   将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

题目链接

class Solution {
    public int[] smallestK(int[] arr, int k) {
        int[] array = new int[k];
        if(arr.length==0||k==0) {
            return array;
        }
        if (arr.length <= k) {
            return arr;
        }
        //内部类重新实现compare方法,变成大堆
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        int len = arr.length;
        for (int i = k; i < len; i++) {
        //用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
            if (arr[i] < priorityQueue.peek()) {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        for (int i = 0; i < k; i++) {
            array[i] = priorityQueue.poll();
        }
        return array;
    }
}

java对象的比较

PriorityQueue中插入对象

优先级队列插入元素要求:插入的元素必须可以比较或者不能是null

优先级队列底层使用堆,向堆中插入元素必须要进行比较

元素比较

在Java中,基本类型的对象可以直接进行比较

对于引用类型而言,并不能直接用>或者<的方式比较,可以比较,但是对于用户自己的自定义类型默认继承Object类,而当使用比较时会默认调用equal方法,而该方法并非比较对象的内容,而是比较引用变量的地址

对象比较

要比较对象的内容,就像优先级队列中插入对象,需要按照对象内容来进行调整

覆写基类的equals

class Student {
    private int age;
    private String name;
    public Student(int age) {
        this.age = age;
    }
    public int getAge() {
        return age;
    }

    @Override
    public boolean equals(Object obj) {
        //判断是不是同一个引用
        if(this==obj) {
            return true;
        }
        //如果obj是null对象或者不是Student的子类
        if(obj==null||!(obj instanceof Student)) {
            return false;
        }
        Student s = (Student)obj;
        return this.age==s.age
                && this.name.equals(s.name);
    }
}

覆写equals的套路

1. 如果指向同一个对象，返回 true
2. 如果传入的为 null，返回 false
3. 如果传入的对象类型不是Student，返回 false
4. 按照类的实现目标完成比较
5. 注意下调用其他引用类型的比较也需要 equals，例如这里的 name 的比较

覆写基类equal的方式虽然可以比较，但缺陷是：equal只能按照相等进行比较，不能按照大于、小于的方式进行比较。

基于Comparble接口类的比较

Comparble是JDK提供的泛型的比较接口类，源码实现具体如下：

public interface Comparable<E> {
  // 返回值:
  // < 0: 表示 this 指向的对象小于 o 指向的对象
  // == 0: 表示 this 指向的对象等于 o 指向的对象
  // > 0: 表示 this 指向的对象大于 o 指向的对象
  int compareTo(E o);
}

对用用户自定义类型，如果要想按照大小与方式进行比较时：在定义类时，实现Comparble接口即可，然后在类中重写compareTo方法。

基于比较器比较

覆写Comparator中的compare方法

class StuAgeComparator implements Comparator<Student> {
    @Override
    public int compare(Student o1, Student o2) {
        if(o1==o2) {
            return 0;
        }
        //null看作最小
        if(o1==null) {
            return -1;
        }
        if(o2==null) {
            return 1;
        }
        return o1.getAge()-o2.getAge();
    }
}

三种方式对比

覆写的方法 说明
Object.equals
因为所有类都是继承自 Object 的，所以直接覆写即可，不过只能比较相等与
否
Comparable.compareTo
需要手动实现接口，侵入性比较强，但一旦实现，每次用该类都有顺序，属于
内部顺序
Comparator.compare
需要实现一个比较器对象，对待比较类的侵入性弱，但对算法代码实现侵入性
强

集合框架中PriorityQueue的比较方式

集合框架中的PriorityQueue底层使用堆结构，因此其内部的元素必须要能够比大小，PriorityQueue采用了：
Comparble和Comparator两种方式。

1. Comparble是默认的内部比较方式，如果用户插入自定义类型对象时，该类对象必须要实现Comparble接口，并覆写compareTo方法
2. 用户也可以选择使用比较器对象，如果用户插入自定义类型对象时，必须要提供一个比较器类，让该类实现Comparator接口并覆写compare方法

排序

稳定排序:存在相同的数值,如上图的1,排序之前的相对顺序和排序之后的相对顺序不发生改变,不稳定的排序则相反

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳
定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

直接插入排序

	public static void InsertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+1] = tmp;
        }
    }

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

一个稳定的排序可以实现为一个不稳定的排序,但是一个不稳定的排序一定不能变成一个稳定的排序

希尔排序

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

稳定性：不稳定

public static void ShellSort(int[] arr) {
        int gap = arr.length;
        while(gap>1) {
            gap /= 2;
            Shell(arr,gap);
        }
    }

    /**
     * 对每组进行插入排序
     * @param arr
     * @param gap
     */
    private static void Shell(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-gap;
            for (; j >=0 ; j-=gap) {
                if(arr[j]>tmp) {
                    arr[j+gap] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }

选择排序

基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

直接选择排序

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
【直接选择排序的特性总结】

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

	public static void selectSort(int[] arr) {
        if(arr.length<=1) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j]<arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(minIndex,i,arr);
        }
    }
    private static void swap(int i, int j, int[] arr) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

双向选择排序

public static void selectSort2(int[] arr) {
        if(arr.length<=1) {
            return;
        }
        int left = 0;
        int right = arr.length-1;
        while (left<right) {
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <= right; i++) {
                if(arr[minIndex]>arr[i]) {
                    minIndex = i;
                }
                if(arr[maxIndex]<arr[i]) {
                    maxIndex = i;
                }
            }
            swap(minIndex,left,arr);
            if(left==maxIndex) {
                maxIndex = minIndex;
            }
            swap(maxIndex,right,arr);
            left++;
            right--;
        }
    }

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

 static void heapSort(int[] arr) {
        createHeap(arr);
        int end = arr.length-1;
        while (end!=0) {
            swap(end,0,arr);
            adjustDown(arr,0,end);
            end--;
        }
    }

    private static void createHeap(int[] arr) {
        for (int parent = (arr.length-1-1)/2; parent >= 0; parent--) {
            adjustDown(arr,parent,arr.length);
        }
    }

    private static void adjustDown(int[] arr, int parent, int length) {
        int child = parent*2+1;
        while (child<length) {
            if(child+1<length&&arr[child+1]>arr[child]) {
                child++;
            }
            if(arr[child]>arr[parent]) {
                swap(child,parent,arr);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }

【直接选择排序的特性总结】

1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

冒泡排序

public static void bubbleSort(int[] arr) {
        //i表示趟数
        //flg表示判断这一趟是否交换,没交换的话说明已经排序好了
        for (int i = 0; i < arr.length-1; i++) {
            boolean flg = true;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1]) {
                    swap(j,j+1,arr);
                    flg = false;
                }
            }
            if(flg) {
                break;
            }
        }
    }

【冒泡排序的特性总结】

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

快速排序

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有
元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

public static void quickSort(int[] arr) {
        quick(arr,0,arr.length-1);
    }
    private static void quick(int[] arr, int left, int right) {
        if(left>=right) {
            return;
        }
        int res = part(arr,left,right);
        quick(arr,left,res-1);
        quick(arr,res+1,right);
    }

    private static int part(int[] arr, int left, int right) {
        int std = arr[left];
        int start = left;
        while (left<right) {
        //arr[right]>=std去等号可能会出现死循环
        //先从右边开始而非左边开始是因为:可能相遇时遇到比基准数大的数
        //会造成最后不会出现基准数左侧比他都小
            while (left<right&&arr[right]>=std) {
                right--;
            }
            while (left<right&&arr[left]<=std) {
                left++;
            }
            swap(right,left,arr);
        }
        swap(start,left,arr);
        return left;
    }

将区间按照基准值划分为左右两半部分的常见方式有：

1. Hoare版

    private static int part(int[] arr, int left, int right) {
        int std = arr[left];
        int start = left;
        while (left<right) {
            while (left<right&&arr[right]>=std) {
                right--;
            }
            while (left<right&&arr[left]<=std) {
                left++;
            }
            swap(right,left,arr);
        }
        swap(start,left,arr);
        return left;
    }

2. 挖坑法

	private static int DigHole(int[] arr, int left, int right) {
        int std = arr[left];
        int start = left;
        while (left<right) {
            while (left<right&&arr[right]>=std) {
                right--;
            }
            arr[left] = arr[right];
            while (left<right&&arr[left]<=std) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = std;
        return left;
    }

3. 前后指针法

	private static int leftrRightPointers(int[] arr, int left, int right) {
        int prev = left;
        int cur = left+1;
        while (cur<=right) {
            if(arr[cur]<arr[left]&&arr[++prev]!=arr[cur]) {
                swap(cur,prev,arr);
            }
            cur++;
        }
        swap(prev,left,arr);
        return prev;
    }

快速排序优化

1. 三数取中法选key
   找出left,right,mid下标的中值坐标,和坐标互换,作为基准,尽可能减少左右子树分布不均匀的情况
2. 递归到小的子区间时，可以考虑使用插入排序
   因为区间越小,会趋于有序,使用插入排序提高效率

private static void quick(int[] arr, int left, int right) {
        if(left>=right) {
            return;
        }
        //中值作为基准
        int mid = middleNum(arr,left,right);
        swap(mid,left,arr);

        int res = part(arr,left,right);
        quick(arr,left,res-1);
        quick(arr,res+1,right);
    }

    private static int middleNum(int[] arr, int left, int right) {
        int mid = (left+right)/2;
        if(arr[left]<arr[right]) {
            if(arr[mid]<arr[left]) {
                return left;
            } else if (arr[right]>arr[mid]) {
                return right;
            } else {
                return mid;
            }
        }else {
            if(arr[mid]<arr[right]) {
                return right;
            } else if (arr[left]>arr[mid]) {
                return left;
            } else {
                return mid;
            }
        }
    }
    private static int part(int[] arr, int left, int right) {
        int std = arr[left];
        int start = left;
        while (left!=right) {
            while (left<right&&arr[right]>=std) {
                right--;
            }
            while (left<right&&arr[left]<=std) {
                left++;
            }
            swap(right,left,arr);
        }
        swap(start,left,arr);
        return left;
    }

快速排序非递归

public static void quickSortRor(int[] arr) {
        int start = 0;
        int end = arr.length-1;
        Stack<Integer> stack = new Stack<>();
        int std = DigHole(arr,start,end);
        if(std-1>start) {
            stack.push(start);
            stack.push(std-1);
        }
        if(std+1<end) {
            stack.push(std+1);
            stack.push(end);
        }
        while (!stack.isEmpty()) {
            if(!stack.isEmpty()) {
                end = stack.pop();
                start = stack.pop();
            }
            std = DigHole(arr,start,end);
            // 以基准值为分割点，形成左右两部分：[left, std) 和 [std+1, right)
            if(std-1>start) {
                stack.push(start);
                stack.push(std-1);
            }
            if(std+1<end) {
                stack.push(std+1);
                stack.push(end);
            }
        }

快速排序总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使
子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

递归归并排序代码

public static void mergeSort(int[] arr) {
        mergeLink(arr,0,arr.length-1);
    }


    private static void mergeLink(int[] arr, int left, int right) {
        if(left>=right) {
            return;
        }
        int mid = (left+right)/2;
        mergeLink(arr,left,mid);
        mergeLink(arr,mid+1,right);
        merge(arr,left,mid,right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int oneStart = left;
        int oneEnd = mid;
        int twoStart = mid+1;
        int twoEnd = right;
        int[] tmpArray = new int[right-left+1];
        int k = 0;
        while (oneStart<=oneEnd&&twoStart<=twoEnd) {
            if(arr[oneStart]<arr[twoStart]) {
                tmpArray[k++] = arr[oneStart++];
            }else {
                tmpArray[k++] = arr[twoStart++];
            }
        }
        while(oneStart<=oneEnd) {
            tmpArray[k++] = arr[oneStart++];
        }
        while (twoStart<=twoEnd) {
            tmpArray[k++] = arr[twoStart++];
        }
        for (int i = 0; i < tmpArray.length; i++) {
            arr[i+left] = tmpArray[i];
        }
    }

递归归并排序代码

public static void mergeSortNor(int[] arr) {
        int gap = 1;
        while (gap<arr.length) {
            for (int i = 0; i < arr.length; i+=gap*2) {
                int left = i;
                int mid = left+gap-1;
                int right = mid+gap;
                if(mid>=arr.length) {
                    mid = arr.length-1;
                }
                if(right>=arr.length) {
                    right = arr.length - 1;
                }
                merge(arr,left,mid,right);
            }

            gap *= 2;
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int oneStart = left;
        int oneEnd = mid;
        int twoStart = mid+1;
        int twoEnd = right;
        int[] tmpArray = new int[right-left+1];
        int k = 0;
        while (oneStart<=oneEnd&&twoStart<=twoEnd) {
            if(arr[oneStart]<arr[twoStart]) {
                tmpArray[k++] = arr[oneStart++];
            }else {
                tmpArray[k++] = arr[twoStart++];
            }
        }
        while(oneStart<=oneEnd) {
            tmpArray[k++] = arr[oneStart++];
        }
        while (twoStart<=twoEnd) {
            tmpArray[k++] = arr[twoStart++];
        }
        for (int i = 0; i < tmpArray.length; i++) {
            arr[i+left] = tmpArray[i];
        }
    }

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

1. 先把文件切分成 200 份，每个 512 M
2. 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

非基于比较排序

计数排序

指定范围内排序

1. 申请一个数组(长度:最大值-最小值+1)
2. 遍历原来的数组,把数字对应的数组下标进行++
3. 遍历计数数组,写回到原来数组(注意:写的次数要和元素值一样)

public static void countSort(int[] arr) {
        if(arr.length<=1) {
            return;
        }
        //求最大值和最小值
        int min = arr[0];
        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]>max) {
                max = arr[i];
            }
            if(arr[i]<min) {
                min = arr[i];
            }
        }
        //确定数组长度
        int[] countArray = new int[max-min+1];
        //遍历数组,把数据出现的次数存储到数组中
        for (int i = 0; i < arr.length; i++) {
            countArray[arr[i]-min]++;
        }
        //遍历计数数组 把实际的数据写回arr数组
        int k = 0;
        for (int i = 0; i < countArray.length; i++) {
            while (countArray[i]>0) {
                arr[k++] = i+min;
                countArray[i]--;
            }
        }
    }

【计数排序的特性总结】

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定