归并排序，快速排序，希尔排序

归并排序

原理：利用递归和分治技术将数据序列划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并成为越来越大的有序序列。

1. 划分半子表
2. 合并半子表

快速排序

原理：采用分而治之的思想，把大的拆分成小的，再把小的拆分成更小的。给定一组记录，通过一趟排序后，将原序列分为俩部分，其中前一部分的所有记录均比后一部分的所有记录小，然后再依次对前后俩部分的记录进行快速排序，递归该过程，直到序列中所有记录均有序为止。

1. 分解
2. 递归求解
3. 合并

希尔排序

原理：“缩小增量排序”，将待排序的数组元素分成多个子序列，使得我、每个子序列的元素相对较少，然后对各个子序列分别进行插入排序，待整个排序序列基本有序后，最后对所有元素进行一次直接插入排序。

1. 选择一个步长序列
2. 按步长序列个数k，对待排序序列进行k趟排序
3. 每趟排序根据对应补偿ti，将待排序序列分割成ti个子序列，分别对各个子序列进行直接插入排序。