算法之基本排序

基本排序算法比较

基本排序算法	平均时间复杂度	最好时间复杂度	最差时间复杂度	空间复杂度	稳定排序否	原地排序否	优点	缺点
冒泡排序	O(n^2)	O(n)*	O(n^2)	O(1)	是	是	-	-
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	否	是	-	-
插入排序	O(n^2)	O(n)	O(n^2)	O(1)	是	是	-	-
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)*	是	否	稳定	需额外空间
快速排序	O(nlogn)	O(nlogn)	O(n^2)*	O(1)	否	是	不需要额外空间	不稳定*
桶排序	O(n)	O(n)	O(n)	O(n)	否	否	时间复杂度低	对数据范围和分布要求极严格
计数排序	O(n)	O(n)	O(n)	O(n)	可是可不是*	否	时间复杂度低	对数据范围要求极严格
基数排序	O(n)	O(n)	O(n)	O(n)	是	否	时间复杂度低	对数据范围要求严格

说几点：

1. 排序的本质是什么？将逆序对变成正序对 --- 衍生出一道题：求一个数组的逆序对？
2. 平均时间复杂度：是所有不同逆序对组合排序时间复杂度的平均值，从0对到n*(n-1)/2;
   最好时间复杂度：当数组有序时的时间复杂度
   最坏时间复杂度：当数组逆序或者每次都得不到理想的结果
3. 稳定排序判断：排序过程中是否能保证相同元素的前后位置保持不变；
   这个指标对于基本类型数组排序没有区别；
   但是对于对象数组是有区别的，因为对象数组排序可能会根据多个字段维度排序：先根据字段1排序再根据字段2排序，如果根据字段2排序是不稳定的，则相同字段2的值元素之前根据字段1排的序就白费了
   比如：淘宝订单先根据下单时间字段排序，然后根据下单金额排序，排序完之后我们希望相同金额的单内部是按时间排序的，则按下单金额排序就必须采用稳定排序了；
   所以，根据不同场景决定是否采用稳定排序。
4. 每个排序算法说一下注意点：

• 冒泡排序：可以优化外层循环次数，当没有再进行swap时，则不用再继续了
• 归并排序：当数组较大的时候，消耗的空间为O(n)，可能就不大适合；还有一点，你可能发现了每次一分为二的时候都会new一个数组，空间复杂度不应该是O(nlogn)吗？空间复杂度不是这么算法的，空间复杂度是只某一时间占用额外内存的最大值，这里是单线程，每次new完一个数组使用之后会销毁掉，所以最多占用O(n)的空间
• 快排最差时间复杂度为O(n^2)出现的场景：每次partition后都是一分为1和n-1
• 计数排序：可稳定可不稳定，可以有两种写法，见后面的代码部分。
• 具体选择哪个排序算法，要看排序数字的大小，分布规律，是否要求稳定排序等因素。

5. 扩展题

• 求一个数组的逆序对
  归并过程中求解
• O(n)时间复杂度求数组第k大的元素
  快排算法思想+减治法
• 10个接口访问10个日志文件，每个日志文件大小300M且都是按照时间排序的，将其合并成一个文件，但是限制内存大小只有1G，问怎么搞？
  归并算法的merge过程，可以先假定只有两个1G的日志文件怎么搞
• D，a，F，B，c，A，z，b,只有大小写字母，排序将小写字母全部放在大写字母后面，小写字母或者大写字母之间不要求有序? 再问只有大小写字母和数字，将小写字母放左边，数字放中间，大写字母放右边，内部不要求有序，怎么搞？
  外部排序首选：桶排序

各种排序算法实现和优化

1. 冒泡排序

/**
 * 描述：冒泡排序
 *
 * @author xuery
 * @date 2018/11/20
 */
public class BubbleSort {

    private static final int ARR_SIZE = 10;

    public static void main(String[] args) {
        int[] arr = ArrayUtil.generateArray(ARR_SIZE, 50);
        optimizeBubbleSort(arr);
        ArrayUtil.printArray(arr);
    }
    
    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //注意这里不能大于等于，有等于则是非稳定排序
                if(arr[j] > arr[j+1]){
                    ArrayUtil.swap(arr, j ,j+1);
                }
            }
        }
    }

    public static void optimizeBubbleSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        for (int i = 0; i < arr.length - 1; i++) {
            boolean continueFlag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //注意这里不能大于等于，有等于则是非稳定排序
                //优化，如果当前内层循环一次都没有进入到swap则说明已经有序了，不需要往下进行了
                if(arr[j] > arr[j+1]){
                    ArrayUtil.swap(arr, j ,j+1);
                    continueFlag = true;
                }
            }
            if (!continueFlag){
                break;
            }
        }
    }

}

2. 选择排序

/**
 * 描述：选择排序
 *
 * @author xuery
 * @date 2018/11/20
 */
public class SelectSort {

    private static final int ARR_SIZE = 10;

    public static void main(String[] args) {
        int[] arr = ArrayUtil.generateArray(ARR_SIZE, 50);
        selectSort(arr);
        ArrayUtil.printArray(arr);
    }

    public static void selectSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                ArrayUtil.swap(arr, i, minIndex);
            }
        }
    }
}

3. 插入排序

/**
 * 描述：插入排序
 *
 * @author xuery
 * @date 2018/11/20
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = ArrayUtil.generateArray(10, 50);
        insertSort(arr);
        ArrayUtil.printArray(arr);
    }

    public static void insertSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        for (int i = 1; i < arr.length; i++) {
            //从下表i-1遍历到0找到arr[i]插入的位置
            int insertIndex = 0;
            int arri = arr[i];
            for (int j = i - 1; j >= 0; j--) {
                //注意，这里也不能取等号，否则就是不稳定排序了
                if(arr[j] > arri){
                    arr[j+1] = arr[j];
                } else {
                    insertIndex = j+1;
                    break;
                }
            }
            arr[insertIndex] = arri;
        }
    }
}

4. 归并排序

/**
 * 描述：归并排序及非递归实现
 *
 * @author xuery
 * @date 2018/11/20
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = ArrayUtil.generateArray(7, 50);
        MergeSort mergeSort = new MergeSort();
        ArrayUtil.printArray(arr);
        mergeSort.notRecursionMergeSort(arr);
        ArrayUtil.printArray(arr);
    }

    public void mergeSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        recursionMergeSort(arr, 0, arr.length - 1);
    }

    public void recursionMergeSort(int[] arr, int begin, int end) {
        if (begin >= end) {
            return;
        }
        int mid = begin + (end - begin) / 2;
        //divide into two parts
        recursionMergeSort(arr, begin, mid);
        recursionMergeSort(arr, mid + 1, end);
        //merge
        int[] temp = new int[end - begin + 1];
        int i = begin, j = mid + 1, index = 0;
        while (i <= mid && j <= end) {
            //这里需要有等号，保证稳定性
            if (arr[i] <= arr[j]) {
                temp[index++] = arr[i++];
            } else {
                temp[index++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[index++] = arr[i++];
        }
        while (j <= end) {
            temp[index++] = arr[j++];
        }
        //将temp复制会arr对应的位置
        for (int k = 0; k < end - begin + 1; k++) {
            arr[k + begin] = temp[k];
        }
    }

    /**
     * 非递归实现归并排序
     * 思路很简单：就是没有递，只有归，先1+1合并，再2+2合并，最后n/2+n/2合并
     * 如何编写代码：自己举例，确定两两合并的边界，边界一旦确定直接采用之前的merge就可以了
     * 注意点：两两个数不一定相同，要注意越界条件等的判断
     *
     * bug:一定要注意对某些变量操作完之后，它已经不代表最初的值了，想要最初的值就不能对变量操作或者新建一个变量保存最初的值
     * @param arr
     */
    public void notRecursionMergeSort(int[] arr) {

        //step表示step个元素+step个元素合并
        int step = 1;
        while (step < arr.length) {
            for (int i = 0; i < arr.length; i = i + 2 * step) {
                //i--i+step-1合并，i+step--i+2*step-1合并，都包括边界，注意越界条件判断
                //i+step>=arr.length时右边一半没有，结束本step合并
                if (i + step >= arr.length) {
                    break;
                }
                //可以开始合并
                int mid = i + step - 1, right = Math.min(i + 2 * step - 1, arr.length - 1);
                int[] temp = new int[right - i + 1];
                int leftIndex = i, rightIndex = mid + 1, index = 0;
                while (leftIndex <= mid && rightIndex <= right) {
                    if (arr[leftIndex] <= arr[rightIndex]) {
                        temp[index++] = arr[leftIndex++];
                    } else {
                        temp[index++] = arr[rightIndex++];
                    }
                }
                while (leftIndex <= mid) {
                    temp[index++] = arr[leftIndex++];
                }
                while (rightIndex <= right) {
                    temp[index++] = arr[rightIndex++];
                }
                for (int k = 0; k < right - i + 1; k++) {
                    arr[k + i] = temp[k];
                }
            }
            step = step * 2;
        }
    }
}

5. 快速排序

/**
 * 描述：快排填坑法再搞一遍
 * 非稳定排序，相同值可能由于partition导致顺序改变
 *
 * @author xuery
 * @date 2018/11/20
 */
public class QuickSort2 {

    private static final Random random = new Random();

    public static void main(String[] args) {
        int[] arr = ArrayUtil.generateArray(10, 20);
        ArrayUtil.printArray(arr);
        quickSort(arr);
        ArrayUtil.printArray(arr);
    }

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int begin, int end) {
        if (begin >= end) {
            return;
        }

        int partition = partition(arr, begin, end);

        //divide into three parts including [begin,partition-1],partition,[partition+1,end]
        quickSort(arr, begin, partition - 1);
        quickSort(arr, partition + 1, end);
    }

    //挖坑：第一个坑是基准所在的位置，最后一个坑填基准值，填坑条件：与基准值比较，每次循环填两个坑，一左一右
    public static int partition(int[] arr, int begin, int end) {
        //随机取其中的一个值作为基准并与最后一个值交换
        int pIndex = begin + random.nextInt(end - begin + 1);
        if (pIndex != end) {
            ArrayUtil.swap(arr, pIndex, end);
        }
        int pivot = arr[end];
        int i = begin, j = end;
        while (i < j) {
            //从左往右找第一个大于pivot的
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }

            //从右往左找第一个小于pivot的
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
        }
        arr[i] = pivot;
        return i;
    }
}

6. 计数排序

/**
 * 描述：计数排序
 * <p>
 * 算法描述：如其名，遍历数组，数组中的值对应计数数组的下标，将对应计数数组下标对应的值+1操作；之后再遍历计数数组即可完成排序
 * <p>
 * 要求数组中元素的值分布在某个比较小的范围内
 * <p>
 * 可以是不稳定排序或者稳定排序
 *
 * @author xuery
 * @date 2018/11/20
 */
public class CountSort {

    public static void main(String[] args) {
        int[] arr = ArrayUtil.generateArray(10, 20);
        ArrayUtil.printArray(arr);
        stableCountSort(arr);
        ArrayUtil.printArray(arr);
    }

    /**
     * 不稳定的计数排序，无法保证相同数值保证顺序不变，因为是采用从头到尾直接遍历计数数组的方式
     * <p>
     * 假设只有非负整数
     *
     * @param arr
     */
    public static void notStableCountSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        //find max value
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (maxValue < arr[i]) {
                maxValue = arr[i];
            }
        }
        //new a counting arr to count now
        int[] countArr = new int[maxValue + 1];
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;
        }

        int index = 0;
        for (int i = 0; i < countArr.length; i++) {
            while (countArr[i]-- > 0) {
                arr[index++] = i;
            }
        }
    }

    /**
     * 上面的方式是不稳定排序，可以采用比较巧妙的方法改写成稳定排序
     * <p>
     * 从头遍历countArr数组，将之前的数值累加到当前位置并放入countSumArr数组中，这样countSumArr[i]就表示当前小于等于i的数值个数为countSumArr[i]
     * 然后从尾部开始遍历countArr, 比如遍历到countArr[i],根据对应的countSumArr[i]的值就知道应该把i放回原数组arr的哪个位置，
     * 并将countArr[i]和countSumArr[i]分别减一, 对于countArr重复该操作，直至countArr[i]变为0
     * 这样可以巧妙的保证相同数值的元素顺序保持不变
     *
     * @param arr
     */
    public static void stableCountSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        //find max value
        int maxValue = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (maxValue < arr[i]) {
                maxValue = arr[i];
            }
        }
        //new a counting arr to count now
        int[] countArr = new int[maxValue + 1];
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i]]++;
        }

        //calcalate countSumArr just as explained
        int[] countSumArr = new int[maxValue + 1];
        countSumArr[0] = countArr[0];
        for (int i = 1; i < countArr.length; i++) {
            countSumArr[i] = countSumArr[i - 1] + countArr[i];
        }

        for (int i = countArr.length - 1; i >= 0; i--) {
            while(countArr[i]-- > 0){
                arr[--countSumArr[i]] = i;
            }
        }

    }
}