KK's blog

每天积累多一些

0%

快速排序

Posted on Edited on Disqus:

算法思路：

  1. 递归找pivot，然后按小于pivot和大于等于pivot分成两组。每轮递归，pivot肯定在正确（最终）位置上
  2. partition方法类似于Leetcode75的sort colors一样用两个指针i和noSmallerIdx。i是循环指针，而
    noSmallerIdx是第二组大于等于pivot的首元素，或者理解为比pivot小的元素（指针i指着）将要被交换
    的位置（比pivot大的元素）=比pivot小的元素的最后一个+1.
  3. 循环结束后，将pivot交换到正确的位置上。


i指向4，因为4小于pivot，所以要换到前面去，跟6置换，noSmallerIdx向后移。

应用：

  1. 排序
  2. 快速选择quick select
  3. partition，如Leetcode 75

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def quick_sort(self, nums: List[int]):
	if not nums:
		return
	self.q_sort(nums, 0, len(nums) - 1)

def q_sort(self, nums: List[int], start: int, end: int):
	if start >= end:
		return
	pivot = self.partition(nums, start, end)
	self.q_sort(nums, start, pivot - 1)
	self.q_sort(nums, pivot + 1, end)

def partition(self, nums: List[int], start: int, end: int):
	no_smaller_index, pivot = start, end
	for i in range(start, end):
		if nums[i] < nums[pivot]:
			nums[no_smaller_index], nums[i] = nums[i], nums[no_smaller_index]
			no_smaller_index += 1
	nums[no_smaller_index], nums[end] = nums[end], nums[no_smaller_index]
	return no_smaller_index

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(1)。

Quick Select

选择第k小的数(下标从0开始)

注意事项：

  1. left > right不再是等于，因为几个数相等的情况，排序的时候不用再移动，但第k小里面需要继续递归。
  2. binary select是单边递归，而不是双边。要判断pivot是否等于k。
  3. 递归调用仍用k，而不是跟pivot_pos相关，因为k是下标位置
  4. partition中range用[start, end)而不是len

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def quick_select(self, nums: List[int], k: int) -> int:
	if not nums:
		return -1
	return self.q_select(nums, 0, len(nums) - 1, k)

def q_select(self, nums: List[int], start: int, end: int, k: int):
	if start > end:
		return -1
	pivot = self.partition(nums, start, end)
	if k == pivot:
		return nums[pivot]
	if k < pivot:
		return self.q_select(nums, start, pivot - 1, k)
	else:
		return self.q_select(nums, pivot + 1, end, k)

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。

Partition

用于原位排序，将相应的元素放入该放的位置直到不满足条件为止

注意事项：

  1. i不一定会移动，放在else里面 
1
2
3
4
5
6
7
8
9
10
def sort(self, nums: List[int]) -> int:
	i = 0
	while i < len(nums):
		if <condition>
			self.swap(nums, i, j)
		else:
			i += 1

def swap(self, nums, i, j):
	nums[i], nums[j] = nums[j], nums[i]

上述算法的问题不能有效处理两种情况：

  1. 有序数组[1, 2, 3, 4]
  2. 单一数组[2, 2, 2, 2]

第一种情况递归为
[123]
[12]
[1]
只会递归左半，不会递归右半

第二种情况
[2222]
[222]
[22]
[2]
只会递归右半，不会递归左半
这两种情况都是O(n^2)

解决第一个问题用randomize pivot的方法
解决第二个问题用three-way partition的方法，类似于75 Sort colors将区间从两个变成3个: 小于pivot, 等于pivot，大于pivot，这样对于单一值数组，左半和右半就不会递归了

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def sortArray(self, nums: List[int]) -> List[int]:
	if not nums:
		return
	self.q_sort(nums, 0, len(nums) - 1)
	return nums


def q_sort(self, nums: List[int], start: int, end: int):
	if start >= end:
		return
	pivot = random.randint(start, end)
	nums[pivot], nums[start] = nums[start], nums[pivot]
	lt, gt = self.partition(nums, start, end)
	self.q_sort(nums, start, lt - 1)
	self.q_sort(nums, gt, end)

def partition(self, x, start, end):
	i, lt, gt = start, start, end
	while i <= gt and i < len(x) and gt >= 0:
			if x[i] < x[lt]:
					x[i], x[lt] = x[lt], x[i]
					i += 1
					lt += 1
			elif x[i] > x[lt]:
					x[i], x[gt] = x[gt], x[i]
					gt -= 1
			else: # x[i] == x[lt]
					i += 1
	return lt, gt

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public void sort(int[] arr) {
	if(arr == null || arr.length == 0)
		return;
	quickSort(arr, 0, arr.length - 1);
}

void quickSort(int[] arr, int left, int right) {
	if(left >= right)
		return;
	int pivotPos = partition(arr, left, right);
	quickSort(arr, left, pivotPos - 1);
	quickSort(arr, pivotPos + 1, right);
}

int partition(int[] arr, int left, int right) {
	int noSmallerIdx = left;
	int pivot = arr[right];
	for(int i = left; i < right; i++) {
		if(arr[i] < pivot) 
			swap(arr, noSmallerIdx++, i);
	}
	swap(arr, noSmallerIdx, right);
	return noSmallerIdx;
}

void swap(int[] arr, int i, int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}
Free mock interview