前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
使用插入排序和快速排序对整数数组进行排序计算

解决方案

插入排序（从小到大）：
从第二个节点开始：
1、找到前面节点中第一个比自己小的数，记录index
2、从当前节点开始，将前一个元素替换掉当前元素，直到替换到前一个元素是index的时候停止
3、将当前节点赋值给index的后一个元素上即可
时间：O(n^2) 空间O(1)
是否稳定排序：是
是否原地排序：是
快速排序：
1、找到第一个元素作为轴，两边开始中间遍历，比轴大的放轴右边，比轴小的放轴左边
2、结束后通过轴将数组分为两个子数组，分别继续递归即可
时间：O(nlogn ~ n^2)， 平均 nlogn 空间 O(logn)
是否稳定排序：是
是否原地排序：否

代码编写

java语言版本

插入排序：

    /**
     * 插入排序
     * @param arr
     * @return
     */
    public static int[] insertSortCP(int[] arr){
        if (arr == null || arr.length == 1){
            return arr;
        }
        for (int i = 1; i < arr.length; i++){
            // 查询i应该放在哪？
            int index = i;
            int value = arr[i];
            // 往前找到第一个小于index的坐标
            while (index >= 0 && arr[index] >= arr[i]){
                index--;
            }
            // index可能是-1
            index++;
            int temIndex = i;
            while (temIndex > index){
                arr[temIndex] = arr[temIndex-1];
                temIndex--;
            }
            arr[index] = value;
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {3, 4, 1, 5, 6, 8, 9};
        int[] ints = InsertSort(arr, (byte) 0);
        CommonUtils.printArr(ints);
    }

    /**
     * 插入排序（稳定版本）
     * @param arr
     * @return
     */
    public static int[] insertSortStable(int[] arr){
        if (arr == null || arr.length == 1){
            return arr;
        }
        for (int i = 1; i < arr.length; i++){
            // 查询i应该放在哪？
            int index = i;
            int value = arr[i];
            // 往前找到第一个小于index的坐标
            while (index-1 >= 0 && value < arr[index-1]){
                arr[index] = arr[index - 1];
                index--;
            }
            arr[index] = value;
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {3, 4, 1, 5, 2, 8, 6, 9};
        int[] ints = insertSortStable(arr);
        CommonUtils.printArr(ints);
    }

快速排序:

    /**
     * 快速排序（二轮） 非稳定排序，非原地排序
     * @param arr
     * @return
     */
    public static int[] quickSortCP(int[] arr){
        if (arr == null || arr.length == 1){
            return arr;
        }
        quickSortCP1(arr, 0, arr.length - 1);
        return arr;
    }

    private static void quickSortCP1(int[] arr, int left, int right) {
        if (left >= right){
            return;
        }
        int midIndex = getMidIndexForQuickSort(arr, left, right);
        quickSortCP1(arr, left, midIndex - 1);
        quickSortCP1(arr, midIndex+1, right);
    }

    private static int getMidIndexForQuickSort(int[] arr, int left, int right) {
        // 正常默认取第一个值
        int mid = arr[left];
        int leftIndex = left+1;
        int rightIndex = right;
        while (true){

            // 找到左边第一个大于等于mid的
            while (leftIndex <= rightIndex && arr[leftIndex] < mid){
                leftIndex++;
            }
            // 找到右边第一个小于mid的
            while (leftIndex <= rightIndex && arr[rightIndex] > mid){
                rightIndex--;
            }

            if (leftIndex > rightIndex){
                break;
            }
            CommonUtils.swap(arr, leftIndex, rightIndex);
            leftIndex++;
            rightIndex--;
        }
        CommonUtils.swap(arr, rightIndex, left);
        return rightIndex;
    }

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

快速排序在写的时候自己给的测试用例基本是有序的，所以发现，基本有序的时候总会有一边空循环一遍，所以最坏情况是O(n^2)，其实java中的TimSort方法，也就是Collection集合的默认排序，java认为业务中大多数的排序元素都是基本有序的或者部分有序的，所以，也针对这种现象做了一定的merge优化。
插入排序其实我写的版本是一种不稳定的版本，不知道大家有没有发现，其实 while (index >= 0 && arr[index] >= arr[i]){这里相等情况，index还是会移动，所以前面相等的元素会被移动到当前元素的后面导致不稳定，所以插排有稳定的版本，提供给大家。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！