1 插入排序
2 希尔排序
3 选择排序
4 堆排序
5 冒泡排序
6 快速排序
7 归并排序

1 插入排序

思路：

(1) 将数组划分为 “ 已排序区间 ” 和 “ 待排序区间 ”，用 bound 来标识这两个区间，bound 为待排序区间的第一个位置；
(2) 将待排区间的第一个元素（即bound 标记位置的元素），与已排区间的元素进行比较。

public static void insertSort(int[] arr) {
        // 划分“已排区间” 和 “待排区间”
        int bound = 1;
        // 用于控制边界值向后走
        // 即，待排区间往后缩小
        for (; bound < arr.length; bound ++) {
            int v = arr[bound];
            // 待排区间的前一个元素
            int cur = bound - 1;
            // 已排区间从后往前遍历
            // 寻找合适的位置插入 arr[bound]
            for (; cur >= 0; cur --) {
                if (arr[cur] > v) {
                // 元素向后移动一位
                   arr[cur + 1] = arr[cur];
                } else {
                    break;
                }
            }
            // 找到合适位置，插入
            arr[cur + 1] = v;
        }
    }

时间复杂度：O( N² )
空间复杂度：O(1)
稳定排序

2 希尔排序

思路：
规定一个间隔（间隔希尔序列，length / 2，length / 4,length / 8 … 1），将数组分成几个组，对每一组分别进行排序，然后调整分组变化，逐渐使数组变得有序。可以构建两个方法，第一个方法构建分组系数，第二个方法以前的 gap 为依据，进行分组插排。
希尔排序是插入排序的升级版本，因此它的代码实现和思想与插入排序很类似。

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

public static void _shellSort(int[] arr,int gap) {
    int bound = gap;
    for (; bound < arr.length ; bound++) {
        int v = arr[bound];
        int cur = bound - gap;
        for (; cur >= 0 ; cur = cur - gap) {
            if (arr[cur] > v) {
                arr[cur + gap] = arr[cur];
            } else {
                break;
            }
        }
        arr[cur + gap] = v;
    }
}

时间复杂度：O(N²) => O(N^1.3)
空间复杂度：O(1)
不稳定排序

3 选择排序

(1) 将数组分为两个区间，待排区间和已排区间，但注意，这里与插入排序不同的是，插入排序 bound 可以是任意一个元素，而选择排序的 bound 必须从 0 开始。因为选择排序在后续进行选择时，会选出最小值放到已排区间的最后，如果一开始随意选择，后续的元素不一定都比这个元素大，要确保第一个选择的元素是数组最小的元素；

(2) 遍历待排区间，通过打擂台的方式找出最小元素，以待排区间的第一个位置作为擂台。

public static void selectOrder(int[] arr) {
    int bound = 0;
    for (;bound < arr.length; bound ++) {
        for (int cur = bound + 1; cur < arr.length; cur++) {
            if (arr[cur] < arr[bound]) {
                swap(arr,cur,bound);
            }
        }
    }
}

public static void swap (int[] arr,int cur,int bound) {
    int tmp = arr[cur];
    arr[bound] = arr[cur];
    arr[cur] = tmp;
}

时间复杂度：O(N²)
空间复杂度：O(1)
不稳定排序

4 堆排序

(1) 用当前数组创建一个大堆；
(2) 删除堆顶元素，即将堆顶的元素和最后的元素进行交换，然后从堆中删除最后一个元素，注意并非从数组中删除，最大值就被放在了数组最后；
(3) 从 0 号元素进行向下调整，使其重新成为堆；
(4) 再把堆的第一个元素和最后一个元素进行交换，此时的最后一个元素是数组的倒数第二个元素，就把第二大的数放在了数组的倒数第二个位置，以此类推，不断循环。

public static void heapSort(int[] arr) {
    createHeap(arr);
    int heapSize = arr.length;
    for (int i = 0; i < arr.length; i++) {
        // 交换堆上的 第一个和最后一个元素
        // 注意堆的最后一个元素并不是每次都是数组的最后一个元素
        swap(arr,0,heapSize - 1);
        // 删除堆的最后一个元素，但是它还存在在数组中
        heapSize --;
        // 只用调整一次，因为其本身已经是堆，只是交换后的第一个元素需要调整
        shiftDown(arr,heapSize,0);
    }
}

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

public static void shiftDown(int[] arr,int size,int index) {
    int parent = index;
    int child = 2 * parent + 1;
    while (child < size) {
        if (child + 1 < size && arr[child + 1] > arr[child]) {
            child = child + 1;
        }
        if (arr[child] > arr[parent]) {
            swap(arr,child,parent);
        }
        parent = child;
        child = 2 * parent + 1;
    }
}

时间复杂度：O( Nlog^N)
空间复杂度：O(1)
不稳定排序

5 冒泡排序

思路：
比较两个相邻的元素，不符合升序，就交换，如果从后往前遍历，则一趟遍历之后，最大值来到最后；如果从前往后遍历，则一趟遍历之后，最小值来到最后。

public static void bubbleSort(int[] arr) {
    for (int bound = 0; bound < arr.length; bound++) {
        for (int cur = arr.length - 1; cur > bound ; cur--) {
            if (arr[cur - 1] > arr[cur]) {
                swap(arr,cur - 1,cur);
            }
        }
    }
}

时间复杂度：O(N²)
空间复杂度：O(1)
稳定排序

6 快速排序

思路：
(1) 在待排数组中选取一个 “基准值”，然后把这个数组整理为：左侧都比基准值小，右侧都比基准值大；
(2) 使用左右下标从两边往中间遍历。

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

public static void _quickSort(int[] arr,int left,int right) {
    if (left >= right) {
        return;
    }
    // index 表示基准值所在的位置
    int index = partition(arr,left,right);
    _quickSort(arr,left,index - 1);
    _quickSort(arr,index + 1,right);
}

public static int partition(int[] arr,int left,int right) {
    // v 用来存放基准值
    int v = arr[right];
    int l = left;
    int r = right;
    while (l < r) {
        // 找到大于基准值的元素的位置
        while (l < r && arr[l] <= v) {
            l ++;
        }
        // 找到小于基准值的元素的位置
        while (l < r && arr[r] >= v) {
            r --;
        }
        // 交换两个位置的元素
        swap(arr,l,r);
    }
    // 当 l == r 时，循环进不去
    // 交换 l位置 和 right位置的元素，right 为基准值的位置
    swap(arr,l,right);
    return l;
}

时间复杂度：O( NlogN) 最坏为 O(N)
空间复杂度：O(logN)最坏为 O(N) 取决于递归的深度
不稳定排序

快速排序的优化手段：
1、三数取中：即，取三个数，数组的第一个数、最后一个数和中间的数，哪个是中间的数就取哪个；
2、当待处理区间已经比较小的时候，就不继续递归了，直接针对该区间进行插入排序；
3、当递归深度达到一定深度，并且当前待处理区间还是比较大时，还可以使用堆排序

非递归快速排序：

    public static void quickSortByLoop(int[] arr) {
        // 1、创建一个栈用来保存当前的每一个待处理区间
        Stack<Integer> stack = new Stack<>();
        // 2、把根节点入栈，整个数组对应的区间
        stack.push(0);
        stack.push(arr.length - 1);
        // 3、循环取栈顶元素
        while (!stack.isEmpty()) {
            // 取的元素就是当前的待处理区间
            int right = stack.pop();
            int left = stack.pop();
            if (left >= right) {
                // 如果是空区间或只有一个元素，不需要排序
                continue;
            }
            // 调用partition 方法整理当前区间
            int index = partition(arr,left,right);
            // 右侧区间：[index + 1,right]
            stack.push(index + 1);
            stack.push(right);
            // 左侧区间：[left,index - 1]
            stack.push(left);
            stack.push(index - 1);
        }

7 归并排序

思路：
核心操作就是将两个有序数组合并。若数组无序，就将其划分成两部分，直到划分为一个元素，必然有序。

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

    public static void _mergeSort(int[] arr,int left,int right) {
        if (right - left <= 1) {
            // 判定当前区间是不是只有一个元素或者没有元素
            // 此时不需要进行排序
            return ;
        }
        int mid = (left + right) / 2;
        // 先让 [left, right) 区间变成有序
        _mergeSort(arr,left,mid);
        // 再让 [mid,right) 区间变成有序
        _mergeSort(arr,mid,right);
        // 合并两个有序区间
        merge(arr,left,mid,right);
    }

    // 归并中的关键操作，就是归并两个有序数组
    // 使用该方法完成数组归并的过程
    // 此处两个数组就通过参数的 left,mid,right 描述
    // [left, mid) 左侧数组
    // [mid,right) 右侧数组
    public static void merge(int[] arr,int left,int mid,int right) {
        // 创建一个临时空间来保存归并的结果
        // 临时空间得能保存的下待归并的两个数组
        // right - left这么长
        int[] tmp = new int[right - left];
        // 这个下标表示当前元素放到临时空间的哪个位置
        int tmpIndex = 0;
        int cur1 = left;
        int cur2 = mid;
        while (cur1 < mid && cur2 < right) {
            if(arr[cur1] <= arr[cur2]) {
                tmp[tmpIndex] = arr[cur1];
                tmpIndex ++;
                cur1 ++;
            } else {
                tmp[tmpIndex] = arr[cur2];
                tmpIndex ++;
                cur2 ++;
            }
        }
        // 循环结束后，需要把剩余元素也都拷贝到最终结果里
        while (cur1 < mid) {
            tmp[tmpIndex] = arr[cur1];
            tmpIndex ++;
            cur1 ++;
        }
        while (cur2 < right) {
            tmp[tmpIndex] = arr[cur2];
            tmpIndex ++;
            cur2 ++;
        }
        // h还需要把 tmp 的结果再放回 arr 数组 （原地排序）
        for (int i = 0; i < tmp.length; i++) {
//            arr[left] = tmp[i];
//            left ++;
            arr[left + i] = tmp[i];
        }
    }

实践复杂度：O(logN)
空间复杂度：O(N)
稳定排序

非递归归并排序:

public static void mergeSortByLoop(int[] arr) {
    // 控制每个分组的长度，每个待归并数组的长度
    int gap = 1;
    for(;gap < arr.length;gap *= 2) {
        for (int i = 0; i < arr.length; i += 2*gap) {
            // 控制两个相邻数组归并
            int left = i;
            int mid = i + gap;
            if (mid > arr.length) {
                mid = arr.length;
            }
            int right = i + 2 * gap;
            if (right > arr.length) {
                right = arr.length;
            }
            merge(arr,left,mid,right);
        }
    }
}