[数据结构与算法]深刻理解不同排序算法之间的逻辑

提示：请学习完各种排序再阅读会更深刻

一、插入排序与希尔排序

插入排序

• 排序之初，各个子数组都很短，排序之后子数组都是部分有序，这两种情况都很适合插入排序。这一特性将会与其他排序算法结合（比如下面介绍的分治算法的子数组处理），从而提高效率。

希尔排序——插入排序的升级

• 对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。
• 权衡了子数组的规模性和有序性。

二、归并排序与快速排序——分治思想

1.归并排序——利用辅助数组

• 自顶向下的归并排序——递归
  将数组分成两个，先递归处理第一个（将第一个再分成两个），另一个先不做处理。

public sort（a[]，lo，hi）
{
	mid = lo + (hi - lo) / 2;
	sort(a, lo,mid);
	sort(a, mid+1 ,hi);
	merge(a, lo ,mid,hi);
}

• 自底向上的归并排序——循环
  一次性分成若干个小数组。

public sort（a[]）
{
	for(sz = 1; sz < N;sz = sz+sz)	//sz:子数组大小
		for(lo = 0; lo < N-sz;lo += sz+sz) //lo:子数组索引
			merge(a,lo,lo+sz-1,min(lo+sz+sz-1),N-1);
}

2.快速排序——原地排序

快速排序和归并排序是互补的：

1. 归并排序将数组分成两个子数组分别排序，将有序的子数组归并以将整个数组排序。
   而快排是当两个子数组都有序时整个数组就自然有序了。
2. 归并排序，递归调用发生在处理数组之前，即sort（）在merge（）前执行。
   而快排是递归调用发生在处理数组之后，由于需要切分(partition)的位置取决于数组的内容，所以先处理数组。

pubilc sort(a[], lo ,hi)
{
	j = partition(a, lo, hi);
	sort(a, lo ,j-1);
	sort(a, j+1, hi);	
}