如何优化冒泡排序和快排？

冒泡排序的优化： 1：加入哨兵 2：记住每一次交换的最后位置，该位置以后的为有序，不需要改变。

快排的优化：
	1.当待排序序列的长度分割到一定大小后，使用插入排序。原因:对于很小和部分有序的数组，快排不如插排好。当待排序列的长度分割到一定大小后， 继续分割的效率比插入排序要差，此时可以使用插排而不是快排。

	2.在一次分割结束后，可以把与Key相等的元素聚在一 起，继续下次分割时，不再对与key相等元素分割。具体过程：在处理过程中，会有两个步骤:
 第一步，在划分过程中，把与key相等元素放入数组的两端。
 第二步，划分结束后，把与key相等的元素移到枢轴周围。

	3.三数取中:中轴数的选取:最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值,也就是第N/2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上,随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数中值分割法消除了预排序输入的不好情形，并且减少快排大约14%的比较次数。

	4.优化递归操作
快排函教在函数尾都有两次递归操作，我们可以对其使用尾递归优化。
优点:如果待排序的序列划分极端不平衡，递归的深度将趋近于n,而栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。优化后，可以缩减堆栈深度，由原来的O(n)缩减为logn。

概括：这里效率最好的快排组合是：三数取中+插排+聚集相等元素，它和STL中的Sort函数效率差不多。

转载于:https://my.oschina.net/u/4167465/blog/3076875