排序算法（三）

前言

上篇文章排序算法（二）我们介绍了10种排序算法，今天我们再来介绍一些其他的排序算法。

正文

今天我们介绍7种排序算法，它们如下：

Sort Name	Time(Best)	Time(Average)	Time(Worst)	Memory	Stable
BinaryTreeSort	O(n)	O(n * log n)	O(n * log n)	O(n)	Yes
FlashSort	O(n)	O(n+k)	O(n^2)	O(n+k)	Yes
PatienceSort	O(n)	O(n * log n)	O(n * log n)	O(n)	No
StoogeSort	——	——	O(n^(log 3 / log 1.5))	O(n)	Yes
PancakeSort	O(n)	O(n^2)	O(n^2)	O(n)	No
InPlaceMergeSort	——	——	O(n * (log n)^2)	O(1)	Yes
StrandSort	O(n)	O(n^2)	O(n^2)	O(n)	Yes

我们分别来看下。

二叉排序树排序（BinaryTreeSort）

简介及原理

二叉排序树排序（BinaryTreeSort），其原理是利用二叉树的特性，较小值依次比较放在树的左边，较大值依次比较放在树的右边，形成一个数据二叉树，然后将数据从左到右遍历出来即可。

算法描述

1. 对于待排序数组array，构建一个二叉树tree，根节点可以取array[0]，此时根节点的左右叶子节点为null；
2. 对数组里每个元素，放入二叉树tree，如果小于根节点数值，应该放到左边，左边如果没有节点就创建一个并放入，如果有则需要比较其节点值和放入值大小，进而确定要放置的位置；右边同理；
3. 进而我们会得到一个二叉树，我们从左向右遍历二叉树，就可以得到有序的数组。

动图演示

代码实现

相关代码如下：

public class BinaryTreeSort {
    public static int[] binaryTreeSort(int[] array){
        BinaryNode root = new BinaryNode(array[0], null, null);
        for(int i=1; i<array.length; i++){
            root.addChild(array[i]);
        }
        List<Integer> list = BinaryNode.getSortedList(root);
        int[] result = new int[list.size()];
        for (int i=0;i<list.size();i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] a = new int[100];
        Random r = new Random();
        for (int i=0;i<a.length;i++){
            a[i] = r.nextInt(10000);
        }
        System.out.println("BinaryTreeSort排序前：");
        System.out.println(Arrays.toString(a));
        int [] s = binaryTreeSort(a);
        System.out.println("BinaryTreeSort排序后：");
        System.out.println(Arrays.toString(s));
    }
}
/**
 * 二叉树节点类
 */
class BinaryNode{
    /**
     * 节点当前值
     */
    private int value;
    /**
     * 左节点
     */
    private BinaryNode lChild;
    /**
     * 右节点
     */
    private BinaryNode rChild;
    /**
     * 排序结果集
     */
    private static List<Integer> resultList = new ArrayList<>();

    public BinaryNode(int value, BinaryNode l, BinaryNode r){
        this.value = value;
        this.lChild = l;
        this.rChild = r;
    }
    public BinaryNode getLChild() {
        return lChild;
    }
    public BinaryNode getRChild() {
        return rChild;
    }
    public int getValue() {
        return value;
    }

    public static List<Integer> getSortedList(BinaryNode root) {
        iterate(root);
        return resultList;
    }
    /**
     * 添加一个节点
     * **/
    public void addChild(int n){
        if(n < value){
            if(lChild!=null){
                lChild.addChild(n);
            }else{
                lChild = new BinaryNode(n, null, null);
            }
        }else{
            if(rChild!=null){
                rChild.addChild(n);
            }else{
                rChild = new BinaryNode(n, null, null);
            }
        }
    }
    /**
     * 迭代赋值
     * @param root
     */
    public static void iterate(BinaryNode root){
        if(root.lChild!=null){
            iterate(root.getLChild());
        }
        resultList.add(root.getValue());
        if(root.rChild!=null){
            iterate(root.getRChild());
        }
    }
}

其他注意事项

• 这儿是否可以使用平衡二叉树？

  可以，但平衡二叉树可以提高单个数据查找性能，我们这儿需要处理全部数据，同时平衡二叉树插入时涉及到树的旋转变化等，因此使用平衡二叉树的效率不一定比普通二叉树效率高。

  某些情况下，使用平衡二叉树递归取值的栈深度会比普通二叉树要低。

• 该排序算法的时间复杂度：

  时间复杂度（最好）：O(n)

  时间复杂度（平均）：O(n * log n)

  时间复杂度（最差）：O(n * log n)

• 该排序算法空间复杂度：O(n)

• 该排序算法是稳定排序算法。

闪电排序（FlashSort）

简介及原理

闪电排序（FlashSort）是由Karl-Dietrich Neubert在1997年发展而来的一种排序算法，并且在欧洲理论计算机协会的新闻简报上发表了该算法。

该算法类似于桶排序，主要改进了对使用桶的预测。

我们知道，对于桶排序，我们首先要确定桶的数量，不能太多或者太少。

太多的话，桶中元素少，或者无用桶多，会浪费内存；太少的话，桶中元素多，每个桶中这些元素进行由大到小（或者由小到大）排序时就会比较耗时。（可参考HashMap理解桶排序）

因此桶的数量对排序性能的影响也不能忽视，FlashSort就是可以提前预知桶的大致数量及元素在桶中的位置，使其元素尽量利用每个桶，然后进行排序的。

FlashSort是如何预测的呢？

我们知道，桶排序桶的数量bucketCount一般为 INT[(Amax - Amin)/Asize] +1，对于如下数组[1,152,1000,8763,3,88,1000001,666,9999,100]，根据公式可以算出需要的桶的数量为(1000001-1)/10 +1 = 1000001。

显然浪费了大量桶（内存），当然bucketCount也可以设置为数组长度，但是如果有一个长度为100000的数组，数组元素只有[0-9]之间的元素，我们显然设置的bucketCount也会不合适。

你一定会说可以取 INT[(Amax - Amin)/Asize] +1 或者数组长度中的最小值啊，哈哈，当然这么想也正确，但是即使这样，桶排序也不一定会完全把所有的桶充分利用，也会出现空桶的情况，因而造成内存浪费。

FlashSort就可以充分利用桶吗？ 是的，其数据的位置主要依赖一个公式，如下：

K(Ai) = 1 + INT[ (m-1)(Ai-Amin)/(Amax-Amin) ]

这个公式可以算出数组的Ai项在桶中的位置。

比如如下数组[6,2,4,1,5,9]，m如果取数组长度的话 m=6（也表明桶的数量为m个），我们可以算出：

• K(6) = 1 + 5 * 5/8 = 4
• K(2) = 1 + 5 * 1/8 = 1
• K(4) = 1 + 5 * 3/8 = 2
• K(1) = 1 + 5 * 0/8 = 1
• K(5) = 1 + 5 * 4/8 = 3
• K(9) = 1 + 5 * 8/8 = 6

可以看到极大的利用了桶，在数据量较多的情况下，与桶排序相比效果更明显。

可以看到上面我们m （桶的数量）取的数组长度，这显然不太合理，我们m一般取 0.1n (n代表数组长度)，当m<1 时，m=1。这样保证桶尽量少的浪费的前提下，尽可能减少桶的使用数量。

如果数组过大，m过小，会导致每个桶内数据多，排序浪费较多时间；如果数据少，但桶较多，会导致内存浪费。所以对于具体数组，m也可以自己指定，以达到排序效率和空间的优化平衡。

算法描述

• 构建M个桶，M可以取0.1N （N数组长度）或者自定义；
• 根据FlashSort的K(Ai)计算公式，找到每个元素所在的桶，放入元素；
• 对于每个桶中的元素，如果元素个数大于等于2，需要进行内部排序；
• 从小到大（或者大到小）依次取出桶中元素，得到有序数组。

动图演示

代码实现

public class FlashSort {
    public static void flashSort(int[] array) {
        //桶排序
        partialFlashSort(array, array.length);
        //桶内元素使用插入排序
        insertionSort(array);
    }
    private static void partialFlashSort(int[] a, int n) {
        //m值，取0.1n，也可以自由指定
        int bucketSize = n / 10;
        if (bucketSize < 1) {
            bucketSize = 1;
        }
        //构建bucket
        int[] buckets = new int[bucketSize];
        int i, j, k;
        int min = a[0];
        int maxIndex = 0;

        //找到最大最小值
        for (i = 1; i < n; i++) {
            if (a[i] < min) {
                min = a[i];
            }
            if (a[i] > a[maxIndex]) {
                maxIndex = i;
            }
        }
        if (min == a[maxIndex]) {
            return;
        }
        //计算系数
        double c1 = ((double) bucketSize - 1) / (a[maxIndex] - min);
        //计算元素位置
        for (i = 0; i < n; i++) {
            k = (int) (c1 * (a[i] - min));
            buckets[k]++;
        }
        for (k = 1; k < bucketSize; k++) {
            buckets[k] += buckets[k - 1];
        }
        //元素入桶
        int hold = a[maxIndex];
        a[maxIndex] = a[0];
        a[0] = hold;

        int nmove = 0;
        int flash;
        j = 0;
        k = bucketSize - 1;

        while (nmove < n - 1) {
            while (j > (buckets[k] - 1)) {
                j++;
                k = (int) (c1 * (a[j] - min));
            }
            flash = a[j];
            while (j != buckets[k]) {
                k = (int) (c1 * (flash - min));
                hold = a[buckets[k] - 1];
                a[buckets[k] - 1] = flash;
                flash = hold;
                buckets[k]--;
                nmove++;
            }
        }
    }
    private static void insertionSort(int[] a) {
        int i, j, hold;
        for (i = a.length - 3; i >= 0; i--) {
            if (a[i + 1] < a[i]) {
                hold = a[i];
                j = i;
                while (a[j + 1] < hold) {
                    a[j] = a[j + 1];
                    j++;
                }
                a[j] = hold;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[100];
        Random r = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = r.nextInt(10000);
        }
        System.out.println("FlashSort排序前：");
        System.out.println(Arrays.toString(a));
        flashSort(a);
        System.out.println("FlashSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 可以看到FlashSort只是优化了桶排序的元素存放桶的位置，使其尽量均匀分布于每个桶，而且选择合适的m值（桶数量）也是至关重要的（无论FlashSort或者桶排序）；

• 该算法时间复杂度：

  • 时间复杂度（最好）：O(n)
  • 时间复杂度（平均）：O(n+k)
  • 时间复杂度（最差）：O(n^2)

• 该算法空间复杂度：O(n+k)

• 该算法为稳定排序算法。

耐心排序（PatienceSort）

简介及原理

耐心排序（PatienceSort）是将数组的元素分类成很多堆再串接回数组的一种排序算法。受到纸牌游戏的启发和命名。

我们在Windows系统上一定玩过纸牌游戏吧，我们知道，无序的纸牌要变为有序，我们需要将无序的纸牌通过操作进行有序分堆，最后在将这些堆纸牌合并生成有序的结果。

我们后面的动图也会模拟纸牌来看下耐心排序的执行过程。

算法描述

1. 创建一个堆数组；
2. 比较当前指向的元素和每个堆的第一个元素；
3. 若当前元素比所有堆的第一个元素大，创建新的堆并加入到堆数组中；
4. 如果当前元素比堆内的第一个元素小，就放入该堆头部作为新的第一个元素；
5. 分类完后将每个堆有两种处理方式，可以通过合并后使用插入排序形成有序数列，也可以使用优先级队列依次取出元素完成排序。

PS：其实第4步，如果元素找到了多个符合条件的堆，可以放到任意一个堆里作为首元素。

动图演示

代码实现

这里的代码有两个，都比较好理解，第一个是将生成的堆合并，然后使用插入排序处理；第二个是生成堆后，使用优先级队列处理堆中数据。

大家都可以看下。

public class PatienceSort {
    public static void patienceSort(int[] theArray) {
        List<List<Integer>> newList = new ArrayList<>();
        for (int i = 0; i < theArray.length; i++) {
            List<Integer> bucketList = new ArrayList<>();
            //先开始创建一个堆
            if (i == 0) {
                bucketList.add(theArray[i]);
                newList.add(bucketList);
            } else {
                boolean isOk = false;
                for (int j = 0; j < newList.size(); j++) {
                    //如果当前元素比堆内的第一个元素小，就放入该堆头部作为新的第一个元素，然后执行下个元素判断
                    //这儿我们直接放到第一个符合的堆里了，其实放到其它符合的也是可以的，放到最后一个符合的堆里还可以解决子序列问题
                    if (theArray[i] < (int) ((List) newList.get(j)).get(0)) {
                        (newList.get(j)).add(0, theArray[i]);
                        isOk = true;
                        break;
                    }
                }
                //如果当前元素比所有堆内的第一个元素大，就创建个新堆，把元素作为第一个元素放进去
                if (!isOk) {
                    bucketList.add(theArray[i]);
                    newList.add(bucketList);
                }
            }
        }
        ////生成的堆合并，而后使用插入排序
        int q = 0;
        for (int m = 0; m < newList.size(); m++) {
            for (int n = 0; n < (newList.get(m)).size(); n++) {
                theArray[q] = (int) ((List) newList.get(m)).get(n);
                q++;
            }
        }
        //插入排序
        int tmp;
        int j;
        for (int i = 1; i < theArray.length; i++) {
            tmp = theArray[i];
            for (j = i - 1; j >= 0 && theArray[j] > tmp; j--) {
                theArray[j + 1] = theArray[j];
            }
            theArray[j + 1] = tmp;
        }
    }

    public static void main(String[] args) {
        int[] a = new int[200];
        Random r = new Random();
        for (int i=0;i<a.length;i++){
            a[i] = r.nextInt(10000);
        }
        System.out.println("PatienceSort排序前：");
        System.out.println(Arrays.toString(a));
        patienceSort(a);
        System.out.println("PatienceSort排序后：");
        System.out.println(Arrays.toString(a));
    }

    public static <E extends Comparable<? super E>> void patienceSort(E[] n) {
        List<Pile<E>> piles = new ArrayList<Pile<E>>();
        //生成堆
        for (E x : n) {
            Pile<E> newPile = new Pile<E>();
            newPile.push(x);
            int i = Collections.binarySearch(piles, newPile);
            if (i < 0){
                i = ~i;
            }
            if (i != piles.size()) {
                piles.get(i).push(x);
            }else {
                piles.add(newPile);
            }
        }
        //使用优先级队列处理数据
        PriorityQueue<Pile<E>> heap = new PriorityQueue<Pile<E>>(piles);
        for (int c = 0; c < n.length; c++) {
            Pile<E> smallPile = heap.poll();
            n[c] = smallPile.pop();
            if (!smallPile.isEmpty()) {
                heap.offer(smallPile);
            }
        }
        assert(heap.isEmpty());
    }
    private static class Pile<E extends Comparable<? super E>> extends Stack<E> implements Comparable<Pile<E>> {
        @Override
        public int compareTo(Pile<E> y) { return peek().compareTo(y.peek()); }
    }
}

其他注意事项

• 该算法有一个变体，可以有效地计算给定数据中的最长增长子列和最长递减子列。比如有个数组[7,8,2,3,5,8,6,4,3,1,5,9]，我们可以看到最长增长子列为[2,3,5,8]，最长递减子列为[8,6,4,3,1]

  我们使用耐心排序算法来看下：

  算法描述的PS部分：如果元素找到了多个符合条件的堆，可以放到任意一个堆里作为首元素，我们在这儿放到最后一个符合的堆中。

  • 根据耐心排序，我们可以把[7,8,2,3,5,8,6,4,3,1,5,9]数组按照上述算法分为如下堆数组： [3,7],[2,8],[5],[1,3,4,6,8],[5],[9]。显而易见最长递减子列为[1,3,4,6,8]的反向序列。
  • 我们对于上述所讲的算法，也可以反过来，即比较当前指向的元素和每个堆的第一个元素，如果当前元素大于该堆第一个元素，在进行放入操作，这样可以得到如下堆数组：[8,7],[8,5,3,2],[6],[4],[3],[9,5,1]。显而易见[8,5,3,2]是最长递增子列的反向序列。

• 该排序算法时间复杂度：

  • 时间复杂度（最好）：O(n)
  • 时间复杂度（平均）：O(n * log n)
  • 时间复杂度（最差）：O(n * log n)

• 该排序算法空间复杂度：O(n)

• 该排序算法为不稳定排序算法

臭皮匠排序（StoogeSort）

简介及原理

臭皮匠排序（StoogeSort）是一种低效的递归排序算法，是由Howard、Fine等教授提出的所谓“漂亮的”排序算法，代码很漂亮但是很耗时。

臭皮匠排序翻译的由来：因为这个排序和3有很大关系（3个臭皮匠）。

我们来看下算法描述：

算法描述

1. 如果最后一个值小于第一个值，则交换这两个数；
2. 如果当前集合元素数量大于等于3：
   1. 使用臭皮匠排序前2/3的元素；
   2. 使用臭皮匠排序后2/3的元素；
   3. 再次使用臭皮匠排序前2/3的元素。

动图演示

代码实现

public class StoogeSort {
    public static void stoogeSort(int[] array) {
        stoogeSort(array, 0, array.length - 1);
    }
    private static void stoogeSort(int[] array, int low, int high) {
        //如果第一个数大于最后一个数，交换位置
        if (array[low] > array[high]) {
            swap(array, low, high);
        }
        if (low + 1 >= high){
            return;
        }
        int third = (high - low + 1) / 3;
        //排序前2/3数组元素
        stoogeSort(array, low, high - third);
        //排序后2/3数组元素
        stoogeSort(array, low + third, high);
        //排序前2/3数组元素
        stoogeSort(array, low, high - third);
    }
    private static void swap(int[] a, int b, int c) {
        if (b == c){
            return;
        }
        int temp = a[b];
        a[b] = a[c];
        a[c] = temp;
    }

    public static void main(String[] args) {
        int[] a = new int[100];
        Random r = new Random();
        for (int i=0;i<a.length;i++){
            a[i] = r.nextInt(10000);
        }
        System.out.println("StoogeSort排序前：");
        System.out.println(Arrays.toString(a));
        stoogeSort(a);
        System.out.println("StoogeSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 该算法是一种低效的递归排序算法，甚至慢于冒泡排序，相比经典排序，臭皮匠排序性能十分差；

• 该算法的时间复杂度：

  时间复杂度（最差）：O(n^(log 3 / log 1.5))

• 该算法的空间复杂度：O(n)

• 该排序算法为稳定排序算法。

煎饼排序（PancakeSort）

简介及原理

煎饼排序（PancakeSort），我们对于排序数组，可以看成一叠大大小小的煎饼，假设我们有一把锅铲，可以每次从任意位置铲起上方全部煎饼并翻面，最终我们可以实现按煎饼大小进行排序的煎饼堆。

比如对于一个数组 [3,1,3,6,8,2,7,1]，我们把它看成煎饼堆，则我们使用“锅铲”翻转的过程如下：

1. [3,1,3,6,8,2,7,1] 初始化
2. [8,6,3,1,3,2,7,1] 先把“大煎饼”8翻转到上面
3. [1,7,2,3,1,3,6,8] 再把“大煎饼”8翻转到下面
4. [7,1,2,3,1,3,6,8] 再把“第二大煎饼”7翻转到上面
5. [6,3,1,3,2,1,7,8] 再把7翻转到下面
6. [1,2,3,1,3,6,7,8] 再把6翻转到下面
7. [3,2,1,1,3,6,7,8] 再把3翻转到上面
8. [1,1,2,3,3,6,7,8] 再把3翻转到下面，完成排序

算法描述

1. 对于待排序数组，找到最大值最小值及索引；
2. 将最大值翻转到顶部，在翻转到数组底部；
3. 此时再从未排序数组里找到最大值及索引，重复1、2过程。

动图演示

代码实现

public class PancakeSort {
    /**
     * 翻转
     * @param n
     * @param heap
     */
    private static void flip(int n, int[] heap) {
        for (int i = 0; i < (n + 1) / 2; ++i) {
            int tmp = heap[i];
            heap[i] = heap[n - i];
            heap[n - i] = tmp;
        }
    }
    /**
     * 获取最小最大值数组
     * @param n
     * @param heap
     * @return
     */
    private static int[] minmax(int n, int[] heap) {
        int xm, xM;
        xm = xM = heap[0];
        int posm = 0, posM = 0;
        for (int i = 1; i < n; ++i) {
            if (heap[i] < xm) {
                xm = heap[i];
                posm = i;
            } else if (heap[i] > xM) {
                xM = heap[i];
                posM = i;
            }
        }
        return new int[]{posm, posM};
    }
    private static void sort(int n, int dir, int[] heap) {
        if (n == 0) {
            return;
        }
        int[] mM = minmax(n, heap);
        int bestXPos = mM[dir];
        int altXPos = mM[1 - dir];
        boolean flipped = false;

        if (bestXPos == n - 1) {
            --n;
        } else if (bestXPos == 0) {
            flip(n - 1, heap);
            --n;
        } else if (altXPos == n - 1) {
            dir = 1 - dir;
            --n;
            flipped = true;
        } else {
            flip(bestXPos, heap);
        }
        sort(n, dir, heap);
        if (flipped) {
            flip(n, heap);
        }
    }
    public static void pancakeSort(int[] array) {
        sort(array.length, 1, array);
    }

    public static void main(String[] args) {
        int[] a = new int[100];
        Random r = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = r.nextInt(10000);
        }
        System.out.println("PancakeSort排序前：");
        System.out.println(Arrays.toString(a));
        pancakeSort(a);
        System.out.println("PancakeSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 煎饼排序的一个问题变种为焦煎饼排序，即对于我们的煎饼，每张煎饼都有一面是烤焦的，最终除了按照大小排序以外还要让所有焦面向下；

  焦煎饼问题： 比如对于上面的[3,1,3,6,8,2,7,1]数组，它们的右面都是“焦”的，我们按照上面的步骤走，会发现当执行到第4步得到[7,1,2,3,1,3,6,8]，其中[7,1][3,1,3,6,8]是焦面向下，[2]是焦面向上的，我们执行第5步把7翻转到底下时，7的焦面就向上了，就不符合要求了，因此这时候我们需要在单独翻转一次“煎饼”7，然后把[7,1,2,3,1,3,6]整个翻转一下。

  关于这部分的代码我就略过了，有兴趣的同学可以自己写一下。关于如何表示焦煎饼的正反两面也可以思考下。

• 煎饼排序的时间复杂度：

  • 时间复杂度（最好）：O(n)
  • 时间复杂度（平均）：O(n^2)
  • 时间复杂度（最差）：O(n^2)

• 该排序算法的空间复杂度：O(n)

• 该排序算法是一种不稳定排序算法。

原地归并排序（InPlaceMergeSort）

简介及原理

原地归并排序（InPlaceMergeSort）是归并排序（MergeSort）的一个变种。

我们知道，当使用归并排序时，我们需要借助辅助数组。原地归并排序可以使我们不使用辅助数组即可完成目标数组的排序。

算法描述

1. 将长度为n的数组分为两个n/2的子序列；
2. 对两个子序列分别进行归并排序；
3. 将两个排序好的子序列合并成一个最终的排序序列。

动图演示

代码实现

public class InPlaceMergeSort {
    public static void inPlaceMergeSort(int[] array) {
        inPlaceMergeSort(array, 0, array.length - 1);
    }
    private static void inPlaceMergeSort(int[] array, int first, int last) {
        int mid, lt, rt;
        int tmp;
        if (first >= last) {
            return;
        }
        mid = (first + last) / 2;
        inPlaceMergeSort(array, first, mid);
        inPlaceMergeSort(array, mid + 1, last);
        lt = first;
        rt = mid + 1;
        // One extra check:  can we SKIP the merge?
        if (array[mid] <= array[rt]) {
            return;
        }
        while (lt <= mid && rt <= last) {
            // Select from left:  no change, just advance lt
            if (array[lt] <= array[rt]) {
                lt++;
                // Select from right:  rotate [lt..rt] and correct
            } else {
                // Will move to [lt]
                tmp = array[rt];
                System.arraycopy(array, lt, array, lt + 1, rt - lt);
                array[lt] = tmp;
                // EVERYTHING has moved up by one
                lt++;
                mid++;
                rt++;
            }
        }
        // Whatever remains in [rt..last] is in place
    }

    public static void main(String[] args) {
        int[] a = new int[100];
        Random r = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = r.nextInt(10000);
        }
        System.out.println("InPlaceMergeSort排序前：");
        System.out.println(Arrays.toString(a));
        inPlaceMergeSort(a);
        System.out.println("InPlaceMergeSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 该排序的时间复杂度与归并排序相当：

  时间复杂度（最差）：O(n * (log n)^2)

• 由于未使用辅助数组，因此该排序的空间复杂度为：O(1)

• 该排序为稳定排序算法。

Strand排序（StrandSort）

简介及原理

Strand排序（StrandSort）又称串排序、线排序，其原理主要和子有序数组有关。

这儿的子有序数组是这样定义的：比如一个数组[5,3,7,8,2,1,9]，则它的子有序数组为[5,7,8,9],此时原数组变为[3,2,1],其中子有序数组为[3]，依次类推……得到最终子有序数组为[5,7,8,9],[3],[2],[1]。

得到子有序数组后将它们合并为新的有序数组。

比如数组[7,9,6,3,2,5,8,1]，我们使用Strand排序：

• [7,9,6,3,2,5,8,1] 得到子有序数组和另一个子数组 [7,9][6,3,2,5,8,1];
• [6,3,2,5,8,1] 得到子有序数组和另一个子数组 [6,8][3,2,5,1] ，将[7,9]和[6,8]有序合并得到[6,7,8,9];
• [3,2,5,1] 继续得到 [3,5][2,1]， [3,5]与[6,7,8,9]合并得到[3,5,6,7,8,9];
• [2,1]得到[2][1]，继续合并得到[1,2,3,5,6,7,8,9]；
• [1,2,3,5,6,7,8,9]即为要求的有序数组。

算法描述

1. 对于待排序数组，取首元素为基础数；
2. 向后寻找子有序数组，原数组变为一个子有序数组和一个新的子数组；
3. 对于新的子数组，继续1、2步逻辑，得到新的子子有序数组和另一个新的子子数组；
4. 将子有序数组和子子有序数组合并成有序数组，新的子子数组重复上述逻辑。

动图演示

代码实现

这儿我们借助LinkedList实现StrandSort

public class StrandSort {
    private static <E extends Comparable<? super E>> LinkedList<E> strandSort(LinkedList<E> list) {
        if (list.size() <= 1) {
            return list;
        }
        LinkedList<E> result = new LinkedList<>();
        while (list.size() > 0) {
            LinkedList<E> sorted = new LinkedList<>();
            //same as remove() or remove(0)
            sorted.add(list.removeFirst());
            for (Iterator<E> it = list.iterator(); it.hasNext(); ) {
                E elem = it.next();
                if (sorted.peekLast().compareTo(elem) <= 0) {
                    //same as add(elem) or add(0, elem)
                    sorted.addLast(elem);
                    it.remove();
                }
            }
            result = merge(sorted, result);
        }
        return result;
    }

    private static <E extends Comparable<? super E>> LinkedList<E> merge(LinkedList<E> left, LinkedList<E> right) {
        LinkedList<E> result = new LinkedList<>();
        while (!left.isEmpty() && !right.isEmpty()) {
            //change the direction of this comparison to change the direction of the sort
            if (left.peek().compareTo(right.peek()) <= 0) {
                result.add(left.remove());
            } else {
                result.add(right.remove());
            }
        }
        result.addAll(left);
        result.addAll(right);
        return result;
    }

    public static void strandSort(int[] array){
        LinkedList<Integer> linkedList = new LinkedList<>();
        Arrays.stream(array).forEach(e -> linkedList.add(e));
        List<Integer> list = strandSort(linkedList);
        assert list.size() == array.length;
        for(int i=0;i<array.length;i++){
            array[i] = list.get(i);
        }
    }
    
    public static void main(String[] args) {
        int[] a = new int[100];
        Random r = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = r.nextInt(10000);
        }
        System.out.println("StrandSort排序前：");
        System.out.println(Arrays.toString(a));
        strandSort(a);
        System.out.println("StrandSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 该排序算法的时间复杂度如下：

  • 时间复杂度（最好）： O(n)
  • 时间复杂度（平均）： O(n^2)
  • 时间复杂度（最差）： O(n^2)

• 该排序算法的空间复杂度为： O(n)

• 该排序算法是稳定排序算法。

总结

今天我们了解了7种排序算法，这7种排序算法还是比较好理解的，我们可以看到，各个排序都有各自的一些优点（某些个例除外），比如有的时间复杂度要低些，但空间复杂度要高些；有的空间复杂度低，但是时间复杂度要高些；还有一些数据量小的情况下，可能经典排序（冒泡、插入、选择）效率要高，因此可以选择一个合适的阈值，当要排序的数组部分数据量小时，我们可以使用它们代替。

比如归并排序，如果数组较小，就没必要继续归并，而采用插入排序可能会提高效率等。

所以后面我们会介绍一些经典的混合排序，还有一些基于某些原理的排序等。