四、分治思想排序
----概念：将原问题分割为数个简单易求的子问题，用递归解决这些子问题后，合并子问题的答案作为最终答案（分割与合并不能太过复杂）。
1、快速排序原理与应用
----方法概念：
在待排序的数列中，我们首先要找一个数字作为基准数。为了方便，我们一般选择第 1 个数字作为基准数（其实选择第几个并没有关系）。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。
----具体方法：
① 一遍单项扫描法
② 双指针扫描法
③ 三指针分区法（对于重复元素多的可提高其性能）
tips：工程上的优化
① 三点中值法
② 绝对中值法
③ 列表较短时使用插入排序
2、归并法排序
----方法：
分解 将原长度为n的数组分为长度为n/2的两个部分
解决 对两个部分进行递归的排序
合并 合并两个子序列以获得结果（重点）
----相关算法案例：
①左边奇数右边偶数进行归并（使用快排知识点）
② 最快效率找到乱序数组中第k个元素
③ 找出数组中超过数组长度一半的数(4解法Ⅰ排序求中位数ⅡHash统计Ⅲ顺序统计Ⅳ不同的数消除)
④ 寻找发帖水王
⑤ 在非负数组（无序）中找到最小可用id {Ⅰ暴力扫描 n^2 Ⅱ开辟辅助空间Ⅲ先排序再找对应位置是否等于对应值（类比二分法）}
⑥ 合并两有序数组并排序
⑦ 求数组中所有逆序对（1暴力查找2归并排序加一步）
3、堆排序：
----Ⅰ树及二叉树简介：
① 根节点 子节点 叶子节点 每个子节点只有一个父节点 每个父节点可以有多个子节点
② 可以用数组表示一颗树
③ 遍历方法1先序（先根再左右，从上至下）2中序（先左再根再右 从下至上）3后序（）
④ 计算左右子树2i+1和 2i+2， 计算父子树i-1/2取整
----Ⅱ堆的概念：
二叉堆是一个完全二叉树或者近似完全二叉树（有一边完全）
二叉堆满足两个特性：
①每个父节点的键值都大于等于（小于等于）任意一个子节点的键值
②每个节点的左子树，右子树都是一个二叉堆（都是最大堆或最小堆）
大顶堆：任何节点的值都大于子节点的堆
小顶堆：任何节点的值都小于子节点的堆
----堆排序方法（复杂度为nlogn）：
① 堆化（将数组转化为大顶堆或者小顶堆）nlogn
② 排序 （将跟元素与最后一个元素交换位置）nlogn
4、最快的排序方法 --计数排序：
----概念:
用辅助数组对数组中出现的数字计数，数字转下标，下标转数字。
时间复杂度低（为n+k， n为数组长度， k为数组中元素最大值）但消耗空间可能较大
5、桶排序：
----概念：
设计k个桶编号0—k-1，然后将n个输入数分布到各个桶去，对各个桶进行排序，按照次序将各个桶中的数据罗列出来即可
时间复杂度n——nlogn
6、基数排序：
----概念：
按低位有效数字排序，然后逐一像上一位排序，直到最高位结束。（根据各位上的数值将他们遍历在0—9的桶中）
时间复杂度位kn k位最大位数 n位数据数量。
排序算法的总结:
#基础排序
–冒泡排序
谁大谁上，每一轮都把最大的顶到天花板
效率太低O(n2)–掌握swap
–选择排序
效率较低，但经常用它内部的循环方式来找最大值和最小值─怎么一次性求出数练 O(n2)
–插入排序
虽然平均效率低，但是在序列基本有序时，它很快，所以也有其适用范围 Arrays这个工具类在1.7里面做了较大改动
–希尔排序（缩小增量排序），是插排的改良，对空间思维训练有帮助
#分治法
–快排
是软件工业中最常见的常规排序法，其双向指针扫描和分区算法是核心，
往往用于解决类似问题，特别地partition算法用来划分不同性质的元素，
–归并排序
空间换时间–逆序对数
归并重视子问题的解的合并
–堆排序
用到了二叉堆数据结构，是继续掌握树结构的起手式=插排+二分查找
总结：上面三个都是NlgN的复杂度，其中快排表现最好，是原址的不用开辟辅助牢间;
上面7种都是基于比较的排序，可证明它们在元素随机顺序情况下最好是NLgN的。
下面三个是非比较排序，在特定情况会比基于比较的排序要快:
–1.计数排序
可以说是最快的:0(N+k),k=max0f(sourceArr),
用它来解决问题时必须注意如果序列中的值分布非常广，空间将会浪费很多 所以计数排序的适用范围是:序列的关键字比较集中
–⒉.桶排序
先分桶，再用其他排序方法对桶内元素排序，按桶的编号依次检出。(分配-收集 用它解决问题必须注意序列的值是否均匀地分布在桶中）。
如果不均匀，那么个别桶中的元素会远多于其他桶，桶内排序用比较排序，极端情况下，全部 还是会退化成NlgN
其时间复杂度是∶时间复杂度:O(N+C)，其中C=N*(logN-logM)，约等于N*lgN N是元素个数，M是桶的个数。
–3.基数排序
kN级别〈k是最大数的位数）是整数数值型排序里面又快又稳的，无论元素分布 只开辟固定的辅助空间(10个桶)
对比桶排序，基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作 桶内多个数据必须进行基于比较操作的排序。
因此，在实际应用中，对十进制整数来说，基数排序的应用范围更加广泛。
算法时间复杂度总结
