八大排序算法

一、直接插入

- 1.基本思路

- 2.代码实现

- 3.时间复杂度和空间复杂度
二、希尔排序

- 1.基本思路

- 2.代码实现

- 3.时间复杂度和空间复杂度
三、简单选择

- 1.基本思路

- 2.代码实现

- 3.时间复杂度和空间复杂度
四、堆排序

- 1.基本思路

- 2.代码实现

- 3.时间复杂度和空间复杂度
五、冒泡排序

- 1.基本思路

- 2.代码实现

- 3.时间复杂度和空间复杂度
六、快速排序

- 1.基本思路

- 2.代码实现

- 3.时间复杂度和空间复杂度
七、归并排序

- 1.基本思路

- 2.代码实现

- 3.时间复杂度和空间复杂度
八、基数排序

- 1.基本思路

- 2.代码实现

- 3.时间复杂度和空间复杂度
总结




八大排序算法
一、直接插入
1.基本思路
在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
2.代码实现

1.遍历数组，每次循环从第二个数字往前插入
2.设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。
3.从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。

public static void insertSort(int[] data) {
    int temp;
    for(int i = 1;i < data.length; i++){// 取第i个数,插入前边的有序的序列
        temp = data[i];
        int j;
        for(j = i - 1; j>=0; j--) {// 从第i-1的位置上开始比较
            if(data[j] > temp) {// 若前面的数大，则往后挪一位
                data[j+1] = data[j];
            } else {
                break;// 否则，说明要插入的数比较大
            }
        }
        data[j+1] = temp;// 找到这个位置，插入数据
    }
}

3.时间复杂度和空间复杂度
直接插入排序的平均复杂度为O(n²)，最坏时间复杂度：O(n²)，空间复杂度：O(1)，没有分配内存。
二、希尔排序
针对直接插入排序下的效率问题，有人对此进行了改进与升级，这就是现在的希尔排序。希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
1.基本思路


1.数的个数为length，i=length/2，将下标差值为i的数分为一组，构成有序序列。


2.再取i=i/2 ，将下标差值为i的数分为一组，构成有序序列。


3.重复第二步，直到k=1执行简单插入排序。


思路：

1.希尔排序（shell sort）这个排序方法又称为缩小增量排序，是1959年D·L·Shell提出来的。该方法的基本思想是：设待排序元素序列有n个元素，首先取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列，所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。
2.由于开始时，increment的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期increment取值逐渐变小，子序列中元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。

希尔排序举例：


2.代码实现

1.遍历数组，每次循环从第二个数字往前插入
2.设定插入数和得到已经排好序列的最后一个数的位数。temp和j=i-1。
3.从最后一个数开始向前循环，如果插入数小于当前数，就将当前数向后移动一位。

（1）首先确定每一组序列的下标的间隔，循环每次需要的间隔：int i = length/2; i >0 ; i /= 2
（2）然后将每一组序列中元素进行插入排序，第二组第一个插入的数字是第一组第一个插入数字之后的那个数组，从i之后每个数字都要进行插入排序，就是插入的序列是各自不同的序列，不是一个一个子序列循环，而是在一个循环中for (int j=i;j<length;j++)完成所有子序列的插入排序。
（3）直到i=0为止。
public static void shellSort(int[] array) {
    int length = array.length;
    for (int i = length / 2; i > 0; i /= 2) {//序列的间隔，一直到间隔为一，这时候就只有一个子序列
        for (int j = i; j < length; j++) {//从i之后每个数字都要进行插入排序，就是插入的序列是各自不同的序列
            int temp = array[j];//里面就是直接插入算法
            int k;
            for (k = j - i; k >= 0; k -= i) {//实现各个数字插入排序到不同的序列中，直到间隔为1的时候，只有一个序列，就是完全的一个直接插入排序
                if (temp < array[k]) {
                    array[k + i] = array[k];
                } else {
                    break;
                }
            }
            array[k + i] = temp;//把数字插入到位置上
        }
    }
    System.out.println(Arrays.toString(array));
}

3.时间复杂度和空间复杂度
希尔排序的平均时间复杂度为O(n²)，空间复杂度O(1) 。
三、简单选择
1.基本思路
基本原理如下：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录的位置与第一个记录的位置交换；接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小记录并与第二个位置记录交换；重复该过程，直到进行比较的记录只剩下一个为止。
2.代码实现

1.确定要插入最小值的位置，从0开始到最后int i = 0; i <len ; i++
2.将每次开始位置上的数字暂定为最小值min,从开始数字之后一个个和min比较，再把最小值存放到min
3.将最小值所在位置上的数字和开始位置上的数字交换

public static void selectSort(int[] array) {
    int len = array.length;
    for (int i = 0; i < len; i++) {//确定每次开始的位置
        int min = array[i];//设定开始数字为最小的值最小值
        int flag = i;
        for (int j = i + 1; j < len; j++) {//把最小值存放到min,从开始数字向后一个个和min比较，再把最小值存放到min
            if (min > array[j]) {
                min = array[j];
                flag = j;
            }
        }
        if (flag != i) {
            array[flag] = array[i];
            array[i] = min;
        }
    }
    System.out.println(Arrays.toString(array));
}

3.时间复杂度和空间复杂度
简单选择排序的时间复杂度为O(n²)
四、堆排序
1.基本思路

1.若array[0，…，n-1]表示一颗完全二叉树的顺序存储模式，则双亲节点指针和孩子结点指针之间的内在关系如下：

任意一节点指针 i：
父节点：i==0 ? null : (i-1)/2
左孩子：2*i + 1
右孩子：2*i + 2


2.堆得定义

n个关键字序列array[0，...，n-1]，当且仅当满足下列要求：(0 <= i <= (n-1)/2)
① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]； 称为小根堆；
② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]； 称为大根堆；


3.建立大顶堆

n个节点的完全二叉树array[0，…，n-1]，最后一个节点n-1是第(n-1-1)/2个节点的孩子。对第(n-1-1)/2个节点为根的子树调整，使该子树称为堆。
对于大根堆，调整方法为：若【根节点的关键字】小于【左右子女中关键字较大者】，则交换。
之后向前依次对各节点（(n-2)/2 - 1）~ 0为根的子树进行调整，看该节点值是否大于其左右子节点的值，若不是，将左右子节点中较大值与之交换，交换后可能会破坏下一级堆，于是继续采用上述方法构建下一级的堆，直到以该节点为根的子树构成堆为止。
反复利用上述调整堆的方法建堆，直到根节点。

4.堆排序（大顶堆）

①将存放在array[0，...，n-1]中的n个元素建成初始堆；
②将堆顶元素与堆底元素进行交换，则序列的最大值即已放到正确的位置；
③将数组中array[0，...，n-1]前n-1个元素再次形成大根堆，再重复第②③步，直到堆中仅剩下一个元素为止。

2.代码实现

/**
    *  大顶堆排序
    * @param array
    */
public static void maxHeapSort(int[] array) {
    int i;
    int len = array.length;
    // 构建大顶堆
    for (i = len / 2 - 1; i >= 0; i--) {
        adjustMaxHeap(array, i, len);
    }
    // 堆顶是最大值，交换堆顶和最后一个数，再重新调整最大堆，下一次循环   i--
    for (i = len - 1; i >= 0; i--) {
        int temp = array[0];
        array[0] = array[i];
        array[i] = temp;
        adjustMaxHeap(array, 0, i);
    }
    System.out.println(Arrays.toString(array));
}

private static void adjustMaxHeap(int[] a, int pos, int len) {
    int temp;
    int child;
    for (temp = a[pos]; 2 * pos + 1 < len; pos = child) {
        // 数组从0开始，r(i)>=r(2i) r(i)>=r(2i+1)  对应 pos => 2 * pos + 1 和 2 * pos +2
        child = 2 * pos + 1;
        // 有右孩子，且右孩子数值更大
        if (child + 1 < len && a[child] < a[child + 1]) {
            child++;
        }
        // 最大的孩子大于根节点
        if (a[child] > temp) {
            a[pos] = a[child];
        } else {
            break;
        }
    }
    a[pos] = temp;
}

3.时间复杂度和空间复杂度
时间复杂度:建堆：o(n)，每次调整o(log n)，故最好、最坏、平均情况下：o(n*logn);
五、冒泡排序
1.基本思路
一次冒泡将序列中从头到尾所有元素两两比较，将最大的放在最后面。
将剩余序列中所有元素再次两两比较，将最大的放在最后面。
重复第二步，直到只剩下一个数。
2.代码实现
/**
 * @author fupeng
 * 冒泡排序优化第二版
 * 第一版优化增加flag标记，没有数字交换直接return，最优时间复杂度O(n)
 * 第二版优化，增加tempPostion记录内循环最后一次交换的位置，来缩减内循环的次数
 */
public static void bubbleSort(int[] array) {
    int len = array.length - 1;
    // 开辟一个临时空间, 存放交换的中间值
    int temp;
    // 记录最后一次交换的位置
    int tempPostion = 0;
    // 要遍历的次数
    for (int i = 0; i < array.length - 1; i++) {
        int flag = 1; // 设置一个标志位
        // 依次比较相邻两个数的大小，遍历一次后，会将前面没有排好序的最大值放到后面位置
        for (int j = 0; j < len; j++) {
            // 比较相邻的元素，如果前面的数大于后面的数，交换
            if (array[j] > array[j + 1]) {
                temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
                // 发生交换，标志位置0
                flag = 0;
                // 记录交换的位置
                tempPostion = j;
            }
        }
        // 把最后一次交换的位置给len，来缩减内循环的次数
        len = tempPostion;
        // 如果没有交换过元素，则已经有序
        if (flag == 1) {
            System.out.println(Arrays.toString(array));
            return;
        }
    }
    System.out.println(Arrays.toString(array));
}

3.时间复杂度和空间复杂度
冒泡排序的最好时间复杂度为O(n),最坏时间复杂度为O(n²),平均时间复杂度为O(n²),空间复杂度为O(1),它是一种稳定的排序算法。
六、快速排序
1.基本思路
快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：

1.从数列中挑出一个元素，称为"基准"（pivot）。
2.重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3.递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
2.代码实现
public static void quickSort(int[] array) {
    sort(array, 0, array.length - 1);
    System.out.println(Arrays.toString(array));
}

private static void sort(int[] a, int low, int high) {
    int i = low;
    int j = high;
    if (a.length <= 1) {
        return;
    }
    if (i >= j) {
        return;
    }
    int index = a[i];
    while (i < j) {
        while (i < j && a[j] >= index)
            j--;
        if (a[j] < index)
            a[i++] = a[j];
        while (i < j && a[i] <= index)
            i++;
        if (a[i] > index)
            a[j--] = a[i];
    }
    a[i] = index;
    sort(a, low, i - 1);
    sort(a, i + 1, high);
}

3.时间复杂度和空间复杂度
虽然 快排的时间复杂度达到了 O(n²)，但是在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。
七、归并排序
1.基本思路
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

1.分而治之



可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

2.合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。




2.代码实现
public static void mergeSort(int[] array) {
    int[] temp = new int[array.length];// 在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
    mergeSort(array, 0, array.length-1, temp);
    System.out.println(Arrays.toString(array));
}

private static void mergeSort(int[] arr, int left, int right, int []temp) {
    if(left < right) {
        int mid = (left+right) / 2;
        mergeSort(arr, left, mid, temp);// 左边归并排序，使得左子序列有序
        mergeSort(arr, mid+1, right, temp);// 右边归并排序，使得右子序列有序
        merge(arr, left, mid, right, temp);// 将两个有序子数组合并操作
    }
}

private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left;// 左序列指针
    int j = mid+1;// 右序列指针
    int t = 0;// 临时数组指针
    while (i <= mid && j <= right) {
        if(arr[i] <= arr[j]) {
            temp[t++] = arr[i++];
        } else {
            temp[t++] = arr[j++];
        }
    }
    while(i <= mid) {// 将左边剩余元素填充进temp中
        temp[t++] = arr[i++];
    }
    while(j <= right) {// 将右序列剩余元素填充进temp中
        temp[t++] = arr[j++];
    }
    t = 0;
    // 将temp中的元素全部拷贝到原数组中
    while(left <= right) {
        arr[left++] = temp[t++];
    }
}

3.时间复杂度和空间复杂度
归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
八、基数排序
1.基本思路

1.基数排序的思想就是先排好各位，然后排好各位的基础上排十位，以此类推，直到遍历最高位 次，排序结束（仔细理解最后一句话）
2.基数排序不是比较排序，而是通过分配和收集的过程来实现排序
3.初始化10个桶(固定的)，桶下标为0-9
4.通过得到待排序数字的个十百等位的数字，把这个数字对应的item放到对应的桶中
5.基数排序有两种排序方式：LSD和MSD，最小位优先(从右边开始)和最大位优先(从左边开始)


2.代码实现
public static void radixSort(int[] array) {
    ArrayList<ArrayList<Integer>> queue = new ArrayList<>();
    for (int i = 0; i <10 ; i++) {
        queue.add(new ArrayList<>());// 创建一个基数从0---9 每个数字上都是一个list
    }
    // 找到最大值，并判断最大值是几位数
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    int time = 0;
    while (max > 0) {
        max /= 10;
        time++;
    }
    for (int i = 0; i < time; i++) {// 循环每一个位数（个位、十位、百位）
        for (int j = 0; j < array.length; j++) {// 循环数组，取每一个值
            int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
            ArrayList<Integer> queue3 = queue.get(x);

            queue3.add(array[j]);
            queue.set(x, queue3);
        }
        int count = 0;
        for (int k = 0; k < 10; k++) {
            while (queue.get(k).size() > 0) {
                ArrayList<Integer> queue4 = queue.get(k);
                array[count] = queue4.get(0);
                queue4.remove(0);
                count++;
            }
        }
    }
}

3.时间复杂度和空间复杂度
归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
总结

引用：
https://www.cnblogs.com/mensan/p/10570050.html
https://www.cnblogs.com/jyroy/p/11248691.html
https://www.cnblogs.com/chengxiao/p/6194356.html
https://www.jianshu.com/p/8340dfaea3af

    大数据的排序和内存排序其实核心都差不多，只是大数据不能一次性的load到内存，所以就有了大数据处理的惯用手法“分治”和“归并”。这是处理大数据的屡试不爽的方法。将数据分片，交给不同的机器去处理，或者在同一台机器上分批处理（因为一次没法load）。
    我们举例来说明怎么分片排序（外归并排序），这里我们进行的是9路归并排序：
    比如，要对 9GB的数据进行排序，但机器上只有 1 GB 的可用内存时，外归并排序按如下方法操作：
    1. 读入 1GB 的数据至内存中，用某种常规方式（如快速排序、堆排序等方法）在内存中完成排序。
    2. 将排序完成的数据写入磁盘，文件大小约1GB
    3. 重复1，2，则产生了9个小文件（每个大小1GB），每个文件里的数据都是排好序的。
   下面开始归并：
   1. 从9个文件里各读出100MB数据（9个文件共占用了900MB内存，还有100MB内存作为输出缓冲区）。
   2. 对9路有序数据的第一个进行比较，得到最小的，输出到缓冲区，这个数据就是所有元素的最小值。
   3. 该路数据前移动，后一个自动成为队首数据；
   4.重复2和3，如果某一路队列空了，则从该路关联的文件里load，直到文件全部load完。
   5.如果缓冲区满，则写入结果文件中。
   6.全部数据处理完，排序完成！

一、归并排序

1、介绍。

        归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。

        归并排序是稳定排序，需要额外内存，空间复杂度O(n)。时间复杂度，最佳情况：O(nlogn)  最差情况：O(nlogn)  平均情况：O(nlogn)。

2、步骤。

    (1)申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。

    (2)设定两个指针，最初位置分别为两个已经排序序列的起始位置。

    (3)比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置。

    (4)重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾。

3、代码。

public static void main(String[] args) {
        System.out.println("------开始------");
        //生成生成两份一模一样的随机数组，其中一组用系统自带的方法进行排序，到时候进行验证。
        final int number = 100000;
        int[] sortArray = new int[number];
        int[] sortArrayCopy = new int[number];
        for (int i = 0; i < sortArray.length; i++) {
            sortArray[i] = (int) (Math.random() * number);
        }
        System.arraycopy(sortArray, 0, sortArrayCopy, 0, number);//数组复制
        Arrays.sort(sortArrayCopy);

        //开始排序
        long startTime = System.currentTimeMillis();
        mergeSort(sortArray);//归并(合并)排序
        System.out.println("花费时间：" + (System.currentTimeMillis() - startTime));

        //跟系统排序之后数组进行比较，查看是否排序成功。
        if (Arrays.equals(sortArray, sortArrayCopy)) {
            System.out.println("排序成功");
        } else {
            System.out.println("排序失败");
        }
        System.out.println("------结束------");
    }

//归并(合并)排序 最佳情况：T(n) = O(n)  最差情况：T(n) = O(nlogn)  平均情况：T(n) = O(nlogn)
private static void mergeSort(int[] array) {
    //只剩一个数了
    if (array.length < 2) {
        return;
    }
    //将array数组，切成left和right两个数组
    int middle = array.length / 2;
    int[] left = new int[middle];
    int[] right = new int[array.length - middle];
    for (int i = 0; i < array.length; i++) {
        if (i < middle) {
            left[i] = array[i];
        } else {
            right[i - middle] = array[i];
        }
    }
    //递归
    mergeSort(left);
    mergeSort(right);
    merge(array, left, right);
}

private static void merge(int[] array, int[] left, int[] right) {
    int leftIndex = 0, rightIndex = 0;
    for (int i = 0; i < array.length; i++) {
        if (leftIndex >= left.length) {//left数组已经排完了
            array[i] = right[rightIndex++];
        } else if (rightIndex >= right.length) {//right数组已经排完了
            array[i] = left[leftIndex++];
        } else if (left[leftIndex] < right[rightIndex]) {//left数组的值小于right数组的值
            array[i] = left[leftIndex++];
        } else {//left数组的值大于等于right数组的值
            array[i] = right[rightIndex++];
        }
    }
}

4、结果。



二、自然归并排序

1、介绍。

        自然归并排序:对于初始给定的数组,通常存在多个长度大于1的已自然排好序的子数组段.例如,若数组a中元素为{4,8,3,7,1,5,6,2},则自然排好序的子数组段有{4,8},{3,7},{1,5,6},{2}.用一次对数组a的线性扫描就足以找出所有这些排好序的子数组段.然后将相邻的排好序的子数组段两两合并,构成更大的排好序的子数组段({3,4,7,8},{1,2,5,6}).继续合并相邻排好序的子数组段,直至整个数组已排好序。

        自然归并排序是稳定排序，需要额外内存，空间复杂度O(n)。时间复杂度，最佳情况：O(nlogn)  最差情况：O(nlogn)  平均情况：O(nlogn)。

2、步骤。

        跟归并排序的步骤一样，只不过在选择middle的时候，将前面已经排序好的作为一个数组。

3、代码。

public static void main(String[] args) {
        System.out.println("------开始------");
        //生成生成两份一模一样的随机数组，其中一组用系统自带的方法进行排序，到时候进行验证。
        final int number = 100000;
        int[] sortArray = new int[number];
        int[] sortArrayCopy = new int[number];
        for (int i = 0; i < sortArray.length; i++) {
            sortArray[i] = (int) (Math.random() * number);
        }
        System.arraycopy(sortArray, 0, sortArrayCopy, 0, number);//数组复制
        Arrays.sort(sortArrayCopy);

        //开始排序
        long startTime = System.currentTimeMillis();
        natureMergeSort(sortArray);//自然归并(合并)排序
        System.out.println("花费时间：" + (System.currentTimeMillis() - startTime));

        //跟系统排序之后数组进行比较，查看是否排序成功。
        if (Arrays.equals(sortArray, sortArrayCopy)) {
            System.out.println("排序成功");
        } else {
            System.out.println("排序失败");
        }
        System.out.println("------结束------");
    }

//自然归并(合并)排序 最佳情况：T(n) = O(n)  最差情况：T(n) = O(nlogn)  平均情况：T(n) = O(nlogn)
private static void natureMergeSort(int[] array) {
    //只剩一个数了
    if (array.length < 2) {
        return;
    }
    //将array数组，切成left和right两个数组
    int middle = array.length / 2;
    for (int i = 0; i < array.length - 1; i++) {
        if (array[i] > array[i + 1]) {
            middle = i;
            break;
        }
    }
    int[] left = new int[middle];
    int[] right = new int[array.length - middle];
    for (int i = 0; i < array.length; i++) {
        if (i < middle) {
            left[i] = array[i];
        } else {
            right[i - middle] = array[i];
        }
    }
    //递归
    mergeSort(left);
    mergeSort(right);
    merge(array, left, right);
}

private static void merge(int[] array, int[] left, int[] right) {
    int leftIndex = 0, rightIndex = 0;
    for (int i = 0; i < array.length; i++) {
        if (leftIndex >= left.length) {//left数组已经排完了
            array[i] = right[rightIndex++];
        } else if (rightIndex >= right.length) {//right数组已经排完了
            array[i] = left[leftIndex++];
        } else if (left[leftIndex] < right[rightIndex]) {//left数组的值小于right数组的值
            array[i] = left[leftIndex++];
        } else {//left数组的值大于等于right数组的值
            array[i] = right[rightIndex++];
        }
    }
}

4、结果。

本文转自https://www.cnblogs.com/huangxincheng/archive/2012/12/19/2824943.html  

说到排序，大家第一反应基本上是内排序，是的，算法嘛，玩的就是内存，然而内存是有限制的，总有装不下的那一天，此时就可以来玩玩

外排序，当然在我看来，外排序考验的是一个程序员的架构能力，而不仅仅局限于排序这个层次。

 

一：N路归并排序

1.概序

    我们知道算法中有一种叫做分治思想，一个大问题我们可以采取分而治之，各个突破，当子问题解决了，大问题也就KO了，还有一点我们知道

内排序的归并排序是采用二路归并的，因为分治后有LogN层，每层两路归并需要N的时候，最后复杂度为NlogN，那么外排序我们可以将这个“二”

扩大到M，也就是将一个大文件分成M个小文件，每个小文件是有序的，然后对应在内存中我们开M个优先队列，每个队列从对应编号的文件中读取

TopN条记录，然后我们从M路队列中各取一个数字进入中转站队列，并将该数字打上队列编号标记，当从中转站出来的最小数字就是我们最后要排

序的数字之一，因为该数字打上了队列编号，所以方便我们通知对应的编号队列继续出数字进入中转站队列，可以看出中转站一直保存了M个记录，

当中转站中的所有数字都出队完毕，则外排序结束。如果大家有点蒙的话，我再配合一张图，相信大家就会一目了然，这考验的是我们的架构能力。



 

图中这里有个Batch容器，这个容器我是基于性能考虑的，当batch=n时，我们定时刷新到文件中，保证内存有足够的空间。

 

扩展

leveldb应用

在 LevelDB 数据库中高层数据下沉到低层时需要经历一次 Major Compaction，将高层文件的有序键值对和低层文件的多个有序键值对进行归并排序。磁盘多路归并排序算法的输入是来自多个磁盘文件的有序键值对，在内存中将这些文件的键值对进行排序，然后输出到一到多个新的磁盘文件中。

 



 

多路归并排序在大数据领域也是常用的算法，常用于海量数据排序。当数据量特别大时，这些数据无法被单个机器内存容纳，它需要被切分位多个集合分别由不同的机器进行内存排序（map 过程），然后再进行多路归并算法将来自多个不同机器的数据进行排序（reduce 过程），这是流式多路归并排序，为什么说是流式排序呢，因为数据源来源于网络套接字。

 



 

多路归并排序的优势在于内存消耗极低，它的内存占用和输入文件的数量成正比，和数据总量无关，数据总量只会线性正比影响排序的时间。

下面我们来亲自实现一下磁盘多路归并算法，为什么是磁盘，因为它的输入来自磁盘文件。

算法思路

我们需要在内存里维护一个有序数组。每个输入文件当前最小的元素作为一个元素放在数组里。数组按照元素的大小保持排序状态。

 



 

接下来我们开始进入循环，循环的逻辑总是从最小的元素下手，在其所在的文件取出下一个元素，和当前数组中的元素进行比较。根据比较结果进行不同的处理，这里我们使用二分查找算法进行快速比较。注意每个输入文件里面的元素都是有序的。

1. 如果取出来的元素和当前数组中的最小元素相等，那么就可以直接将这个元素输出。再继续下一轮循环。不可能取出比当前数组最小元素还要小的元素，因为输入文件本身也是有序的。

 



 

2. 否则就需要将元素插入到当前的数组中的指定位置，继续保持数组有序。然后将数组中当前最小的元素输出并移除。再进行下一轮循环。

 



 

3. 如果遇到文件结尾，那就无法继续调用 next() 方法了，这时可以直接将数组中的最小元素输出并移除，数组也跟着变小了。再进行下一轮循环。当数组空了，说明所有的文件都处理完了，算法就可以结束了。

 



 



值得注意的是，数组中永远不会存在同一个文件的两个元素，如此才保证了数组的长度不会超过输入文件的数量，同时它也不会把没有结尾的文件挤出数组导致漏排序的问题。