排序算法（二）

前言

之前一篇文章介绍了10种常用的排序算法，Java排序算法,今天我们来介绍一些其它的排序算法。

数据排序问题到今天，虽然是一个“已经被解决了”的问题，但是仍有许多排序算法出现，它们有些基于一些原理，有些是基础排序算法的优化。

我们了解下这些排序算法，对我们是十分有帮助的。

正文

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

Sort Name	Time(Best)	Time(Average)	Time(Worst)	Memory	Stable
BeadSort	O(n)	O(n^2)	O(n^2)	O(n^2)	YES
SleepSort	unpredictable	unpredictable	∞	unpredictable	NO
BogoSort	O(n)	O(n * n!)	O(n * n! -> ∞ )	O(1)	NO
PermutationSort	O(n!)	O(n!)	O(n!)	O(1)	NO
GnomeSort	O(n)	O(n^2)	O(n^2)	O(1)	YES
PigeonholeSort	O(n+k)	O(n+k)	O(n+k)	O(n*k)	YES
CombSort	——	O(n^2)	O(n^2)	O(1)	NO
CocktailSort	O(n)	O(n^2)	O(n^2)	O(1)	YES
BinaryInsertionSort	O(n)	O(n^2)	O(n^2)	O(1)	YES
CycleSort	O(n)	O(n^2)	O(n^2)	O(1)	NO

我们分别来看一下。

珠排序（BeadSort）

简介及原理

珠排序(BeadSort)，也叫重力排序，是一种自然排序算法，由Joshua J. Arulanandham, Cristian S. Calude 和 Michael J. Dinneen 在2002年发展而来，并且在欧洲理论计算机协会的新闻简报上发表了该算法。

该算法的原理可认为基于重力原理，我们对算盘一定比较熟悉，设想算盘上的每个珠子代表1，开始时算珠排列无序，当我们竖起算盘时，算珠就会整齐的排列起来。

算法描述

1. 我们需要找到待排序数组中的最大值，以此值为x轴最大值，以待排序数组长度为y轴，我们可以构建一个二维数组（算盘）；
2. y轴上数据表示数组元素的值，因此我们以y轴为基准，对于一个数组元素N，就在该位置放N个珠子（表现在二维数组上即为1）;
3. 上面即是算盘的初始化，初始化完成后，我们以x轴为基准，这时候y轴珠子的高度不同，切换基准后，由于重力原因，珠子会下坠，直到稳定;
4. 最后我们以y轴为基准获取上面的值，从下到上可形成数组的倒序，从上到下可形成数组的正序，这样数据便排序完成。

动图演示

代码实现

根据上面描述，我们很容易实现代码：

public class BeadSort {
    public static void beadSort(int[] array) {
        int length = array.length;
        //获取待排序数组的最大值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if(array[i] < min){
                min = array[i];
            }
        }
        //初始化算盘
        //构建一个二维数组，算盘最小长度应该为 max,高为 length
        int[][] bead = new int[max][length];
        for (int y=0;y<length;y++){
            for(int x=0;x<array[y];x++){
                bead[x][y] = 1;
            }
        }

        //珠子下落
        for(int x=0;x<max;x++){
            int count = 0;
            for(int y=0;y<length;y++){
                if(bead[x][y]==0){
                    count ++;
                }
            }
            //有值，需要移动
            if(count!=0){
                int[] temp = new int[max];
                for(int k=0;k<count;k++){
                    temp[k] = 1;
                }
                bead[x] = temp;
            }
        }

        //完成后取出数值
        for(int y=0;y<length;y++){
            int len = 0;
            for(int x=0;x<max;x++){
                if(bead[x][y]!=0){
                    len ++;
                }
            }
            array[y] = len;
        }

    }
    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("BeadSort排序前：");
        System.out.println(Arrays.toString(a));
        beadSort(a);
        System.out.println("BeadSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 可以看到我们构建了一个 max length 的二维数组，实际我们想下，也可以构建一个 (max-min+1) length 的二维数组，最后排好后都加上min，理论上可以节约空间。
• 这个排序算法有一个缺点很明显：那就是它只适用于正整数的排序，原因很明显，“算盘”上我们没法表示负数。
• 如果你非要用这种排序方法排含有负数的数组，可以对数组分类，分成正数数组和负数数组，负数数组数据先转为正数排序，排好后在转成负数数组和另一个排好的正数数组合并。

• 关于珠排序的时间复杂度：

  O(1)：即所有珠子都同时移动，但这种算法只是概念上的，无法在计算机中实现。

  O(√n)：在真实的物理世界中用引力实现，所需时间正比于珠子最大高度的平方根，而最大高度正比于n。

  O(n)：一次移动一列珠子，可以用模拟和数字的硬件实现。

  O(S)，S是所有输入数据的和：一次移动一个珠子，能在软件中实现。

• 空间复杂度：可以看到影响空间的max值和length值，都和数据大小n成正比关系，因此该算法即使在最好的情况下，也是有O(n^2)空间复杂度的。

• 稳定性：我们看动图里3的位置变化，可以知道该排序算法是稳定的。
• 实用性：该排序方法并不实用，也不建议使用。

睡排序（SleepSort）

简介及原理

顾名思义，就是睡一会儿，按谁先醒的顺序输出。这要借助计算机中的线程休眠（sleep）机制。

算法描述

1. 对于待排序数组，开 数组长度 个线程，并使它们同时等待；
2. 同时执行线程的sleep方法，sleep数组元素值的时间，哪一个线程先苏醒，就把该值输出；
3. 所有线程sleep完成后，就得到了排序好的数据。

动图演示

代码实现

public class SleepSort {
    public static List<Integer> sleepSort(int[] nums) {
        //创建num个线程池，进行睡排序
        ExecutorService executorService = Executors.newFixedThreadPool(nums.length);
        final CountDownLatch doneSignal = new CountDownLatch(nums.length);
        final List<Integer> list = Collections.synchronizedList(new ArrayList<>());
        List<Future> futureList = new ArrayList<>();
        for (final int num:nums) {
           Future future = executorService.submit(()->{
                doneSignal.countDown();
                try {
                    doneSignal.await();
                    //线程时间为毫秒，可靠性较弱，我们 * 1000 改为秒，可靠性会提高，但是仍有可能排序错误！！！
                    Thread.sleep(num * 1000);
                    list.add(num);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });
            futureList.add(future);
        }
        //循环检测线程是否完成
        while (true){
            boolean finish = true;
            for(Future future:futureList){
                if(!future.isDone()){
                    finish = false;
                }
            }
            if(finish){
               executorService.shutdown();
               break;
            }
        }
        return list;
    }
    public static void main(String[] args) {
        int[] a = new int[10];
        Random r = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = r.nextInt(10);
        }
        System.out.println("SleepSort排序前：");
        System.out.println(Arrays.toString(a));
        List<Integer> list = sleepSort(a);
        System.out.println("SleepSort排序后：");
        System.out.println(Arrays.toString(list.toArray()));
    }
}

其他注意事项

• 强烈不推荐在任何地方使用此方法，如果应用于项目，被发现后后果自付，与本作者无关。

• 该排序方法有许多明显缺点：

  • 该排序方法只能应用于较小的正整数排序；
  • 该排序方法是不可靠的，上述代码我们即使对num * 1000增加了可靠度，而后输出的排序结果也有可能不正确；
  • 该排序方法是不稳定的；
  • 该排序方法的时间复杂度取决于数据值大小，一般远远大于任何排序算法；
  • 由于开了N个线程，我们一般认为该排序方法空间复杂度大于其它排序算法。

Bogo排序（BogoSort）

简介及原理

Bogo排序又称猴子排序，其原理基于猴子无限定理。

猴子无限定理：无限只猴子，在无限的时间内，随机敲击键盘，总有一只可以敲出莎士比亚全集。

可以看到，本排序方法主要思想就是基于运气！！！

算法描述

1. 检查数组是否已排序，如果已排序，输出结果；
2. 如果不是有序数组，随机打乱数组里数据位置，返回第一步。

动图演示

代码实现

public class BogoSort {
    public static void bogoSort(int[] array) {
        int size = array.length;
        int i, j;
        boolean tag;
        while (true) {
            tag = true;
            //检测是否有序
            for (i = 1; i < size; i++) {
                if (array[i] < array[i - 1]) {
                    tag = false;
                    break;
                }
            }
            //如果有序，则排序完成
            if (tag) {
                break;
            }
            //顺序不对，则随机打乱
            Random random = new Random();
            for (i = 0; i < size; i++) {
                j = random.nextInt(size);
                //随机交换两值
                swap(array, i, j);
            }
        }
    }
    private static void swap(int[] a, int p, int q) {
        int temp = a[p];
        a[p] = a[q];
        a[q] = temp;
    }
    public static void main(String[] args) {
        int[] a = new int[10];
        Random r = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = r.nextInt(10000);
        }
        System.out.println("BogoSort排序前：");
        System.out.println(Arrays.toString(a));
        bogoSort(a);
        System.out.println("BogoSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 当数据量逐渐变大时，该排序方法时间复杂度会激增，因此该排序方法非常不实用。
• 可以看到该排序方法是不稳定的。

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

  • 时间复杂度（最好）：O(n)
  • 时间复杂度（平均）：O(n * n!)
  • 时间复杂度（最差）：O(n * n! -> ∞ )

• 该排序方法的空间复杂度为 O(1)。

全排序（PermutationSort）

简介及原理

全排序（PermutationSort）又称全排列排序，顾名思义，一个长度有限的数组，其内部数据的排列组合也是有限的，我们找到全部排列组合，里面总至少有一个组合满足数组有序这个条件。

全排列：从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列，当m=n时所有的排列情况叫全排列。

PS：对于一个长度为n的数组，其全排列组合有 n! 种。

算法描述

1. 对于一个长度为n的数组，列出其所有排列组合情况；
2. 校验所有排列组合是否有序，如果有序，输出该组合结果。

动图演示

代码实现

public class PermutationSort {
    public static int[] permutationSort(int[] a) {
        List<int[]> list = new ArrayList<>();
        permute(a, a.length, list);
        for (int[] x : list) {
            if (isSorted(x)) {
                return x;
            }
        }
        return a;
    }
    //获取数组的全排列
    private static void permute(int[] a, int n, List<int[]> list) {
        if (n == 1) {
            int[] b = new int[a.length];
            System.arraycopy(a, 0, b, 0, a.length);
            list.add(b);
            return;
        }
        for (int i = 0; i < n; i++) {
            swap(a, i, n - 1);
            permute(a, n - 1, list);
            swap(a, i, n - 1);
        }
    }
    //判断数组是否有序
    private static boolean isSorted(int[] a) {
        for (int i = 1; i < a.length; i++) {
            if (a[i - 1] > a[i]) {
                return false;
            }
        }
        return true;
    }
    //交换数组两数数值
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

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

其他注意事项

• 首先看到我们上面代码，列出了所有排列情况，再一一判断每种情况是不是有序，实际上List<int[]> list这个是多余的，我们完全可以在生成每一种组合后，直接判断它是否有序，这样可以节约一定空间和时间，这儿不再过多介绍。
• 可以看到这种排序方法也是不实用的，当数据逐渐变大时，排序耗时我们是无法容忍的。
• 可以看到这种排序方法是不稳定的。
• 该方法的时间复杂度为 O(n!)。
• 该排序方法的空间复杂度为 O(1)。

侏儒排序（GnomeSort）

简介及原理

侏儒排序（GnomeSort或StupidSort）最初由伊朗计算机工程师Hamid Sarbazi-Azad博士于2000年提出并被称为“愚蠢排序”，然后由Dick Grune描述并命名为“GnomeSort”。它在概念上很简单，不需要嵌套循环。

关于GnomeSort名字的由来：Dick Grune描述了一个花园侏儒的故事，侏儒对花园花盆进行分类，他看着旁边的花盆和前一个花盆; 如果他们按照正确的顺序，他会向前迈出一步；否则他会将它们交换掉，并向后退一步；如果无法继续后退，他会继续前进; 如果他前进后前面没有了花盆，他就完成了花盆排序。

算法描述

1. 对于给定的数组a，从0下标开始，跳过下标0；
2. 对于大于0的下标，如3，判断数组值a[3]和a[2]大小，如果a[3]>=a[2]，继续下一个值比较；
3. 如果a[3] < a[2],就会将a[3]和a[2]交换，同时我们的位置会移动到下标2上，比较a[2]（实际上是原来的a[3]）与a[1]的大小，相当于重复第二步过程；
4. 可以看到边界条件就是位置为0和位置为数组长度-1的地方，一个是无法继续向“后退”（说明这个值是当前已排序部分的最小值），一个是无法继续“前进”（说明排序完成）。

动图演示

代码实现

public class GnomeSort {
    public static void gnomeSort(int[] ar) {
        int n = ar.length;
        int i = 0;
        while (i < n) {
            if (i == 0 || ar[i - 1] <= ar[i]) {
                i++;
            } else {
                int tmp = ar[i];
                ar[i] = ar[i - 1];
                ar[--i] = tmp;
            }
        }
    }
    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("GnomeSort排序前：");
        System.out.println(Arrays.toString(a));
        gnomeSort(a);
        System.out.println("GnomeSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 可以看到侏儒排序十分“简单”（代码层面上），它只有一层循环，但是循环次数 >=n次（n为数组长度），当顺序错误（ar[i - 1] > ar[i]）时，除了交互两数外，i值还会减1，这就是所说的“后退”；
• 我们也可以引入变量，用来记录a[i]，在与a[i - 1]及之前的数进行对比，找到位置后进行存储，这样处理的话侏儒排序类似于插入排序的变种；
• 可以看到该排序方法为稳定排序；

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

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

• 该排序方法的空间复杂度为 O(1)。

鸽巢排序（PigeonholeSort）

简介及原理

鸽巢排序（PigeonholeSort）也被称作基数分类，原理类似桶排序,同样需要一个很大的鸽巢（桶排序里管这个叫桶），鸽巢其实就是数组，数组的索引位置就表示值，该索引位置的值表示出现次数，如果全部为1次或0次那就是桶排序。

鸽巢排序的原理：我们可以构建数组元素最大值个“鸽巢”，对于待排序数组，将它的元素值一个个对应到“鸽巢”索引值上，如果“鸽巢”该索引位置值为0，表示数组里没有此值，如果为n（>=1），表示数组里该元素（索引值）有n个该值。

算法描述

1. 给定一个待排序数组，创建一个备用数组（鸽巢），并初始化元素为0，备用数组的索引即是待排序数组的值；
2. 把待排序数组的值，放到“鸽巢”里（即用作备用数组的索引）；
3. 把“鸽巢”里的值再依次送回待排序数组。

动图演示

代码实现

public class PigeonholeSort {
    private static int[] pigeonhole(int[] array, int maxNumber){
        int[] pigeonhole = new int[maxNumber + 1];
        /*
         * pigeonhole[10] = 4; 的含意是
         * 在待排数组中有4个10出现,同理其它
         */
        for (int item:array) {
            pigeonhole[item]++;
        }
        return pigeonhole;
    }
    public static void pigeonholeSort(int[] array){
        int max = array[0];
        for (int e:array) {
            if(e>max){
                max = e;
            }
        }
        //构建鸽巢
        int[] sorted = pigeonhole(array,max);
        int index = 0;
        for(int i=0;i<sorted.length;i++){
            //如果有不为空的说明放入了元素，下标即为元素值
            if(sorted[i]!=0){
                for(int k=0;k<sorted[i];k++){
                    array[index] = i;
                    index++;
                }
            }
        }
    }
    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("PigeonholeSort排序前：");
        System.out.println(Arrays.toString(a));
        pigeonholeSort(a);
        System.out.println("PigeonholeSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 感觉是不是很像计数排序？是的，鸽巢排序的一个比较有名的变形就是计数排序，对于解决指定问题有奇效；
• 我们可以看到，如果我们数组元素差值较大，比如[1,100,100000,888888]这个数组，我们使用鸽巢排序，会浪费很大空间，所以它只有在差值(或者可被映射在差值)很小的范围内的数值排序的情况下适用（鸽巢也可以是对象数组等，对象的比较需要有具体实现等）;
• 我们一般很少使用鸽巢排序, 因为它很少可以在灵活性, 简便性, 尤是速度上超过其他主流排序算法；
• 该排序算法为稳定排序算法；

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

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

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

梳排序（CombSort）

简介及原理

梳排序（CombSort）是一种由Wlodzimierz Dobosiewicz于1980年所发明的不稳定排序算法，并由Stephen Lacey和Richard Box于1991年四月号的Byte杂志中推广。

梳排序改良自冒泡排序和快速排序，其要旨在于消除“乌龟”（亦即在数组尾部的小数值），这些数值是造成冒泡排序缓慢的主因。相对地，“兔子”（亦即在数组前端的大数值）不影响冒泡排序的性能。

我们知道，在冒泡排序中，只比较数组中相邻的二项，即比较的二项的间距（Gap）是1，梳排序提出此间距其实可大于1。

梳排序中，开始时的间距设置为数组长度，并在循环中以固定比率递减，即递减率。在一次循环中，梳排序如同冒泡排序一样把数组从首到尾扫描一次，比较及交换两项，不同的是两项的间距不固定于1。如果间距递减至1，梳排序假定输入数组大致排序好，并以冒泡排序作最后检查及修正。

递减率的设置影响着梳排序的效率，原作者以随机数作实验，得到最有效递减率为1.3。

如果此比率太小，则导致循环中有过多的比较，如果比率太大，则未能有效消除数组中的“乌龟”。有时候我们也会取递减率倒数与间距相乘（因为编程语言乘法较快）来进行计算，这个倒数通常取0.8.

算法描述

1. 对于待排序数组，我们开始以数组长度为间距delta，比较两值，如果a[i] > a[i + delta]，则交换他们的位置；
2. 根据递减率shrink，先判断间距delta是否 >1，是的话下次间距变为delta = delta/shrink ，继续第一步比较；
3. 最后再用冒泡排序排序一遍得到排序好的数组。

动图演示

代码实现

public class CombSort {
    public static void combSort(int[] data) {
        int n = data.length;
        final double shrink = 1.3;
        int i, delta = n, noswap = 0;
        while (noswap == 0) {
            for (noswap = 1, i = 0; i + delta < n; i++) {
                if (data[i] > data[i + delta]) {
                    data[i] ^= data[i + delta];
                    data[i + delta] ^= data[i];
                    data[i] ^= data[i + delta];
                    noswap = 0;
                }
            }
            if (delta > 1) {
                delta /= shrink;
                noswap = 0;
            }
        }
    }

    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("CombSort排序前：");
        System.out.println(Arrays.toString(a));
        combSort(a);
        System.out.println("CombSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 上述代码我们使用了除法计算循环间距，当然也可以使用乘法，乘数可以取0.8；
• 梳排序的效率在开始时最佳，接近结束时，即进入冒泡排序时最差。如果间距delta变得太小时(例如小于10)，我们可以改用插入排序等其他排序算法，提升整体性能；
• 梳排序是一种不稳定排序算法；

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

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

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

鸡尾酒排序（CocktailSort）

简介及原理

鸡尾酒排序（CocktailSort）是冒泡排序（BubbleSort）的一种变形，也称双向冒泡排序。

之所以称为双向冒泡排序，是因为该排序算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。如何双向呢？

对于冒泡排序，我们每次是由左到右（或者由右到左）依次比较序列里的每个元素；而对于鸡尾酒排序，我们是先由左到右然后在由右到左去比较序列中的元素。

算法描述

1. 对于待排序数组，对于每次循环，我们都会由左到右（升序）进行冒泡排序，然后在由右到左（降序）进行冒泡排序；
2. 这样对于外层循环，我们只需循环数组一半长度即可；
3. 先对数组从左到右排序（升序）将最大的数字放在最右端;
4. 再对数组从右到左排序（降序）将最小的数字放在最左端;
5. 以此类推（先找最大，再找最小，然后找第二大，再找第二小），不断缩小未排序数字的范围，直到最后一个数字结束。

动图演示

代码实现

public class CocktailSort {
    public static void cocktailSort(int[] src) {
        for (int i = 0; i < src.length / 2; i++) {
            //将最小值排到队首
            for (int j = i; j < src.length - i - 1; j++) {
                if (src[j] > src[j + 1]) {
                    int temp = src[j];
                    src[j] = src[j + 1];
                    src[j + 1] = temp;
                }
            }
            //将最大值排到队尾
            for (int j = src.length - 1 - (i + 1); j > i; j--) {
                if (src[j] < src[j - 1]) {
                    int temp = src[j];
                    src[j] = src[j - 1];
                    src[j - 1] = 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("CocktailSort排序前：");
        System.out.println(Arrays.toString(a));
        cocktailSort(a);
        System.out.println("CocktailSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 我们可以看到，鸡尾酒排序相对于普通冒泡排序减少了数据比较次数，因此鸡尾酒排序是冒泡排序的一种优化，其理论性能会高于普通冒泡排序；

• 鸡尾酒排序的时间复杂度：

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

• 空间复杂度：O(1)

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

折半插入排序（BinaryInsertionSort）

简介及原理

折半插入排序（BinaryInsertionSort）又称二分插入排序，是普通插入排序（InsertionSort）的一种优化。

听名字也很好理解，对于普通插入排序，我们是和已排队列一个一个比较找到该值要插入的位置；而对于折半插入排序，是在已排数组中通过二分查找查找到数据插入位置，在将数据统一后移来实现。

算法描述

1. 二分法查找插入位置，创建两个指针 low = 0，high = i-1；
2. mid = (low+high)/2 ,对于data[i]，如果data[i] < data[mid]，说明还要向小查找，此时将high = mid-1；如果data[i] > data[mid]。说明还要向大查找，此时将low = mid+1；
3. 需要判断low和high，如果low > high，就无需继续查找了，要插入的位置即为low，否则继续进行2步骤。

动图演示

代码实现

public class BinaryInsertionSort {
    public static int[] binaryInsertionSort(int[] data) {
        for (int i = 1, len = data.length; i < len; i++) {
            // 要插入的元素
            int temp = data[i];
            int low = 0;
            int high = i - 1;
            // 折半比较，直到找到low大于high时（找到比他大的值的位置low）
            while(low <= high) {
                int mid = (low+high)/2;
                if (data[mid] > temp) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            // 移动 比他大的值，全部后移
            for (int j = i; j > low; j--) {
                data[j] = data[j-1];
            }
            // 插入
            data[low] = temp;
        }
        return data;
    }

    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("BinaryInsertionSort排序前：");
        System.out.println(Arrays.toString(a));
        int[] s = binaryInsertionSort(a);
        System.out.println("BinaryInsertionSort排序后：");
        System.out.println(Arrays.toString(s));
    }
}

其他注意事项

• 和普通插入排序比起来，因为使用了二分查找，所以理论上比较次数平均会少一些；
• 折半查找只是减少了比较次数，但是元素的移动次数不变；

• 该排序时间复杂度：

  时间复杂度和排序完成度没有关系，和数组大小有关系，因此该排序时间复杂度与普通插入排序相当。

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

• 空间复杂度：O(1)

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

圈排序（CycleSort）

简介及原理

圈排序的理论基础是，如果每个坏组的元素返回到它们的正确位置，那么整个序列将被排序。

什么是坏组？

给定一个对象序列，例如一个整数数组;如果这些元素没有按顺序排列，那是因为其中一些元素在它们之间交换了位置。如下：

对于数列 [4,1,2,3,5,0]不是按顺序排列的，因为4,5,0交换了位置(1个坏组)，[4、2、3、7、5、0、1]顺序不对，因为4、5、0交换了位置，2、3、7、1交换了位置(两个坏组)。

在离散数学中，每一组，无论好坏，都被称为一个周期或一个轨道。

我们按照此理论进行的排序便可称为圈排序。

算法描述

1. 对于待排序数组，比如[5、3、4、8、6、1、2]，可以看到它的有序数组为[1、2、3、4、5、6、8]；
2. 可以看到5、3、4、8、6、1、2顺序不对，不在自己位置上，5应该在6的位置，6应该在1的位置，1应该在5的位置上，因此5、6、1构成了一个坏组；同理3应该在4位置，4应该在8位置，8应该在2位置，2应该在3位置，因此3、4、8、2构成一个坏组；
3. 我们通过循坏将上述两个坏组的位置调整，单项循坏，位置变化 5->6->1->5，3->4->8->2->3，便可以得到有序数组[1、2、3、4、5、6、8]。

动图演示

代码实现

public class CycleSort {
    public static void cycleSort(int[] array) {
        for (int cs = 0, seeker, pos; cs < array.length - 1; cs++) {
            //假设array[cs]中的元素不合适
            seeker = array[cs];
            pos = cs;
            //找到seeker的正确位置(pos)
            for (int i = cs + 1; i < array.length; i++) {
                if (array[i] < seeker) {
                    pos++;
                }
            }
            //如果seeker已经在正确的位置，继续
            if (pos == cs) {
                continue;
            }
            //复制后移动索引pos(如果有的话)
            while (seeker == array[pos]) {
                pos++;
            }
            //seeker放到了它正确的位置（索引pos处），同时原来pos处的元素成为了新的seeker，需要找到另一个位置
            seeker = set(array, seeker, pos);

            //在进入下一个循环之前完成当前循环。在当前周期结束时，pos==cs，因为一个周期总是在它开始的地方结束。
            while (pos != cs) {
                //代码同上
                pos = cs;
                for (int i = cs + 1; i < array.length; i++) {
                    if (array[i] < seeker) {
                        pos++;
                    }
                }
                while (seeker == array[pos]) {
                    pos++;
                }
                seeker = set(array, seeker, pos);
            }
        }
    }

    private static int set(int[] array, int data, int ndx) {
        try {
            return array[ndx];
        } finally {
            array[ndx] = data;
        }
    }

    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("CycleSort排序前：");
        System.out.println(Arrays.toString(a));
        cycleSort(a);
        System.out.println("CycleSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 可以看到圈排序期间，每个元素最多移动一次；

• 该算法的时间复杂度：

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

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

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

总结

通过上述10种排序算法，我们了解了许多“奇奇怪怪”的排序算法，以及它们的一些原理，排序算法也远远不止这些，后面我们还会介绍更多的排序算法，及其一些基本原理。

源码

上述文章中包含本章中所有的源代码，有兴趣的同学也可以通过我的 Github 查看源码。