402v /posts/leetcodeshi-zhan-kuai-su-pai-xu

LeetCode实战 - 快速排序

status: publishedNotevisibility: publicplato11/24/2015
#algorithm#leetcode#quicksort

最近在刷LeetCode，顺便把之前不会、掌握的不熟练的算法都看一遍，今天要说的是快速排序。

###快速排序 快速排序是通常比其他基于比较的排序算法效率更高，效率最好体现在大部分情况下都能达到O(nlogn)的时间复杂度。

快排的算法实现利用到了分治法（Divide and Conquer）和递归（recursive），以某个特定值为基准（pivot）将一个List分成两个子List处理。

###划分（Partation） 快速排序的思路是：

  1. 在无序数组中取某个特定值为标准；
  2. 从头部开始查找第一个大于标准值的位置（指针head）；
  3. 从尾部开始查找第一个小于标准值的位置（指针tail）；
  4. 交换两个位置的值；
  5. 继续重复2和3直到head指针的位置大于等于指针tail的位置。

这样称作快速排序的一次划分，每趟划分之后都会有一个元素到达排序后最终位置。

Ruby版本的划分算法如下：

# 基准值选取（随机pivot）
def pick_pivot (nums, left_i, right_i)
	Random.new.rand(left_i..right_i)
end

# 划分
def partition(nums, left_i, right_i)

	# 确定pivot
	pivot = pick_pivot(nums, left_i, right_i)
	
	# 保存pivot值
	pivot_value = nums[pivot]
	
	# 将pivot与最右侧元素调换，该位置相当于一个tmp值，用于下面算法中swap的中间值
	nums[pivot],nums[right_i] = nums[right_i],nums[pivot]
	
	# 划分比较，left_i大于等于right_i时循环终止
	while left_i < right_i do
		while left_i < right_i do
			# 找到左边第一个大于基准值的index
	        if nums[left_i] > pivot_value then
				# swap
				nums[left_i],nums[right_i] = nums[right_i],nums[left_i]
				# 最右侧元素索引左移一位
				right_i -= 1
	            break
	        end

			# 记录此时最左侧元素位置
			left_i += 1
		end
		
		while left_i < right_i do
			# 找到右侧第一个小于基准值的index
			if nums[right_i] < pivot_value then
				# swap
				nums[right_i],nums[left_i] = nums[left_i],nums[right_i]
				# 最左侧元素索引右移一位
				left_i += 1
				break
			end
			
			# 记录此时最右侧元素位置
			right_i -= 1
		end
	end
	
	# 将保存的pivot值移到正确的位置
	nums[right_i] = pivot_value
	
	# 返回当前划分位置
	left_i
end

###基准关键字的选取 在当前无序区中选取划分的基准关键字（pivot）是决定算法性能的关键，通过优化pivot选取算法可以提高快速排序算法的效率。

一些算法书上给出的算法都是直接使用数组的第一个元素作为pivot，这时如果当前数组已经有序，就会出现时间复杂度为O(n2)的最坏情况。

#####随机选取 上述划分代码给出的基准值选取函数pick_pivot中采用的是随机选取，这是一种性能较好的pivot选取方法。

用一个随机函数产生一个取位于 low 和 high 之间的随机数 k(low≤k≤high)，用 R[k] 作为基准，这相当于强迫R[low..high]中的记录是随机分布的。用此方法所得到的快速排序一般称为随机的快速排序。

随机选取可以大大降低快速排序出现最坏时间复杂度的情况。

#####三者取中 另一种可行的选取办法是三者取中。即在当前区间里，将该区间首、尾和中间位置上的关键字比较，取三者之中值所对应的记录作为基准，在划分开始前将该基准记录和该区的最后一个元素进行交换。

注意：划分算法中pivot值和原数组中最后一个元素交换这一步非常重要，也比较容易出错。这一步即保留了pivot值，同时为后续swap提供了temp空间。

###快速排序的递归实现

快速排序的Ruby版本实现如下：

# 快速排序
def quick_sort(nums, start_i, end_i)
	
	# 递归出口
	if start_i >= end_i then
		return
	end
	
	# 基本操作：一趟划分
	i = partition(nums, start_i, end_i)
	
	# 此时i位置元素已到位，递归前后两个sublist
	quick_sort(nums, start_i, i-1)
	quick_sort(nums, i+1, end_i)
end

# 测试
nums = [1,2,6,4,3,4,6]
quick_sort(nums, 0, nums.length - 1)

###快速排序的时间复杂度

因为快速排序的记录移动次数不大于比较的次数，所以快速排序中的基本操作就是比较，时间复杂度也关注比较的次数。

#####最坏的时间复杂度 最坏的时间复杂度发生在：每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。此时，快速排序必须做 n-1 次划分，第i次划分开始时区间长度为 n-i+1，所需的比较次数为 n-i(1≤i≤n-1)，故总的比较次数达到最大值：Cmax = n(n-1)/2=O(n2)。

比如上面描述的如果选取第一个元素为pivot，并且该数组为有序数组就会出现最坏情况。

#####最好的时间复杂度 快速排序最好和平均时间复杂度都为O(nlogn)。

在最好情况下，每次划分所取的基准都是当前无序区的"中值"记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。

用递归树来分析最好情况下的比较次数更简单。因为每次划分后左、右子区间长度大致相等，故递归树的高度为 O(logn)，而递归树每一层上各结点所对应的划分过程中所需要的关键字比较次数总和不超过n，故整个排序过程所需要的关键字比较总次数 C(n)=O(nlogn)。

###快速排序的稳定性 快速排序是不稳定的排序算法，即当关键字K1 == K2时，如果R1在R2之前，采用快速排序后无法确定R1R2的顺序。

关于我们讨论算法稳定性的意义再多说几句。

以下引用自维基百科 - 排序算法

当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。

(4, 1)  (3, 1)  (3, 7)（5, 6）

在这个状况下，有可能产生两种不同的结果，一个是让相等键值的纪录维持相对的次序，而另外一个则没有：

(3, 1)  (3, 7)  (4, 1)  (5, 6)  （維持次序）
(3, 7)  (3, 1)  (4, 1)  (5, 6)  （次序被改變）

不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，（比如上面的比较中加入第二个标准：第二个键值的大小）就会被决定使用在原先数据次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。

典型的例子就是在基数排序中，即我们要对多个关键词多次排序的时候，就一定要使用稳定算法。

###快速排序与堆排序的比较

基于比较的排序算法的时间复杂度最快能达到O(nlogn)，其中效率最好的是快速排序和堆排序，二者也经常放在一起比较。

归并排序也可以达到O(nlogn)，而且像基数排序、桶排序是可以达到O(n)级别的时间复杂度，不在这里展开说了。

从数学意义上，虽然完全逆序的情况下，快速排序会降到选择排序的速度（即快排的最坏情况下时间复杂度为O(n2)，而之前提过堆排序的最坏情况下时间复杂度仍可以达到O(nlogn)），不过从概率角度来说，不对算法做编程上优化时，快速排序的平均速度比堆排序要快一些。

从使用意义上，根据知乎上的这篇回答快排的缓存利用率高于堆排序，所以在实际使用上快排优于堆排序。

算法效率的好坏并不是一成不变的，取决于实际样本的特点、数据的量，根据实际情况选择合适的排序算法才是学习的最终目的。

###参考资料

  1. 数学之美番外篇：快排为什么那样快
  2. 知乎 - 堆排序缺点何在
  3. 知乎 - 为什么在平均情况下快速排序比堆排序要优秀
  4. 极客学院Wiki-快速排序

评论 · 0

还没有评论。