Java 数据结构与算法 插入类排序：直接插入排序、希尔排序

我们常见的排序算法有：

 先介绍插入的排序。其中，希尔排序是直接插入排序的优化。

直接插入排序

    直接插入排序是比较简单的排序，把待排序的记录按照值得大小一个一个插入到已经排好序的有序序列中，一直到全部插入完成。就类似于我们玩扑克的时候整牌的时候的插入牌。

    当第i个元素插入的时，从0到i-1下标的元素已经排好序，这个时候第i个元素和前面的元素比较，找到合适的地方后插入。比如排序数组{ 2，4，1，5，6，3 }。

  代码如下：

    public void insertSort(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 {
                    //没有排序的时候，说明前面的排好了，可以直接结束
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

直接插入排序总结：

（1）元素越接近有序，直接插入排序的效率越高；

（2）直接插入排序的时间复杂度：最好情况下O(n)，最坏情况下O(n^2)；

（3）空间复杂度：O(1)

（4）稳定性：稳定

希尔排序

    又称缩小增量排序。是直接插入排序的优化。整个过程中，先选定一个整数，把待排序中所有记录分成组，所有距离为记录的分为一组，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当分组达到1 时，所有记录在统一组内排好序。

    希尔排序只需要对直接插入排序进行一些改动。当分组是1的时候，希尔排序实现的就是直接插入排序。代码如下：

    public void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            shell(array, gap);
            gap /= 2;
        }
        shell(array, 1);
        
    }
    
    private void shell(int[] array, int gap) {
        for (int i = 1; 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 {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

希尔排序总结：

（1）希尔排序是对直接插入排序的优化；

（2）当代码中的gap>1，都是希尔排序的预排序，都是为了让数组更有序。当gap==1时，才是真正的排序；

（3）由于gap的取值是不确定的，所以希尔排序的时间复杂度一般在O(n^1.25)~O(1.6n^1.25);

（4）希尔排序是不稳定的排序。

    介绍完插入类的排序，介绍选择类的排序。选择排序每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。有直接选择排序和堆排序。

直接选择排序

    从数组i下标到len-1下标中选择一个最大或最小的元素，如果它不是最后一个元素，则直接和最后一个交换，然后在剩下的数组集合中重复，一直到集合剩余一个元素。

    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            swap(array, minIndex, i);
        }
    }
 
    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

直接选择排序特性：

（1）直接选择排序好理解，但是效率不高，实际中很少使用；

（2）时间复杂度：O(N^2)；

（3）空间复杂度：O(1)；

（4）稳定性：不稳定

堆排序

    堆排序是利用堆这种数据结构来排序的排序算法，是选择排序的一种。在进行堆排序之前，要先建立堆，堆有大堆和小堆之分。建立堆后，在进行堆排序。从小到大排序，需要建立大堆；从大到小排序，需要建立小堆。

  

class Heap {
 
    //堆排序的元素
    private int[] elem;
    private int usedSize;
 
    public Heap() {
        this.elem = new int[10];
    }
 
    //创建堆
    public void create(int[] array) {
        //对元素进行拷贝
        System.arraycopy(array, 0, this.elem, 0, array.length);
        this.usedSize = array.length;
        //创建堆
        //从整个数组的一半取整开始创建,一直到0下标结束
        for (int i = (this.usedSize - 1 - 1) >>> 1; i >= 0; --i) {
            //每一次都要进行向下调整
            shiftDown(i, this.usedSize);
        }
 
    }
 
    //向下调整
    private void shiftDown(int root, int len) {
        //从数组的一半开始创建的,所以这里的root是父节点
        int parent = root;
        //父节点的左孩子节点下标是2*i+1
        int child = (parent << 1) + 1;
 
        //进行调整
        //每一次调整都有可能导致大根堆的某一个节点不满足,需要多次调整
        //调整的过程中,孩子节点的下标不可能超过整个数组长度
        while (child < len) {
            //寻找左右孩子的最大值和父节点进行交换
            //寻找的前提是要有右孩子存在
            //右孩子最大值是不可能超过整个数组的长度的,超过说明没有右孩子
            if (child + 1 < len && this.elem[child] < this.elem[child + 1]) {
                //右孩子比左孩子值大,就加1
                ++child;
            }
 
            //找到右孩子,和父节点比较,比父节点大,就进行交换
            if (this.elem[parent] < this.elem[child]) {
                swap(parent, child);
                //一次交换完成,就更新父节点和孩子节点的值,进行下一轮调整
                //父节点到孩子节点上,孩子节点仍然是2*i+1
                parent = child;
                child = (parent << 1) + 1;
            } else {
                //没有交换,说明是大根堆
                break;
            }
 
        }
    }
 
    //交换
    private void swap(int i, int j) {
        int tmp = this.elem[i];
        this.elem[i] = this.elem[j];
        this.elem[j] = tmp;
    }
 
    //堆排序
    public void heapSort(int[] array) {
        //先创建堆,在进行排序,可以不写这一步
        create(array);
        //创建堆后,要进行升序还是降序排序
        //从小到大排序,使用大根堆
        //从大到小排序,使用小根堆
        //堆排序是倒着排的,从小到大的排序在堆中排序是先把大的放在后面,然后从后往前排序,看起来就像是倒序的从大到小排序
        //从小到大排序,在堆中,相当于倒序的从大到小排序,使用大根堆,堆顶的元素是最大的,放在当前的后面后就固定它
        //最后的结果是从堆顶到堆尾,堆顶的值是最小的,到堆尾就是最大的
 
        //堆的主要操作就是向上调整和向下调整
 
        //从最后一个元素开始排序
        //堆排序建立了大根堆,堆顶一定是当前最大的,要把堆顶和堆尾进行交换,这里使用从小到大排序
        int end = this.usedSize - 1;
        while (end > 0) {
            //交换堆顶和堆尾
            swap(0, end);
            //从0下标开始调整到end,不能调整后面的
            shiftDown(0, end);
            --end;
        }
 
        //调整好的数组拷贝到原来的数组中
        System.arraycopy(this.elem, 0, array, 0, this.usedSize);
    }
}

 堆排序性质：

（1）时间复杂度：O(N*logN)；

（2）空间复杂度：O(1)；

（3）稳定性：不稳定。