直接插入排序法

基本思想: 再要排序的数组中，假设前面的n-1（n>=2）个数已经是排号顺序的。现在要把第n个数插入到前面的有序数组中，使得这n个数也是排好序的，如此循环直到全部排序完成。

时间复杂度: 时间复杂度 O（nn） ，空间复杂度O(1)

结构的复杂性及适用情况: 是一种简单的排序算法。不仅适合顺序存储结构（数组），而且适合连接存储结构（链表），只不过连接存储结构不用在移动数据只需要移动指针。

*哨兵 算法中引入的附加记录R[0] 成为监视哨、哨兵（Sentinel）

作用1：进入循环查找之前记录保存了R[i]的副本。使后来不至于因记录后移而丢失数据

作用2：可以监视j的数据。如果一单j的数据小鱼了哨兵位置数据马上停止循环。
思考1:一切为了简化边界条件而引入的结点能成为哨兵。哨兵使得循环次数大为减少

`

public static void straightInsertionSort(int[] array) {

    //哨兵
    int sentinel, j;

    //循环
    for (int i = 1; i < array.length; i++) {
        j = i - 1;

        // 哨兵位 
        sentinel = array[i];

        //找到当前哨兵位置数据的位置
        while (j >= 0 && sentinel < array[j]) {
            array[j + 1] = array[j];// 将大于sentinel的值整体后移一个单位
            j--;
        }

        //进行赋值
        array[j + 1] = sentinel;
    }
}

`

冒泡排序法

基本思路：比较相邻的两个元素大小，如果第一个比第二个大交换两个元素位置

时间复杂度： O(n*n)
思想1 里层循环只负责把最大的数放到里层循环的末尾。外层循环控制负责没里层做完
一次循环减少元素个数

`

public void sort(int[] a){
    int temp = 0;
    for (int i = a.length - 1; i > 0; --i){
        for (int j = 0; j < i; ++j){
            if (a[j + 1] < a[j]){
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

`

###快速排序###

基本思想： 选择一个基准元素，通常选择第一个元素或者选择最后一个元素。通过一次扫描
将带排序的数组分为两部分，一部分比基准元素小，一部分比基准元素大或者相等。此时基准元素
正好在排好序的位置。然后在用递归方法排序划分的两个部分。

时间复杂度： 最理想 O(nlogn) 最差时间O(n^2)

说明： 快速排序是对冒泡排序的一种改进。最理想的就是每次选择的是正好中间的数据。
最差时间就是冒泡排序

####堆排序####

什么是堆： 一种数据结构，堆可以视为一颗完全二叉树
（除了底层之外每一层都是满的），可以采用数组来表示堆（完全二叉树）

分类： 最大堆、最小堆。最大堆父节点大于或者等于每个子节点，
树中最大数出现在根结点。最小堆相反。

节点与数组索引的关系: parent(i) left=(2i) right=(2i+1)

初始化最大堆

得到无序初始化堆

a[]={16,7,3,20,17,8}

初始化过程从最后一个结点开始调整



初始化总结: 每次调整都是从父节点、左孩子结点、右孩子结点三者中选择最大的
跟父节点进行交换，每次交换后需要重新对被交换的孩子节点进行调整。

堆的插入删除: 整体概括

堆插入：每次都是将新数据放到数组的最后。可以发现插入新数据前这个数组是个有序数组，
这样新插入堆元素可以使用 直接插入算法变种算法，我只需要比较当前插入数据和父的关系，
进行数据交换。

堆删除： 堆的删除只能删除堆顶数据，然后把最后一个数据放到堆顶（这样的操作是为了
快速构件出新的堆结构），然后执行自上而下的比较。

时间复杂度计算： 每次修正的时间复杂度是O(logN),初始化堆的时间复杂度是O(N*logN)。
所以最后整个堆的时间复杂度 M*logM +(N-M)*log(N-M) 一般M比较小，所以整个堆排序的时间复杂度是 N*logN

public class MyHeapSort {
    private static int[] sort = new int[] { 1, 0, 10, 20, 3, 5, 6, 4, 9, 8, 12,
            17, 34, 11 };

    public static void main(String[] args) {
        buildMaxHeapify(sort);
    }

    /**
     * 得到左孩子节点下标
     * 
     * @param index
     * @return
     */
    public static int getLeftChild(int index){
        return (index<<1)+1;
    }

    /**
     * 
     * 得到右孩子节点下标
     * @param index
     * @return
     */
    public static int getRightChild(int index){
        return (index<<1)+2;
    }

    /**
     * 得到父节点
     * 
     * @param index
     * @return
     */
    public static int getParent(int index){
        return (index-1)>>1;
    }

    /**
     * 每次递归都是一棵小树比较
     * 包括比较时边界的限定
     * 
     * @param heap
     */
    public static void initHeap(int[] heap,int heapSize,int lastParent){

        //当前节点位置最大
        int max = lastParent;
        int left = getLeftChild(lastParent);
        int right = getRightChild(lastParent);



        //不能交换值 只能交换位置
        if(left<heapSize&&heap[max]<heap[left]){
            max = left;
        }
        if(right<heapSize&&heap[max]<heap[right]){
            max = right;
        }

        // 交换值，把叶子节点为父的树从新排序
        if(heap[lastParent] != heap[max]){
            int temp = heap[lastParent];
            heap[lastParent] = heap[max];
            heap[max] = temp;

            //这个递归是为了交换后下面子树的顺序维护
            initHeap(heap,heapSize,max);
        }
    }

    //得到最后一个元素的父节点进行比较
    public static void buildMaxHeapify(int[] heap){
        int last = heap.length-1;
        int lastParent = getParent(last);
        for(int i=lastParent;i>=0;i--){
            initHeap(heap,heap.length,i);
        }
        for(int aa:heap){
            System.out.println(aa);
        }
    }
}

####BitMap####

基本思想： 使用bit来标记数据一个bit位对应一个数。
以前的一个整数占用空间4个字节32bit。现在一个整数一个bit。用来排序的

百度百科例子： 假设我们要对0-7内的5个元素(4,7,2,5,3)排序
（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。
要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte的空间，
将这些空间的所有Bit位都置为0。
然后遍历这5个元素，首先第一个元素是4，
那么就把4对应的位置为1（可以这样操作 p+(i/8)|(0×01<<(i%8))
当然了这里的操作涉及到Big-ending和Little-ending的情况，
这里默认为Big-ending）,因为是从零开始的，所以要把第五位置为1。
然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，
一直到最后处理完所有的元素，将相应的位置为1。
然后我们现在遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），
这样就达到了排序的目的。实就是把计数排序用的统计数组的每个单位缩小成bit级别的布尔数组

缺点不足： 无法对重复的数据进行排序和查找

map映射表： 重点是把十进制转换成二进制bit,所以需要一个映射表，创建一个数组，
数组的每一位代表4byte 32bit。能够表示32个整数。

位移转换：index_loc = N / 32即可，index_loc即为n对应的数组下标。
例如n = 76, 则loc = 76 / 32 = 2,因此76在a[2]中。
求十进制数0-N对应的bit位(数组中的位移) bit_loc = N % 32即可，
例如 n = 76, bit_loc = 76 % 32 = 12