算法概念

任何被明确定义的计算过程可以称作算法，它将某个值活一组值作为输入，并产生莫格值或一组值作为输出。所以算法可以被称作将输入转为输出的一系列的计算步骤。

这样的概况是比较抽象和标准的，其实说白了就是步骤明确的解决问题的方法。由于是在计算机中执行，所以通常先用伪代码表示，清晰的表达出思路和步骤。这样真正执行的时候，就可以使用不同的语言来实现出相同的兄啊过给。

概况的说，算法就是解决问题的工具。在描述一个算法时，我们关注的是输入与输出。也就是说只要把原始数据和结果描述清楚了，那么算法所作的事情也就清楚了。

在设计一个算法时也是需要先明确我们有什么和我们要什么。

在这里插入图片描述

插入排序介绍

插入排序得基本思路是每次插入一个元素，每一趟完成对待插入元素得放置，直到全部插入完成。

直接插入排序
直接插入排序是一种最简单得排序方法，过程就是将每个待排元素逐个插入到已经排号得有序序列中。
折半插入排序
由于在插入排序的过程中，已经生成了一个（排好的元素组成）有序数列。所以插入待排元素时可以使用折半查找的方式，更快速的确定新元素的位置，当元素个数较多时，折半插入排序优于直接插入排序。
希尔排序
希尔排序可以看作是分组排序的排序方法。把全部元素分成几组（等距元素分到一组），在每一组内进行直接插入排序。然后继续减少间距，形成新的分组，进行排序，直到间距为1时停止。

希尔排序

输入
n个数的序列，通常直接存放再数组中，可能是任何顺序。
输出
输入序列的一个新排列，满足从小到大的顺序（默认讨论升序，简单的修改就可以实现降序排列）
算法说明
希尔排序也称缩小增量排序，是直接插入排序的一种改进算法，更为高效。希尔排序的核心思想是先将数据进行分组，在每个分组中进行直接插入排序。通过不断的更改增量，得到新的分组，在每个组中再进行直接插入排序，直到增量减少至1，最后一次对所有的集合元素进行一次直接插入排序。
由于在前几次的分组和排序中，已经调整了元素的位置，所以最后一次的元素串位次数会大大减少。在分组的过程中，增量d不断变化，通常第一个增量的选取不会超过n/2（这样每组中至少有两个元素），然后每次减半，直到增量为1.如果这样调节增量，则分组排序可以在不超过 log2n的情况下，完成操作。
算法流程

与直接插入排序不同的是，每次分组排序后，整体序列更加接近有序，但是不产生有序区。可以看到，在分组中的每次排序，都是把较小的数尽量往左侧丢，因为组内的数据量较小，这样就能有效的减少数据串位的词素，在最后一次的调整时就可以减少数据的串位次数和串位距离。

伪代码

希尔排序中也用到了直接插入排序算法，伪代码如下：

d = A.length / 2
while d > 0
    for i = 1 to d
        for j = i + d to A.length by d
            tmp = A[j]
            k = j - d
            while k > 0 and A[k] > tmp
                A[k + d] = A[k]
                k = k - d
            A[k + d] = tmp
    d = d / 2

十分重要：本代码中固定了d的变换规律为每次取一半，实际上并不是固定的，对于不同的数据集使用不同的增量序列会收获不同的效果，增量序列也会直接影响到算法的执行效率。

最外层的while循环控制一共执行几趟排序，取决于d的变化
第一层for循环用于控制在每个分组中要执行的操作
第二层for循环就是我们之前熟悉的直接插入排序代码

算法实践

输入数据：11，34，20，10，12，35，41，32，43，14

java源码

public class ShellSort {

    public static void main(String[] args) {
        // input data
        int[] a = {11,34,20,10,12,35,41,32,43,14};
        // 初始化增量
        int d = a.length / 2;
        // 控制每一次的分组排序
        while (d > 0){
            // 控制每一组内的直接插入排序
            for (int i = 0;i < d;i++){
                // 组内进行直接插入排序
                for (int j = i + d;j < a.length;j+=d){
                    int tmp = a[j];
                    int k = j - d;
                    while(k > 0 && a[k] > tmp){
                        a[k + d] = a[k];
                        k = k -d;
                    }
                    a[k + d] = tmp;
                }
            }
            // 增量按一定规律每次变化
            d = d / 2;
        }
        // 查看排序结果
        for (int data : a){
            System.out.print(data + "\t");
        }
    }

}