排序是数据结构与算法研究中相当重要的主题，简单的排序算法有冒泡排序、插入排序、选择排序，复杂的排序算法有希尔排序、归并排序、快速排序等。

简单排序算法执行速度相对慢一些，但是仍值得学习和研究，它们实现上比较简单，容易理解，在某些情况下，比如小规模的数据排序时，甚至比高级的排序算法更有效。

排序过程包括的基本操作：1 比较， 2 交换。

1 冒泡算法

冒泡算法是最基础，最简单的算法，它比较和交换操作的时间复杂度都是 $O(N^2)$O(N2)。其他的算法都是基于冒泡算法去设计，或者优化比较操作的时间复杂度，或者优化交换的时间复杂度，总之效率肯定比冒泡算法高。

算法过程：

代码实现：

    public static void bubbleSort(int[] source) {
        IntStream.range(0 ,source.length).forEach(i-> bubbleOnce(source, source.length - i));
    }

    private static void bubbleOnce(int[] source, int len) {
        IntStream.range(0, len - 1).forEach( i-> {
            if (source[i] > source[i + 1]) {
                swap(source, i, i+1);
            }
        });
    }

	// 交换函数
    private static void swap(int[] source, int i, int j) {
        if (i < 0 || i > source.length || j < 0 || j > source.length || i == j) {
            return;
        }

        int tmp = source[i];
        source[i] = source[j];
        source[j] = tmp;
    }

2 选择算法

选择算法在冒泡算法的基础上优化了数据交换的次数，不是每次比较后都进行交换，而是选择最小的数据项，交换至数据列的首部。比较的次数依然是 $O(N^2)$O(N2)，但交换的次数减少至$O(N)$O(N)。当 交换 消耗的 cpu 时间远大于比较消耗的 cpu 时间时，选择算法很有效！

算法过程：

	public static void selectSort(int[] source) {
        int len = source.length;
        IntStream.range(0 ,len).forEach(i-> swap(source, i, findMinValueIndex(source, i)));
    }

    private static int findMinValueIndex(int[] source, int start) {
        int[] cache = {source[start], start};

        IntStream.range(start+1, source.length).forEach(i -> {
            if (source[i] < cache[0]) {
                cache[0] = source[i];
                cache[1] = i;
            }
        });

        return cache[1];
    }

3 插入排序

插入算法 比较 和 交换 的次数大致是冒泡算法的一半，因此插入算法比冒泡算法快一倍，比选择排序略快。

但是，对于已经有序或者基本有序的序列，插入排序更有效。对于已排序的序列，插入排序的时间复杂度为 $O(N)$O(N)，对于逆序的序列，时间复杂度 $O(N^2)$O(N2)。

算法过程：

    public static void insertSort(int[] source) {
        int len = source.length;
        IntStream.range(1, len).forEach(i -> insertOnce(source, i));
    }

    private static void insertOnce(int[] source, int start) {
        for (int i = start; i > 0 && source[i-1] > source[i]; i--) {
            swap(source, i, i - 1);
        }
    }

4 归并排序

归并排序的时间复杂度是$O(N*logN)$O(N∗logN)，而且实现的逻辑也比较简单，至少比希尔排序和快速排序更容易理解，但缺点是需要额外的存储空间，大小等于被排序的数组。当空间足够时，归并排序时一个很好的选择。

算法过程：

代码实现：

public static int[] mergeSort(int[] source) {
        int len = source.length;
        int[] tmp;
        int[] target = new int[len];

        for (int step = 1; step < len; step*=2) {
            for (int start = 0;start < len; start+=2*step) {
                int end = start + 2* step > len? len: start + 2* step;
                merge(source, start, start + step, source,start + step, end, target, start, end);
            }
            tmp = source;
            source = target;
            target = tmp;
        }

        return source; // 特别注意，这里返回的才是已排序的序列！
    }

    public static void merge(int[] arrayA, int i, int ea,
                       int[] arrayB, int j, int eb,
                       int[] arrayC, int k, int ec) {
        for (; k < ec; k++) {
            if ( i < ea && (j >= eb || arrayA[i] < arrayB[j])) {
                arrayC[k] = arrayA[i];
                i++;
            } else {
                arrayC[k] = arrayB[j];
                j++;
            }
        }
    }

本例中并没有使用递归，递归算法在概念上容易理解，但是，在实际运用中递归算法的效率并不高！

5 希尔排序

希尔排序的时间复杂度为 $O(N*(logN)^2)$O(N∗(logN)2)，几乎和归并算法一样容易实现，并且不需要额外的存储空间。

希尔排序是对插入排序的优化，插入排序对于接近逆序的序列很低效，希尔排序通过增量插入的方式，减少数据 比较 和 交换 的次数。所谓的增量插入，简单的说就是增加交换的距离！

算法过程：

代码实现：

    public static void shellSort(int[] source) {
        int num = source.length;

        int h = 1;
        while (h <= num) {
            h = 3*h + 1; // 保证 1, 4, 13 ....
        }

        for (int i = h; i > 0; i = (i-1)/3) {
            for (int j = i; j < num; j++) {
                for (int t = j; t>=i && source[t] < source[t - i]; t-=i) {
                    swap(source, t, t-i); 
                }
            }
        }
    }

当增量为 1 时，希尔排序的代码逻辑等于插入排序，由于之前的增量插入已经对序列进行了调整，使得最后一次的插入排序非常的高效！

6 快速排序

快速排序的时间复杂度为 $O(N*logN)$O(N∗logN)，是最流行的排序算法。

快速排序算法本质上通过把一个数组划分为两个子数组，然后递归地调用自身为每一个子数组进行快速排序来实现的。

算法过程：

算法实现：

	public static void quickSort(int[] source) {
        doQuickSort(source, 0, source.length-1);
    }

    private static void doQuickSort(int[] source, int from, int to) {
        int right = partition(source, from, to-1);

        if (right > from + 1) doQuickSort(source, from, right - 1);
        if (right < to-1) doQuickSort(source, right+1, to);
    }

    public static int partition(int[] source, int left, int right) {
        int pivot = source[right+1];
        int index = right + 1;

        while (left < right) {
            if (source[left] < pivot) {
                left++;
                continue;
            }

            if (source[right] > pivot) {
                right--;
                continue;
            }

            swap(source, left, right);
        }

        if (source[right] > source[index]) {
            swap(source, right, index);
            return right;
        } else {
            return index;
        }

    }

递归调用，数据量大时会 StackOverflowError！

7 执行性能比较

1. 生成测试数组

	public static int[] randomArray(int len) {
        int[] range = IntStream.range(1, len+1).toArray();
        mix(range);
        mix(range);
        mix(range);
        return range;
    }

    private static void mix(int[] source) {
        int len = source.length;
        IntStream.range(0, source.length).forEach(i->{
            int j = (2*i*i+2)%(len-1);
            int tmp = source[i];
            source[i] = source[j];
            source[j] = tmp;
        });
    }

10000 条数据执行结果：

算法名称	随机序列（毫秒）	顺序序列（毫秒）	逆序序列（毫秒）
bubble.sort	338	297	104
select.sort	444	457	472
insert.sort	132	209	2
merge.sort	6	5	6
shell.sort	30	11	8
quick.sort	16	179	63
Arrays.sort	12	1	1
Stream.sort	7	4	5

Arrays.sort 跟 Stream.sort 都是 Dual-Pivot Quicksort algorithm （双基值快速排序算法）！