* 一:    在一个数组中有一个数出现奇数次
*     其余的数都是偶数次,怎么找出现
*     奇数次的这个数
*       findOdd 解决
*
*       如果有两个数出现奇数次怎么找到
*       findOdd2-findOdd2Plus   解决
    /**
     * 已知数组中只有两个数出现奇数次,假设这两个数是a和b
     * 则ans = a^b   且   ans!=0
     * 我们找到ans中不为1的那一个比特位,a和b中在这一位上
     * 必不相同,所以我们可以借此将数组中的数分成两组,使用
     * temp来异或这一位为1的元素,最后temp必为a或者b
     * 最后再用ans^=temp;将两数分离
     * */
*
* 二:    插入排序  insertSort
* 三:    二分查找  binarySearch
* 四:    局部最小值,找到一个无序数组中同时
*       小于左右两边的局部最小值,且这
*       个数组中的两个相邻元素不相等
*       要求效率好于O(N)
*       findPartMin 解决

/**
 *
 * master公式
 * T(N) = a*T(N/b) + O(N^d)
 * a是子问题调用的次数
 * b是子问题的规模
 * d是除去调用子问题的时间复杂度
 * 本例中左右分别调用一次,因此a=2
 * 每个子问题的规模是N/2 因此b=2
 * 最后求最大值的时间复杂度为O(1)
 * 因此该算法的master公式是
 * T(N) = 2*T(N/2) + O(1)
 * 再求时间复杂度:
 * 如果logb(a) < d 则时间复杂度是O(N^d)
 * 如果logb(a) > d 则时间复杂度是O(N^logb(a))
 * 如果logb(a) = d 则时间复杂度是O(log(N)*(N^d))
 * 本算法中的时间复杂度是O(N)
 * */
     * 归并排序的扩展
     * 小和问题和逆序对问题
     * 小和问题
     * 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组
     * 的小和。求一个数组的小和。
     * 例子：[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
     * 解法是把左边小于它的个数看做右边大于它的个数,等效成另外一个问题
     * 如 [1,3,4,2,5] 4*1+2*3+1*4+1*2 = 16 时间复杂度是O(NlogN)计算方法同上
     *
     * 逆序对问题在一个数组中，左边的数如果比右边的数大，则折两个数
     * 构成一个逆序对，请打印所有逆序对的数量。
     *
     * 这两个问题是一个问题
     * *
     * */
    /**
     * 荷兰国旗问题
     * 问题一
     * 给定一个数组arr,和一个数num,请把小于等于num的数放在数组的左边，大于num的
     * 数放在数组的右边。要求额外空间复杂度0(1),时间复杂度0(N)
     * pivo1 pivo2
     * 问题二（荷兰国旗问题）
     * 给定一个数组arr,和一个数num,请把小于num的数放在数组的左边，等于num的数放
     * 在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度0(1),时间复杂度
     * 0(N)
     * pivo3
     * */

/**
 * 堆排序扩展题目
 * 已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元
 * 素移动的距离可以不超过k,并且k相对于数组来说比较小。请选择一个合适的
 * 排序算法针对这个数据进行排序。
 * 我们可以利用小根堆,先将0-k+1进行小根堆排序,然后输出arr[0] 后
 * swap(arr[0],arr[k+2]),然后调整小根堆后输出arr[0]
 * 在java中的PriorityQueue默认使用的就是小根堆
 * 故我们可以利用这个
 * */
     /**
     * bucketSort
     * 计数排序 - 假定我们知道数据的分布范围,如0-100;则我们遍历数组统计每个数的频率
     *           如0有7个...,则在辅助数组上的0位置赋值7,最后根据辅助数组还原整个数组
     *           此时排序的效率是O(N),空间效率未知,因为要根据数据的分布情况来计算
     * 基数排序 - 课本上有,并且就是桶排序
     *
     * */