[数据结构与算法]快速排序算法

快速排序算法介绍

快速排序是经常用到的一种排序方法，和冒泡排序不同的是，通过随机选择一个数作为基准pivot，通过比较，将数组划分为小于基准和大于基准的两部分。之后在分别对小于基准和大于基准的部分重复以上过程。通过递归实现整个数组的排序。

具体步骤

为了保证排序的效率，应该随机选取数组中的某个数作为基准。

1. 随机选择[l, r]之间的一个基准pivot后，将所选数组与最后一位互换——将基准换至最后一位的目的是为了不影响前面比较的过程。
2. 使用两个指针（在python中即为两个变化的索引值）i，j——其中i 表示当前小于基准部分的最大索引，初始值为l-1。此处 i=l-1 的原因是一开始默认第一位不是小于基准的数；j负责从l->r逐个遍历数组
3. 分别比较 nums[j] 和 nums[r]（此处是与nums[r]相比较，不再是nums[pivot]，因为基准已经被换至最后），如果nums[j]<nums[r]，说明当前的数小于基准，需要将i后移一位，并与当前的nums[j]互换。反之，则继续移动j
4. 然后，将最后一位的基准换至小于基准部分的后面。此处需要先i++，因为基准是换至小于基准部分的后面。最后返回的也是i，所以需要操作i的值，而不是仅仅完成互换。

代码示例

class Solution():
	def partition(self, nums, l, r):
		p = random.randint(l, r)
		nums[p], nums[r] = nums[r], nums[p]
		i = l-1
		for j in range(l, r):
			if nums[j] < nums[r]:
				i += 1
				nums[j], nums[i] = nums[i], nums[j]
		i+=1
		nums[r], nums[i] = nums[i], nums[r]
		return i
	
	def quicksort(self, nums, l, r):
		if r-l<=0:
			return
		m = self.partition(nums, l, r)
		self.quicksort(nums, l, m-1)
		self.quicksort(nums, m+1, r)
		# 此处将nums[m]略过是因为m与前后已经有了明确的大小关系，无需再参与比较。
	def sort(self, nums):
		self.quicksort(nums, 0, len(nums)-1)
		return nums


if __name__ == "__main__":
	nums = [2,8,4,1,3,5,6,7]
	s = Solution()
	print(s.sort(nums))

直观

假设随机选取pivot=2
nums=[2,8,4,1,3,5,6,7]——>nums=[2,8,7,1,3,5,6,4]

最后将基准换至i后面——> nums=[2,1,3,4,7,5,6,8]

思考的几个问题

1. j 遍历的 range(l, r)是从l->r，而不是r-1：因为在调用sort()时，传入的r已经是len(nums)-1，已经是数组最后一个的下表，也就是range(l, r)产生的最后一个j=r-1，刚好是基准的前一个数，故不需要r-1，否则会out of index
2. nums[j]应该与nums[r]相比较：因为nums[pivot]已换至最后一位
3. 为什么一开始i=l-1？因为尚不知道数组的第一个数与基准的关系，如果第一个数比基准大的话，此时i的索引已经为0，后续再次进入循环时，r+1=1，就直接跳过第一个数进行交换了。
4. 最后基准换至i后时，为什么是先i+=1，而不是直接与nums[i+1]进行交换即可：因为最后需要返回基准所在的位置