1、插入排序：（元素少时插排最快）

1、[ 有序区间（黄色区间），无序区间（蓝色区间） ]

每次操作：

• 1、抓无序区间（右侧蓝区）的第一张牌（红色牌）
• 2、依次和有序区间（左侧黄区）的牌比较（绿色为正在比较的牌）
• 3、选择适合的位置插入

动图展示：

代码实现：

    public static void insertSort(long[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            //1、抓无序区间第一张牌(红色牌)
            long key = array[i + 1];
            //2、将取出的牌依次和有序区间的牌比较
            int j;
            for (j = i; j >= 0; j--) {
                //如果取出 红色的牌的值 < 绿色牌的值
                if (key < array[j]) {
                    //将 绿牌 往后挪一个位置
                    array[j + 1] = array[i];
                } else {
                    break;
                }
            }
            //3、选择合适的位置插入
            array[j + 1] = key;
        }
    }

性能分析：

具备稳定性（相等的两个数相对位置不会变），插入排序，初始数据越接近有序，时间效率越高

2、希尔排序：

希尔是发明者（ShellSort）

插排的优化版（分组插排排序）

排序步骤：（分为几组，就意味着中间间隔是多少）（组数一般为 数组长度 / 2）（下次的组数为上次组数的一半）

• 1、将数组按不同颜色依次分成了 5 组：然后进行组内比较大小，调换顺序
• 2、将第一次调整好的数组分成 2 组：然后进行组内比较大小，调换顺序
• 3、将第二次调整好的数组进行整体比较

动图展示：

代码实现：

    public static void shellSort(long[] array) {
        //gap为间隔，也就是分为了几组
        int gap = array.length / 2;
        while (true) {
            insertSortGap(array,gap);
            if (gap == 1) {
                break;
            }
            //下次的组数为上次组数的一半
            gap = gap / 2;
        }
    }
    public static void insertSortGap(long[] array,int gap) {
        for (int i = gap; i < array.length; i++) {
            // key 为同一组中的第二个数
            long key = array[i];
            int j = 0;
            //同一组中的第一个数
            for (j = i - gap; j >= 0; j = j -gap) {
                //第二个数 < 第一个数
                if (key < array[j]) {
                    //第二个数的值 = 第一个数的值
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            //第一个数 = 之前保存的第二个数的值（此时的 j 是一个负数，加上 gap 刚好为第一个数）
            array[j + gap] = key;
        }
    }

性能分析：

不稳定

3、选择排序：

[ 有序区间（黄色区间），无序区间（蓝色区间）]

每一次从无序区间选出最小（或最大）的一个元素，存放在无序区间的最前（或最后），直到全部待排序的数据元素排完

动图展示：

代码实现：

    public static void selectSort(long[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            //有序区间：[0,i)
            //无序区间：[i,array.length]
            int minIndex = i;//最小数下标
            //先从无序区间中找到最小的数
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            //交换这个 最小数 和 无序区间的第一个数
            long t = array[minIndex];
            array[minIndex] = array[i];
            array[i] = t;
        }
    }

性能分析：

不稳定：（相等的两个数相对位置会变）

int[] a = { 9, 2, 5a, 7, 4, 3, 6, 5b };
// 交换中该情况无法识别，保证 5a 还在 5b 前边

4、堆排序：

随便给一组数据：[ 20,17,16,5,4,3 ]

（无序区间，我们用下划线的方式表示）（有序区间：用小蓝圈来表示）

排序流程：

• 1、建大堆：[ 20,17,4,16,5,3 ]
• 2、从大堆中找出最大值（堆顶元素），和无序区间的最后一个数字交换
• 3、此时数组中左边是无序区间，右边是有序区间，用来存放最大值
• 4、交换完数字后，需要对交换的堆顶元素进行向下调整为大顶堆（不包括有序区间）
• 5、循环遍历该过程

不能通过小堆来实现，因为有序区间放在开头的话，堆的逻辑结构就构不成二叉树了

代码实现：

   public static void heapSort(long[] array) {
        //1、建大堆
        createHeap(array,array.length);
        //2、进行选择的过程，一共需要 array.length - 1组
        for (int i = 0; i < array.length - 1; i++) {
            //无序区间：[ 0,array.length - 1]
            //交换0号下标（大堆中0号下标为堆中最大值）和无序数组中最后一个元素
            long t = array[0];
            array[0] = array[array.length - 1 - i];
            array[array.length - 1 - i] = t;
            // 无序区间变为：[ 0,array - i - 1]
            //向下调整
            adjustDown(array,array.length-1-i,0);
        }
    }
    //建大堆
    private static void createHeap(long[] array, int size) {
        for (int i = (size - 2) / 2; i >= 0; i--) {
            adjustDown(array,size,i);
        }
    }
    //向下调整
    private static void adjustDown(long[] array, int size, int index) {
        while (true) {
            //1、判断该结点是不是叶子结点
            int leftIndex = 2 * index + 1;
            if (leftIndex >= size) {
                //左孩子不存在，该节点是叶子结点
                return;
            }
            //2、找出最大的孩子
            int maxIndex = leftIndex;
            int rightIndex = 2 * index + 2;
            if (rightIndex < size && array[rightIndex] > array[maxIndex]) {
                maxIndex = rightIndex;
            }
            //3、比较最大孩子和该节点的大小
            if (array[index] >= array[maxIndex]) {
                //当前结点的值大于两个孩子的值，则无须交换
                return;
            }
            //4、交换
            long t = array[index];
            array[index] = array[maxIndex];
            array[maxIndex] = t;
            //5、将最大孩子视为 index，循环回去
            index = maxIndex;
        }

性能分析：

不稳定

5、冒泡排序：

[ 无序区间（蓝色区间），有序区间（黄色区间）]

绿色为两个正在比较的牌

在无序区间（蓝色区间），通过相邻两个数的比较，将最大的数冒泡到无序区间的最后，持续这个过程

动图展示：

代码实现：

    public static void bubbleSort(long[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            //无序区间：[0,array.length - 1]
            //有序区间：[array.length - i,array.length]

            //每次进行冒泡之前，假设数组已经有序
            boolean isSorted = true;
            //进行冒泡过程
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    long t = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = t;
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
        }
    }

性能分析：

稳定（当两个数字相同时，不交换两个数字的位置）

6、快速排序：（重点）

步骤：

• 1、从数组中选择一个数（一般是最左边的那个数），作为基准
• 2、实现 partition 方法（小于 基准的放 左边，大于 基准的放 右边）
• 3、分别对左右两个区间按同样的方法处理
• 4、直到（小区间有序： size = 0 / 1）

例如：给定数组：[ 5,2,1,7,3,6,9 ]
（我们用红框来表示基准）

解法类似一颗二叉树

最终结果： [ 1,2,3,5,6,7,9 ]

动图展示：

代码实现：

    public static void quickSort(long[] array) {
        quickSortInternal(array,0,array.length - 1);
    }
    //给定位置之间采用快排
    private static void quickSortInternal(long[] array, int lowIndex, int highIndex) {
        //4、区间内的个数 = 0 / 1时，结束
        int size = highIndex - lowIndex + 1;
        if (size <= 1) {
            return;
        }
        //1、选出一个数（选择最左边的）- array[lowIndex]
        //2、执行 partition，小的放左，大的放右
        //keyIndex 是经过 partition之后，选出来的数最终所在的下标（一次 partition之后，红框的位置）
        int keyIndex = partition(array,lowIndex,highIndex);
        //3、分别对左右区间进行相同处理 - 递归
        quickSortInternal(array,lowIndex,keyIndex - 1);
        quickSortInternal(array,keyIndex + 1,highIndex);
    }

    //以选出的 lowIndex 位置下的元素为基准，遍历数组，把比基准元素小的放到他左边，比他大的放右边
    private static int partition(long[] array, int lowIndex, int highIndex) {
        //选择合适的方法:
        //方法1： 
        //return hover(array,lowIndex,highIndex);
        //方法2：
        //return digAHole(array,lowIndex,highIndex);
        //方法3：
        return doublePointer(array,lowIndex,highIndex);
    }

实现 partition 方法：

• 方法1：Hover 法

    private static int hover(long[] array, int lowIndex, int highIndex) {
        int leftIndex = lowIndex;
        int rightIndex = highIndex;
        // 选择的数是最左边的一个
        long key = array[lowIndex];
        //选择了最左边，从右边先开始
        //因为从右边写起来比较简单，从左边开始写需要处理特殊情况，较复杂
        while (leftIndex < rightIndex) {
            while (leftIndex < rightIndex && array[rightIndex] >= key) {
                rightIndex--;
            }
            while (leftIndex < rightIndex && array[leftIndex] <= key) {
                leftIndex++;
            }
            //rightIndex下标遇到比基数小的数，leftIndex下标遇到比基数大的数，则，交换两个数字
            swap(array,leftIndex,rightIndex);
        }
        swap(array,lowIndex,leftIndex);
        return leftIndex;
    }
    private static void swap(long[] array,int index1,int index2) {
        long t = array[index1];
        array[index1] = array[index2];
        array[index2] = t;
    }

• 方法2：挖坑法（效率最高）

    private static int digAHole(long[] array, int lowIndex, int highIndex) {
        //key 代表基数，将其挖出，则该位置为空
        long key = array[lowIndex];
        int leftIndex = lowIndex + 1;
        int rightIndex = highIndex;
        while (leftIndex < rightIndex) {
        
            while (leftIndex < rightIndex && array[rightIndex] >= key) {
                rightIndex--;
            }
            //把右边小于基数的那个数填到之前左边挖出的坑中
            array[lowIndex] = array[rightIndex];
            
            while (leftIndex < rightIndex && array[leftIndex] < key) {
                leftIndex++;
            }
            //把左边大于基数的那个数填到上边空出的那个位置
            array[rightIndex--] = array[leftIndex++];
        }
        //将 key 放回剩余的坑中
        array[rightIndex] = key;
        return rightIndex;
    }

• 方法3：前后遍历法：

设置两个指针，依次往后遍历，当遇到 > 基准值的时候，让 separateIndex下标不动，i 继续遍历，遍历到 < 基准值的时候，交换两下标的值，最后交换 separateIndex 的前一个值和基准的值

    private static int doublePointer(long[] array, int lowIndex, int highIndex) {
        int separateIndex = lowIndex + 1;
        for (int i = lowIndex + 1; i <= highIndex; i++) {
            if (array[i] < array[lowIndex]) {
                swap(array,i,separateIndex);
                separateIndex++;
            }
        }
        swap(array,lowIndex,separateIndex - 1);
        return separateIndex - 1;
    }
    private static void swap(long[] array,int index1,int index2) {
        long t = array[index1];
        array[index1] = array[index2];
        array[index2] = t;
    }

性能分析：
每一次 partition 时间复杂度是 O(n)，一共多少层，看二叉树的高度（二叉树一般是 log(n)，最坏是 n）

不稳定

快排优化：

• 1、partition 挖坑（小细节优化）
• 2、数量比较少的时候，不是最快（当区间的个数低于某个阈值时（16），使用插排）
• 3、优化选择特殊的数的方式
  （1）随机数
  （2）挑几个数，选大小为中间值的（三数取中）
• 4、把相等的值特殊处理

7、归并排序：（重点）

分治法 思想：

• 1、把数组平均分成两份。分别对左右两个区间，进行相同方式处理（归并排序），直到区间内个数（size = 0 / 1）
• 2、合并左右两个有序数组

代码实现：

    public static void mergeSort(long[] array) {
        mergeSortInternal(array,0,array.length);
    }
    //区间范围时左闭右开的
    // array[lowIndex,highIndex ]
    private static void mergeSortInternal(long[] array, int lowIndex, int highIndex) {
        int size = highIndex - lowIndex;
        if (size <= 1) {
            return;
        }
        int midIndex = (highIndex + lowIndex) / 2;
        // 左区间：[lowIndex,midIndex)
        // 右区间：[midIndex,highIndex)
        mergeSortInternal(array,lowIndex,midIndex);
        mergeSortInternal(array,midIndex,highIndex);
        // 左右两个区间有序，进行合并
        mergeOrderedIntervals(array,lowIndex,midIndex,highIndex);
    }
    // 新建一个额外数组，将需要合并的两个数组中依次取出元素进行比较，在放入额外数组中
    private static void mergeOrderedIntervals(long[] array, int lowIndex, int midIndex, int highIndex) {
        int size = highIndex - lowIndex;//新数组长度
        long[] extra = new long[size];
        int leftIndex = lowIndex;//左边数组的下标
        int rightIndex = midIndex;//右边数组的下标
        int i = 0;//新数组下标
        // 两个数组中都有元素
        while (leftIndex < midIndex && rightIndex < highIndex) {
            // <= 保证稳定性
            if (array[leftIndex] <= array[rightIndex]) {
                extra[i] = array[leftIndex];
                leftIndex++;
            } else {
                extra[i] = array[rightIndex];
                rightIndex++;
            }
            i++;
        }
        // 已经有数组空了，则将另外一个数组全部放入新数组中
        if (leftIndex < midIndex) {
            //右边数组为空
            while (leftIndex < midIndex) {
                extra[i++] = array[leftIndex++];
            }
        } else {
            //左边数组为空
            while (rightIndex < highIndex) {
                extra[i++] = array[rightIndex++];
            }
        }
        //在将原数组中的值换为新数组的值
        for (int j = 0; j < size; j++) {
            array[lowIndex + j] = extra[j];
        }
    }

性能分析：

稳定

扩展：

排序算法都是在内存中进行的，当出现 海量数据 时，内存存不下，必须借助硬盘，采用归并排序（多路归并）

步骤：

• 1、先将数据平均分为 n 份（每份的大小较小）
• 2、分别对每份数据进行排序
• 3、至此，得到 n 个分别有序的数据文件
• 4、借助内存，进行 n 个有序数据文件的合并
  （1）将每份文件中最小的数放入内存中
  （2）将最小的数选出来，尾插到最后的有序文件中

n 多个数据以文件的形式放到磁盘上，把每个数据的第一个数选出来作为代表放到内存中，比较，谁小就放到最终的结果文件中，尾插进去

排序总结：