java list 二次排序_五种经典排序算法

一、概述

在算法面试题中，排序算法经常被问到，因为涉及排序的业务场景很多，如员工的薪资列表，VIP积分榜，游戏里面玩家战力榜等等。另外排序算法的种类多，效率参差不齐。好的排序算法复杂度能达到 O(logN)，而差的算法会拖垮整个服务器，通过排序算法的设计便能直接看出面试者算法能力的高低。今天我们就来分享一下五种经典的排序算法，分别是： 冒泡排序、插入排序、选择排序、希尔排序、快速排序。

---

二、五种经典算法

第一种排序：冒泡排序，也就是我们刚刚学习Java时认识到的第一个排序算法，其排序的逻辑是：从第一个元素开始将该元素和其他元素对比一遍，逆序则交换位置，接着再将第二个元素进行同样的操作，以此类推。下面我们直接上代码

    /**     * 冒泡排序     */    public static super T>>         int length = t.length;        T temp;        for (int i = 0; i < length - 1; i++)            for (int j = length - 1; j > i; j--)                if (t[i].compareTo(t[j]) > 0) {
                        temp = t[i];                    t[i] = t[j];                    t[j] = temp;                }    }

代码如上所示，编写很简单，设计思想也不复杂，但是我们并不推荐用这种排序算法，因为其效率实在太低，复杂度为O(N^2)，数据量一大的情况下会直接拖死服务器。

第二种排序算法：插入排序，它排序的思想是“两两对比”，比如：在一个无序的数组里面，将第n个元素和第n+1个元素对比，如果是顺序，则位置不动，继续下一个元素的判断(n+1和n+2的对比)，如果是逆序则n+1开始回溯往前比，找出n+1不再逆序的位置，此为1次对比。数组有a个元素，则要比较a-1次。下面附上代码

    /**     * 插入排序     */    public static > void insertionSort(T[] t) {
            int j;        int length = t.length;        for (int i = 1; i < length; i++) {
                T tmp = t[i];            for (j = i; j > 0 && tmp.compareTo(t[j - 1]) < 0; j--)                t[j] = t[j - 1];            t[j] = tmp;        }    }

以上是插入排序的代码，插入排序的复杂度和冒泡排序的复杂度是一样的，都是O(N^2)