/**
 * 元素集合越接近有序，直接插入排序算法的时间效率越高
 * 时间复杂度为O(N^2)
 * 空间复杂度为O(1)
 * 稳定性：稳定的排序
 * @param array
 */
public static void insetSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                }else {
                    array[j + 1] = tmp;
                    break;
                }
            }
            //这是当我们的 j < 0的时候呢，
            //我们退出循环之后相当于 j+1 为0下标
            array[j + 1] = tmp;
        }
    }

我们来看看运行的结果：

说明这个直接插入排序没有任何的问题。

➷ 2、希尔排序：

☞ 希尔排序的基本思想：

希尔排序又称缩小增量法。基本思想就是：先选定一个整数 gap，把待排序的数据分成多个组，所有距离为指定记录的分在同一个组中，对每一个组内的记录进行排序，之后重复上述的过程直至我们的 gap == 1 的时候，所有记录在同一组内排序，就完成了希尔排序了。

☞ 希尔排序的实现：

▶ 思路：

其实我们的分组排序就是相当于我们的在每一个组中进行插入排序。

不管我们最开始如何的分组，最后一定是变成一组数据，进行插入排序。我们在介绍插入排序的时候，是不是说过数据越有序就排的越快，所以我们的在最后一次排序之前都是在尽量的把数据变成有序的，就相当于是预排序的。

我们来看看这个是如何进行的分组排序的，我们在直接插入排序的时候呢，我们的 i 是从1下标开始的，这里呢为我们的 i 下标从 gap 开始，之后我们的 j 下标就是 i - gap 就是 j 下标，这里的 j 就是每次比较完之后都是 j - gap ，我们的每次排完之后呢，我们的 i++ 就可以了，尽管我们的一组没有排完，也是没有问题的，因为我们在 i++ 之后呢还是可以再次排到这组的。

我们来看看流程是什么样的：

由此我们可以看出，在我们的 gap = 1 之前呢，我们的预排序都是将数值大的放到了后面，数值小的放到前面，可以使我们的在最后一次排序中执行的更快。因为这样就可以趋于有序了。

我们对于 gap 这个值呢到现在为止都没有给出一个准确的一个求值方法，最后使 gap 得到 1 就可以了，我们这里直接使用 gap = gap / 2 。

我们来看看代码如何编写的：

▶ 代码：

/**
 * 时间复杂度为：O(N) 这个不是很准确的，但是比直接插入排序快
 * 空间复杂度为：O(1)
 * 稳定性：不稳定的
 * @param array
 */
public static void shellSort(int[] array) {
        int gap = array.length;
        while(gap > 1) {
            gap = gap / 2;
            shell(array,gap);
        }
}

private static void shell(int[] array,int gap) {
        //进行排序
        for (int i = gap; i < array.length; i++) {

            int tmp = array[i];
            int j = i - gap;
            for (;j >= 0;j -= gap) {

                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                }else {
                    array[j + gap] = tmp;
                    break;
                }
            }

            array[j + gap] = tmp;
        }
}

来看看运行的结果：

我们可以看到这个结果是没有问题的。

❄️三、选择排序的实现：

➷ 1、选择排序：

☞ 基本思想：

就是每次都在待排序中选择出最小的数据，存放到数据的起始位置，直到所有的待排序的数据都排完。

☞ 选择排序的实现：

▶ 思路：

我们就是把数组的第一个下标为 i 计为最小的数据把其下标放到 mixIndex，之后我们的定义一个 j 下标设为 i + 1 ，这个 j 下标的值看是不是比我们 mixIndex 的下标的值小，如果小就把其变成 mixIndex 下标，直到我们把数组遍历结束，我们再把 mixIndex 和 i 下标的值交换。一直循环这个操作直至我们的 i 大于等于我们的数组长度。

我们来看看这个操作的流程图是什么样的：

这就是我们的选择排序的流程图了，我们之后来看看我们代码如何编写：

▶ 代码：

/**
 * 选择排序
 * 时间复杂度：O(N^2)
 *     和数据是否有序有关
 * 空间复杂度：O(1)
 * 稳定性：不稳定的
 * @param array
 */
public static void selectSort(int[] array) {

       for (int i = 0; i < array.length; i++) {
            int mixIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[mixIndex]) {
                    mixIndex = j;
                }
            }
            swap(array,i,mixIndex);
        }
}

private static void swap(int[] array,int i,int mixIndex) {
        int tmp = array[i];
        array[i] = array[mixIndex];
        array[mixIndex] = tmp;
}

对于这个选择排序呢我们还有一个优化的，我们上面的代码是从一边找，我们优化呢就是从边找一边找最小值，一边找最大值，我们需要设置两个变量 left 是在数组的开头，right 在数组的结尾，开头的存放最小值，结尾的存放最大值，存放之后把left++，right--，直到它们相遇结束。

我们来看看流程图：

这里我们需要注意的问题：当我们的最大值就是left这个下标的话，当我们和最小值交换后。最大值就会找不到，所以这里要有一个判断，当我们把最小值交换后，我们的最大值在left中时候把maxIndex = minIndex，就是我们的最大值了。

这里也要注意我们的 i 的范围不能超过 right。

我们来看看优化后的代码的编写：

private static void swap(int[] array,int i,int mixIndex) {
        int tmp = array[i];
        array[i] = array[mixIndex];
        array[mixIndex] = tmp;
    }

    public static void selectSort2(int[] array) {
        //优化后的代码
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int minIndex = left;
            int maxIndex = left;

            for (int i = left + 1; i <= right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }
            //交换
            swap(array,left,minIndex);

            if (maxIndex == left) {
                maxIndex = minIndex;
            }

            swap(array,right,maxIndex);

            left++;
            right--;
        }
    }

➷ 2、堆排序：

这个排序我们上一篇博客中已经有所介绍了，这里呢我们直接来看看代码就可以了，如果对于这个代码看不懂，我们的呢可以传送到上一篇博客中：

Java-数据结构-优先级队列(堆)-(二) (ﾟ▽ﾟ*)

代码：

private static void swap(int[] array,int i,int mixIndex) {
        int tmp = array[i];
        array[i] = array[mixIndex];
        array[mixIndex] = tmp;
    }

private static void siftDown(int[] array,int parent,int length) {
        int child = (parent * 2) + 1;
        while (child < length) {
            if (child + 1 < length && array[child + 1] > array[child]) {
                child++;
            }
            if (array[parent] < array[child]) {
                swap(array,child,parent);
                parent = child;
                child = (parent * 2) + 1;
            }else {
                break;
            }
        }
    }


    private static void creatHeap(int[] array) {
        for (int parent = (array.length - 1 -1) / 2; parent >= 0 ; parent--) {
            //向下调整创建堆
            siftDown(array,parent,array.length);
        }
    }


    /**
     * 堆排序
     * 时间复杂度：O(n*logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     * @param array
     */
    public static void HeapSort(int[] array) {
        creatHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            swap(array,0,end);
            siftDown(array,0,end - 1);
            end--;
        }
    }