【概述】

二分查找（Binary Search），又称折半查找，其仅适用于有序的顺序表或数组，不适用于链表

其算法的基本思想是：将给定关键字 key 与表中中间位置的元素对应的关键字进行比较，中间结点由此将查找表分为两个子表，若相等，则查找成功，若不相等，根据关键字 key 与该中间结点关键字的比较结果来确定下一步查找哪一个子表，这样递归进行，直到查找成功或查找结束发现表中没有这样的结点

【基本思想】

简单选择排序是选择类排序中简单的一种，其基本思想是：第 $i$ 趟排序在待排序列 $a[i]$~$a[n]$ 中选取关键码最小的记录，这样每一趟确定第 $i$ 个元素，$n-1$ 趟即可排序完成

简单选择排序的具体的排序过程如下：

【基本思想】

对于直接插入排序，当待排序列为正序时，其时间复杂度可提高到 $O(n)$，故而其更适用于基本有序或数据量不大的排序表，针对这两点，对直接插入排序进行改进，即希尔排序

所谓基本有序，就是小的关键字基本在前，大的关键字基本在后，但基本有序的条件十分苛刻，难以达到，为了达到基本有序，采用跳跃分割策略，即将相距某个增量的记录组成一个子序列，这样保证子序列内分别进行直接插入排序得到的结果是基本有序而非局部有序

【基本思想】

在直接插入排序中，每趟插入过程都进行了两项工作：

• 从有序子表中查找待插入元素应被插入位置
• 给插入位置腾出空间，将待插入元素复制到表中插入位置

【基本思想】

直接插入排序是最简单、最直观的插入类排序算法，其是一种稳定的排序方法，类似于玩扑克时整理手牌的过程

其排序过程为：

排序，即重新排列表中的元素，使表中元素满足按关键字有序的过程

对于待排序表中的两个元素 $R_i$ 和 $R_j$，若排序前后 $R_i$ 和 $R_j$ 的相对位置不变，则称排序算法是稳定的，否则是不稳定的，稳定与不稳定是对算法性质的描述，若待排序表中的元素唯一，则选择排序算法时稳定与否无关紧要

在排序过程中，根据数据元素是否完全在内存中，可将排序算法分为两类：