-
mid=(L+R)/2 可能会溢出；改成 mid=L+(L-R)/2；提升效率，改成mid=L+(R-L)>>1。
-
mid=(L+R)/2 可能会溢出；改成 mid=L+(L-R)/2；提升效率，改成mid=L+(R-L)>>1。
-
其中：a代表子规模执行次数，b代表子规模大小，d代表除了子规模调用其他的操作的时间复杂度。
-
若logba<d ，时间复杂度为 O(Nd)
-
若logba>d ，时间复杂度为 O(Nlogba)
-
若logba==d ，时间复杂度为 O(Nb * logN)
归并排序
-
整体就是一个简单递归，左边排好序、右边排好序，让其整体有序。
-
让其整体有序的过程用了外排序方法.
-
利用master公式来求解时间复杂度
-
归并排序比另外三个（插入、查找、冒泡）优秀的实质（没有浪费比较，每一轮比较都将结果留存下来了顺序的一个部分数组，不遗漏不重算） 时间复杂度O(N*logN)，额外空间复杂度O(N)
不遗漏不重算：举例数组[a,b,c,d,e,f,g]，以c为例子，a,b先比成为[a,b]，然后与c相比合并成[..c..]的一个数组，接下来c依次合并，并与下面的未知继续比较合并，每个都只比较一次。 为什么归并排序过程中能实现单方向的大小判断？ 实际上是因为归并排序在排序过程中保持了数据的局部有序性，当合并时，在两个子数组整体之间存在相对位置关系。这也是为什么只有在合并的时候才能进行单方向上的大小判断 merge_sort.java
小数和问题Redo（分治策略）
问题描述：小和问题和逆序对问题 小和问题 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组 的小和。求一个数组 的小和。 例子:[1,3,4,2,5] 1左边比1小的数，没有; 3左边比3小的数，1; 4左 边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、 2; 所以小和为1+1+3+1+1+3+4+2=16 思路：将求左边比自己小的数转换为求右边比自己大的数的数量，再乘上本身，加给结果 merge_fenzhi.java
逆序对问题
问题描述：数组中的两个数，若前面的一个数大于后面的一个数，那么这两个数组成一个逆序对。输入一个数组，返回逆序对的个数 merge_nixudui.java
快排
时间最差情况是O(N2),原因就是划分的位置太差了，即取得第一个或最后一个值 空间最差是O(N)，最好和平均(收敛至)是O(logN),要记录基数(划分值)位置 挖坑填数 + 分治法：举例｛7，5，9，4，1，3，10｝，取第一个数为基数，存到temp中，0位置上空出来，从后往前找第一个比temp小的数字，挖出来放到0位置上，这里是3，然后3位置空出来了，从前往后找比temp大的，这里是9，然后将9放入3位置上，9位置空了出来，从后往前找比7小的数，这里是1，然后从前往后找比temp大的，无了，左右指针相遇，将temp放入4位置
-
1.0 直接交换 分成两部分，一部分是小于该数，另一部分是大于该数
-
2.0 分成三部分，一部分是小于该数，一部分是等于该数，另一部分是大于该数。可以一次确定一批数
-
3.0 每次选数之前，随机等概率选一个位置的数和最后一个数交换，然后再取最后一个数开始划分。这样复杂度为O(N*logN)
-
4.0 三数取中法，虽然随机基准数方法选取方式减少了出现不好分割的几率，但是最坏情况下还是 O(n²)。为了缓解这个尴尬的气氛，就引入了「三数取中」这样的基准数选取方式 快排1.0 `=quick_sort1.java 快排3.0 quick_sort3.java 快排4.0实现仅替换quick_sort3的partition部分
private static int partition(int[] arr, int left, int right) {
// 采用三数中值分割法
int mid = left + (right - left) / 2;
// 保证左端较小
if (arr[left] > arr[right])
swap(arr, left, right);
// 保证中间较小
if (arr[mid] > arr[right])
swap(arr, mid, right);
// 保证中间最小，左右最大
if (arr[mid] > arr[left])
swap(arr, left, mid);
int pivot = arr[left];
while (right > left) {
// 先判断基准数和后面的数依次比较
while (pivot <= arr[right] && left < right) {
--right;
}
// 当基准数大于了 arr[right]，则填坑
if (left < right) {
arr[left] = arr[right];
++left;
}
// 现在是 arr[right] 需要填坑了
while (pivot >= arr[left] && left < right) {
++left;
}
if (left < right) {
arr[right] = arr[left];
--right;
}
}
arr[left] = pivot;
return left;
}
荷兰国旗问题
(上面问题中条件添加，将等于num的放在数组中间) quick_helanflag.java
TRANSLATE with