1、次序查找的头脑：
将待查找的关键字为key的元素重新到尾与表中元素举行比力，如果中心存在关键字为key的元素，则返回乐成；否则，则查找失败。
2、二分法查找的根本头脑是：（设R[low,…,high]是当前的查找区)
（1）确定该区间的中点位置：mid=L(low+high)/2˩；
（2）将待查的k值与R[mid].key比力，若相当，则查找乐成并返回此位置，否则需确定新的查找区间，继承二分查找，详细方法如下。若R[mid].key＞k，则由表的有序性可知R[mid,…,n].key均大于k，因此若表中存在关键字便是k的结点，则该结点肯定是在位置mid左边的子表R[low,…,mid–1]中。因此，新的查找区间是左子表R[low,…,high]，此中high=mid–1。若R[mid].key<k，则要查找的k必在mid的右子表R[mid+1,…,high]中，即新的查找区间是右子表R[low,…,high]，此中low=mid+1。若R[mid].key=k，则查找乐成，算法竣事。
（3）下一次查找是针对新的查找区间举行，重复步调（1）和（2）。
（4）在查找过程中，low渐渐增长，而high渐渐镌汰。如果high<low，则查找失败，算法竣事。
折半查找在查找乐成时关键字的比力次数最多为 L log2n +1 ˩ 次。
折半查找的时间复杂度为 O(log2n)次。
3、散列表查找的根本头脑是：已知关键字聚集U，最大关键字为m，筹划一个函数Hash，它以关键字为自变量，关键字的存储所在为因变量，将关键字映射到一个有限的、所在连续的区间T[0..n-1](n<<m)中，这个区间就称为散列表，散列查找中利用的转换函数称为散列函数。
开放定址法是指当构造散列表发生辩论时，利用某种探测本领，产生一个探测的散列所在序列，而且逐个查找此所在中是否存储了数据元素，如果没有，则称该散列所在开放，并将关键字存入，否则辩论，继承查找下一个所在。
4、排序分类
5、直接插入排序：即当插入第i个记录时，R1，R2，…，Ri-1均已排好序，因此，将第i个记录Ri依次与Ri-1，…，R2，R1举行比力，找到符合的位置插入。它简朴明确，但速率很慢。
注：对于根本有序的序列，选择直接插入排序方法，时间复杂度近乎线性为：O(n)。
6、希尔（Shell）排序：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。全部间隔为dl的倍数的记录放在同一个组中。先在各组内举行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt–l<O<d2<d1)，即全部记录放在同一组中举行直接插入排序为止。该方法实质上是一种分组插入方法。
7、直接选择排序的过程是，首先在全部记录中选出排序码最小的记录，把它与第1个记录互换，然后在别的的记录内选出排序码最小的记录，与第2个记录互换……依次类推，直到全部记录排完为止。
8、堆排序
（1）堆的界说：设有n个元素的序列{K1，K2，…，Kn}，当且仅当满意下述关系之一时，称之为堆。
(i) Ki≤K2 i 且Ki≤K2 i +1；
(ii) Ki≥K2 i 且Ki≥K2 i +1 。
此中(i)称为小顶堆，(ii)称为大顶堆。
（2）堆排序的根本头脑为：先将序列创建堆，然后输出堆顶元素，再将剩下的序列创建堆，然后再输出堆顶元素，依此类推，直到全部元素均输出为止，此时元素输出的序列就是一个有序序列。
（3）堆排序的算法步调如下(以大顶堆为例)：
(i)初始时将次序表R[1..n]中元素创建为一个大顶堆，堆顶位于R[1]，待序区为R[1..n]。
(ii)循环实验步调3～步调4，共n-1次。
(iii)假设为第i 运行，则待序区为R[1..n-i+1]，将堆顶元素R[1]与待序区尾元素R[n-i+1]互换，此时顶点元素被输出，新的待序区为R[1..n-i ]。
(iv)待序区对应的堆已经被粉碎，将之重新调解为大顶堆。
（4）堆排序时间复杂度为：O(nlog2n)，是不稳固的排序。
9、冒泡排序的根本头脑是，通过相邻元素之间的比力和互换，将排序码较小的元素渐渐从底部移向顶部。由于整个排序的过程就像水底下的气泡一样渐渐向上冒，因此称为冒泡算法。
10、快速排序接纳的是分治法，其根本头脑是将原题目分解成若干个规模更小但结构与原题目相似的子题目。通过递归地办理这些子题目，然后再将这些子题目标解组合成原题目标解。
快速排序通常包罗两个步调：
第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将全部记录都分成两组，第1组都小于该数，第2组都大于该数，如图所示。
第二步，接纳雷同的方法对左、右两组分别举行排序，直到全部记录都排到相应的位置为止。
11、归并也称为归并，是将两个或两个以上的有序子表归并成一个新的有序表。若将两个有序表归并成一个有序表，则称为二路归并。归并的过程是：比力A和A[j]的排序码大小，若A的排序码小于便是A[j]的排序码，则将第一个有序表中的元素A复制到R[k]中，并令i和k分别加1；云云循环下去，直到此中一个有序表比力和复制完，然后再将另一个有序表的剩余元素复制到R中。
12、基数排序是一种借助多关键字排序头脑对单逻辑关键字举行排序的方法。基数排序不是基于关键字比力的排序方法，它得当于元素许多而关键字较少的序列。基数的选择和关键字的分解是根据关键字的范例来决定的，例如关键字是十进制数，则按个位、十位来分解。 |
