【基本思想】

归并排序是分治策略的一个非常典型的应用，其基本思想是将 $n$ 个待排序的记录看成是 $n$ 个长度为 $1$ 的有序序列，然后两两进行归并，第一轮得到 $\frac{n}{2}$ 个长度为 $2$ 的有序序列，第二轮得到 $\frac{n}{4}$ 个长度为 $4$ 的有序序列，以此类推，直到得到一个长度为 $n$ 的有序序列

归并排序的核心是归并操作，即将两个已经排序的序列合并成一个序列的操作，其步骤如下：

【基本思想】

快速排序对冒泡排序的一种改进，在冒泡排序中，记录的比较与移动是在相邻位置进行的，记录每次交换只能后移一个位置，因而总的比较次数与移动次数较多；而在快速排序中，记录的比较与移动是从两端向中间进行的，关键码较大的记录一次就能从前面移动到后面，关键码较小的记录一次就能从后面移动到前面，由于记录移动的距离较远，从而减少了总的比较次数与移动次数

快速排序利用了分治策略，其基本思想是：首先选一个轴值，作为比较的基准，将待排序记录划分为独立的两部分，左侧记录均小于等于轴值，右侧记录均大于等于轴值，然后分别对这两部分重复上述过程，直至序列有序

【基本思想】

鸡尾酒排序也称双向冒泡排序、定向冒泡排序，是原始冒泡排序的改进

双向冒泡排序与冒泡排序的不同在于其从低到高比较，然后再从高到低比较，如此循环往复，直到序列有序，而冒泡排序仅是从低到高的去比较序列中的每个元素

【基本思想】

原始冒泡排序是交换排序中最简单的排序方法，其基本思想是：两两比较相邻记录的关键码，若反序则交换，直到没有反序为止

原始冒泡排序的具体的排序过程如下：

【基本思想】

堆排序利用了堆这一数据结构来进行排序，其基本思想是：将待排序的记录构成堆，然后不断将堆顶元素移走，并将剩余的记录调整成堆，直到堆空

对于大根堆来说，其堆排序结果为降序序列，对于小根堆来说，其堆排序结果为升序序列

【概述】

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

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

【基本思想】

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

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

【基本思想】

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

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

【基本思想】

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

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

【基本思想】

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

其排序过程为：