算法概念

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

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

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

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

相关概念

数据结构

算法经常会和数据结构一起出现，这是因为对于同一个问题，使用不同的数据结构来存储数据，对应的算法可能千差万别。
所以在整个学习过程中，也会涉及到各种数据结构的使用
常见的数据结构包括：

• 数组
• 堆
• 栈
• 队列
• 链表
• 树等等

算法的效率

在一个算法设计完成后，还需要对算法的执行情况作一个评估。一个好的算法，可以大幅度的节省资源消耗和时间。在进行评估时不需要太具体，毕竟数据量是不确定的，通常是以数据量为基准确定一个量级。

通常会使用到两个概念：

• 时间复杂度
• 空间复杂度

时间复杂度

通常把算法中的基本操作重复执行的频度称为算法的时间复杂度。算法中的基本操作一般是指算法中最深层循环内的语句（赋值、判断、四则运算等基础操作）。我们可以把时间频度记为T（n），它与算法中语句的执行次数成正比。其中的n被称为问题的规模，大多数情况下为输入的数据量。

对于每一段代码，都可以转为常数或者与n相关的函数表达式，记作f（n）。如果我们把每一段代码的花费的时间加起来就能够得到一个刻画时间复杂度的表达式，在合并后保留量级最大的部分即可确定时间复杂度。

空间复杂度

程序从开始执行到结束所需要的内存量。也就是整个代码中最大需要占用多少的空间。为了评估算法本身，输入数据所占用的空间不会考虑，通常更关注运算时需要额外定义多少临时变量或多少存储结构。

插入排序介绍

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

• 直接插入排序

直接插入排序是一种最简单得排序方法，过程就是将每个待排元素逐个插入到已经排号得有序序列中。

• 折半插入排序

由于在插入排序的过程中，已经生成了一个（排好的元素组成）有序数列。所以插入待排元素时可以使用折半查找的方式，更快速的确定新元素的位置，当元素个数较多时，折半插入排序优于直接插入排序。

• 希尔排序

希尔排序可以看作是分组排序的排序方法。把全部元素分成几组（等距元素分到一组），在每一组内进行直接插入排序。然后继续减少间距，形成新的分组，进行排序，直到间距为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");
        }
    }

}

• 执行效果

10 11 12 14 20 32 34 35 41 43