持续创造，加速成长！这是我参与「日新方案 10 月更文挑战」的第27天，点击查看活动概略

算法概念

任何被明晰界说的核算进程能够称作算法，它将某个值活一组值作为输入，并产生莫格值或一组值作为输出。所以算法能够被称作将输入转为输出的一系列的核算进程。

这样的概略是比较笼统和标准的，其实说白了便是进程明晰的解决问题的办法。由所以在核算机中履行，所以一般先用伪代码表明，明晰的表达出思路和进程。这样真实履行的时分，就能够运用不同的语言来完成出相同的兄啊过给。

概略的说，算法便是解决问题的工具。在描述一个算法时，咱们重视的是输入与输出。也便是说只要把原始数据和成果描述清楚了，那么算法所作的工作也就清楚了。

在规划一个算法时也是需求先明晰咱们有什么和咱们要什么。

相关概念

数据结构

算法经常会和数据结构一同呈现，这是由于关于同一个问题，运用不同的数据结构来存储数据，对应的算法或许千差万别。 所以在整个学习进程中，也会涉及到各种数据结构的运用 常见的数据结构包含：

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

算法的效率

在一个算法规划完结后，还需求对算法的履行状况作一个评价。一个好的算法，能够大幅度的节约资源消耗和时刻。在进行评价时不需求太具体，究竟数据量是不确认的，一般是以数据量为基准确认一个量级。

一般会运用到两个概念：

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

时刻复杂度

一般把算法中的根本操作重复履行的频度称为算法的时刻复杂度。算法中的根本操作一般是指算法中最深层循环内的句子（赋值、判别、四则运算等基础操作）。咱们能够把时刻频度记为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

​