五、希尔排序

　　主要思路是：

　　先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。由于希尔排序是对相隔若干距离的数据进行直接插入排序，因此可以形象的称希尔排序为“跳着插”。

六、归并排序

　　主要思路是：

　　当一个数组左边有序，右边也有序，那合并这两个有序数组就完成了排序。如何让左右两边有序了？用递归！这样递归下去，合并上来就是归并排序。

　　代码实现

　　void merge（int arr[]， int temp_arr[]， int start_index， int mid_index， int end_index）

　　{

　　int i = start_index， j = mid_index + 1;

　　int k = 0;

　　while （i < mid_index + 1 && j < end_index + 1）

　　{

　　if （arr[i] > arr[j]）

　　temp_arr[k++] = arr[j++];

　　else

　　temp_arr[k++] = arr[i++];

　　}

　　while （i < mid_index + 1）

　　{

　　temp_arr[k++] = arr[i++];

　　}

　　while （j < end_index + 1）

　　temp_arr[k++] = arr[j++];

　　for （i = 0， j = start_index; j < end_index + 1; i ++， j ++）

　　arr[j] = temp_arr[i];

　　}

　　void merge_sort（int arr[]， int temp_arr[]， int start_index， int end_index）

　　{

　　if （start_index < end_index）

　　{

　　int mid_index = （start_index + end_index） / 2;

　　merge_sort（arr， temp_arr， start_index， mid_index）;

　　merge_sort（arr， temp_arr， mid_index + 1， end_index）;

　　merge（arr， temp_arr， start_index， mid_index， end_index）;

　　}

　　}七、堆排序

　　堆排序的难点就在于堆的的插入和删除。

　　堆的插入就是——每次插入都是将新数据放在数组最后，而从这个新数据的父结点到根结点必定是一个有序的数列，因此只要将这个新数据插入到这个有序数列中即可。

　　堆的删除就是——堆的删除就是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点开始将一个数据在有序数列中进行“下沉”。

　　因此，堆的插入和删除非常类似直接插入排序，只不是在二叉树上进行插入过程。所以可以将堆排序形容为“树上插”。