冒泡排序的基础上做出的一个改进，和归并排序一样，快速排序也是一种利用分治思想的递归算法。

直接插入排序，不仅如此，因为快速排序是递归的，所以这种情况经常发生。通常的解决办法是对于小数组不使用递归的快速排序，而代之以直接插入排序等对小数组有效的排序算法。使用这种策略实际可节约大约15%(相对于不使用此策略)的运行时间，一种好的截止范围是N = 10，虽然在5到20之间任一种截止范围都有可能产生类似的结果。这种做法也避免了一些有害的退化情况，如三个元素的中值实际只有一个或两个元素的情况。

堆排序最坏时间复杂度、空间复杂度都优于快速排序，为什么实践中更多使用快排而不是堆排呢？

??（1）快速排序的过程中，访问数据是顺序进行访问的，而且有非常精练和高度优化的内部循环，但是在堆排序中，需要维护堆性质，导致需要跳着数组下标去进行访问元素，对CPU缓存不友好。

??（2）堆排序过程使用更多的比较次数，值得一提的是，对于不同的语言，比较的代价是不同的，具体可参考归并排序的分析。

??二、与归并排序的比较详情参考归并排序的分析。

堆排序结合，由于堆排序的O(NlogN)最坏时间复杂度，我们可以对几乎所有的输入都能到达快速排序的快速运行时间，该算法的最坏运行时间为O(NlogN)。

归并排序分析。

代码实现

??以下一种快速排序的实现是大量分析和经验研究的结果，它代表实现快速排序的非常有效的一种方法(三数中值分割法 + 小数组处理)，即使是对该方法最微小的偏差都可能引起意想不到的坏结果。其中一些细节地方值得读者细细品味，相信读者一定会有所收获。

// C++ 
class QuickSort {  // 快速排序类 
public:
	// 快排驱动程序1(全排序)
	vector<int> quickSort(vector<int>& nums) {   
		quicksort(nums, 0, nums.size() - 1);  // 调用私有方法quickSort排序 
		return nums;  // 返回已排序对象 
	}
	// 快排驱动程序2(部分排序)
	vector<int> quickSort(vector<int>& nums, int left, int right) {   
		quicksort(nums, left, right);  // 调用私有方法quickSort排序 
		return nums;  // 返回已排序对象 
	}
	
private:
	const int CUTOFF = 10;  // 小数组判定界限 
	// 快速排序递归函数 
	void quicksort(vector<int>& nums, int left, int right) {  
		if (left + CUTOFF <= right) {  // 判定是否为小数组 
			int pivot = median(nums, left, right);  // 选取枢纽元 
			
			int i = left;  // 左边起始位置之前 
			int j = right - 1;  // 右边起始位置之后 
			for (;;) {  // 双指针遍历 
				while (nums[++i] < pivot) { }  // 从左找到第一个大于枢纽元的值 
				while (nums[--j] > pivot) { }  // 从右找到第一个小于枢纽元的值 
				if (i < j) {  // 未完成一次遍历 
					swap(nums[i], nums[j]);  // 交换nums[i]和nums[j]的值 
				} else {  // 完成一次遍历 
					break;  // 退出循环 
				}
			}
			// 将枢纽元放在正确的位置(左边都比枢纽元小，右边都比枢纽元大)
			swap(nums[i], nums[right - 1]);
		
			quicksort(nums, left, i - 1);  // 递归排序左子序列 
			quicksort(nums, i + 1, right);  // 递归排序右子序列 
		} else {  // 小数组采用直接插入排序 
			insertionSort(nums, left, right);  // 直接插入排序 
		}
	}
	// 三数中值分割法选取枢纽元 
	int median(vector<int>& nums, int left, int right) {  
		int mid = (left + right) / 2;  // 中间位置 
		
		// 将最小数放在最左边，最大数放在最右边 
		if (nums[mid] < nums[left]) {
			swap(nums[mid], nums[left]);
		}
		if (nums[right] < nums[left]) {
			swap(nums[right], nums[left]);
		}
		if (nums[right] < nums[mid]) {
			swap(nums[right], nums[mid]);
		}
		
		//  因最右边值已经大于中值，将中值与最右边的左边的元素交换
		swap(nums[mid], nums[right - 1]);  // 可减少比较次数，优化 
		return nums[right - 1];  // 返回中值 
	}
	// 直接插入排序 
	void insertionSort(vector<int>& nums, int left, int right) {
	    for (int i = left + 1; i <= right; ++i) {  // 遍历无序序列
	        int key = nums[i];  // 记录准备插入的元素
	        int j = i - 1;  // 记录当前比较位置指针
	            
	        while (j >= 0 && nums[j] > key) {  // 寻找插入位置
	            nums[j + 1] = nums[j];  // 元素后移 
	            --j;  // 指针减1，当前比较位置前移
	        }
	        nums[j + 1] = key;  // 插入合适位置
	    }
	}
};

参考

算法导论

数据结构与算法分析(Java语言描述)

数据结构(C语言版)