算法概念

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

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

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

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

相关概念

数据结构

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

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

算法的效率

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

通常会使用到两个概念：

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

时间复杂度

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

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

空间复杂度

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

插入排序介绍

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

• 直接插入排序

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

• 折半插入排序

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

• 希尔排序

希尔排序可以看作是分组排序的排序方法。把全部元素分成几组（等距元素分到一组），在每一组内进行直接插入排序。然后继续减少间距，形成新的分组，进行排序，直到间距为1时停止。

折半插入排序

• 输入

n个数的序列，通常直接存放在数组中，可能是任何顺序

• 输出

输入序列的一个新排列，满足从小到大的顺序（默认讨论升序，简单的修改可以实现降序排列）。

• 算法说明

每次从原有数据中取出一个数，插入到之前已经排号的序列中，直到所有的数全部取完，那么新的有序排列也就完成了。这个过程与直接插入排序十分类似，不同的地方在于插入时如何寻找位置。

1 直接插入排序：从后（排好的最后一个元素）至前逐一比较寻找位置。
2 折半插入排序：利用已排好的元素有序的特点，使用折半查找的方式快速确定位置。

-算法流程

1 输入数据集被分为有序区和无序区两部分
2 最初有序区没有元素，从无序区不断取出元素放入，保证放入的元素均已有序。
3 已知前i个元素已排好（下标从0至i-1），从无序区取出第一个元素（数据集的第i+1个元素）
4 先与有序区的最后一个元素比较

如果较大则代表该元素已经在合适位置，则直接归入有序区，进入下一个元素的判断
如果较小则需要进一步确定位置，执行一下步骤。

5 搜索区间为从low至high，初始区间为整个有序区（从0至i-1）
6 将待插入元素记录在临时变量tmp中，为后续元素串位做准备
7 计算 mid = （low+high）/2，将该位置的元素与R[i]比较
8 不断的缩小搜索区间，直到确定插入位置（原理与折半查找相同）
9 确定位置后，将有序区中的元素从后至前逐个后串，最后将tmp中的值覆盖到插入位置。

伪代码

折半插入排序可以看做是将直接插入排序与折半查找两种算法进行结合，排序的思路与直接插入排序相同，只是在确定插入位置时借助了折半查找的方法

for i = 2 to A.length
    if A[i]<A[i-1]
        tmp = A[i]
        low = 0 
        high = i -1
        while low <= high
            mid = (low+high)/2
            if A[mid]>tmp
                high = mid - 1
            else
                low = mid +1
        for j= i -1 down to high +1
            A[j+1]=A[j]
        A[high + 1] = tmp

由于不会出现重复元素，所以最后一定会将搜索区间缩小至low与high重合（左右区间端点不断移动）。在最后一次循环时，low、high的值相同，在比较完成后，left与right发生交错，相差为1，此时要选择一个变量的值作为新插入元素的位置参照。

需要明确的是，最后一个比较时不会出现左端点向左移，或右端点向右移的情况，因为在上一次比较时，待插入元素必定是能够落在low与high区间内的，这就决定了tmp一定大于low的元素，小于high对应得元素

并且由于mid得计算方法，最后一次比较是tmp与low对应元素得比较，并且tmp是较大得，此时进入else分支，并且我们知道最终得插入位置应该放在最后比较元素得后一个位置，也就是mid对应位置得后面，所以是mid+1

如果用low 表示，就刚好是low，如果用high表示，则应该是high+1

​