标签（空格分隔）： 排序算法
1. 小的子文件
由于快速排序会递归的调用自身的许多小文件，因而要对小的子文件尽可能使用高效的算法 直观来想即，if(r-l <= M) insertion(a, l, r);，M为子文件规模的阈值。
而一种更高效的实现方式是，在快速排序过程中直接忽略小的子文件， if(r-l <= M) return; 在快速排序完成后，再进行一次整个数组的插入排序。即使子文件的阈值设置较大，因为只有极少数的文件进行了划分操作，所以快速排序部分运行很快；而插入排序操作的对象是几乎有序的文件，所以插入排序部分运行也很快。这个忽略小文件技术无论何时都适用于递归算法,因为本质在于，我们确信所有递归算法在执行小问题实例时会占据时间的大部分。因而可以采用一些混合算法改进总的运行时间。
具体程序上的改进，参见三者取其中的程序实现
2. 三者取其中划分
对快速排序的另一项改进，即使用一个尽可能在文件中间划分的划分元素（避免最坏情况）：对此有2种办法，一种是采用数组中的一个随机元素，，但是在实际应用中不可能使用随机数生成器； 而简单的随意选择可能也是高效的,因此可得到我们另一种划分元素的方法：
从文件中取出三个元素，使用三个元素的中间元素作为划分元素。取数组的最左右两边的元素a[l] a[r]和中间位置的元素a[(l+r)/2]，对这三个数排序，用a[r-1]和a[(l+r)/2]交换，然后对（l+1, r-1） 的数组进行划分，这一改进成为三者取中法 。
/*=================三者取其中 快速排序 （需要最后使用插入排序）=======================*/void quick_sort_middle(Item a[], int l, int r){if(r-l <= M) //小于M的文件不排序，最后统一用插入排序return;exch(&a[r-1], &a[(l+r)/2]);//三交换法对这3个元素排序comp_exch(&a[l], &a[r-1]);comp_exch(&a[l], &a[r]);comp_exch(&a[r-1], &a[r]);int i = partation(a, l+1, r-1);//a[l]<a[r-1], a[r]>a[r-1]quick_sort_middle(a, l, i-1);quick_sort_middle(a, i+1, r);}3. 重复关键字
带有大量重复关键字值使用基本的快速排序性能会极其低效。 直观想是将文件分为3部分： 三路划分法：将标准的划分作如下改动，扫描时将遇到左子文件中和划分元素相等的元素放在文件的最左边，遇到右子文件中和划分元素相等的元素放在文件的最右边。最后在将左右相等的关键字交换到中间，此时，这些元素都已经在最终位置，从递归调用中去除它们。
/*==========三路法快速排序–可适用于重复关键字（需要最后使用插入排序）=========*/void quick_sort_3_way(Item a[], int l, int r)//划分操作已经包含在此函数中{if(r-l <= M)return;int i, j, p, q;i = l-1, j = r;p = l, q = r;Item v = a[r];for(;;){while(less(a[++i], v));while(less(v, a[–j]))if(j == l)(j <= i)break;exch(&a[i], &a[j]);//交换和划分元素相等的元素到左右两边if(a[i] == v)exch(&a[i], &a[p++]);if(a[j] == v)exch(&a[j], &a[q–]);}exch(&a[i], &a[r]);//将相等元素交换到文件中间i = i-1, j = i+1;for(int k = l; k < p; k++, i–)exch(&a[k], &a[i]);for(int k = r; k > q; k–, j++)exch(&a[k], &a[j]);//递归处理子文件quick_sort_3_way(a, l, i);//此时i所处的位置如图1所示quick_sort_3_way(a, j, r);}4. 上述三个部分完整程序
参考资料：《算法：C语言实现》P201
对于旅行，从来都记忆模糊。记不得都去了哪些地方，
