forked from itcharge/AlgoNote
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathArray-QuickSort.py
More file actions
46 lines (38 loc) · 2.02 KB
/
Array-QuickSort.py
File metadata and controls
46 lines (38 loc) · 2.02 KB
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import random
class Solution:
# 随机哨兵划分：从 nums[low: high + 1] 中随机挑选一个基准数，并进行移位排序
def randomPartition(self, nums: [int], low: int, high: int) -> int:
# 随机挑选一个基准数
i = random.randint(low, high)
# 将基准数与最低位互换
nums[i], nums[low] = nums[low], nums[i]
# 以最低位为基准数，然后将数组中比基准数大的元素移动到基准数右侧，比他小的元素移动到基准数左侧。最后将基准数放到正确位置上
return self.partition(nums, low, high)
# 哨兵划分：以第 1 位元素 nums[low] 为基准数，然后将比基准数小的元素移动到基准数左侧，将比基准数大的元素移动到基准数右侧，最后将基准数放到正确位置上
def partition(self, nums: [int], low: int, high: int) -> int:
# 以第 1 位元素为基准数
pivot = nums[low]
i, j = low, high
while i < j:
# 从右向左找到第 1 个小于基准数的元素
while i < j and nums[j] >= pivot:
j -= 1
# 从左向右找到第 1 个大于基准数的元素
while i < j and nums[i] <= pivot:
i += 1
# 交换元素
nums[i], nums[j] = nums[j], nums[i]
# 将基准数放到正确位置上
nums[j], nums[low] = nums[low], nums[j]
return j
def quickSort(self, nums: [int], low: int, high: int) -> [int]:
if low < high:
# 按照基准数的位置，将数组划分为左右两个子数组
pivot_i = self.partition(nums, low, high)
# 对左右两个子数组分别进行递归快速排序
self.quickSort(nums, low, pivot_i - 1)
self.quickSort(nums, pivot_i + 1, high)
return nums
def sortArray(self, nums: [int]) -> [int]:
return self.quickSort(nums, 0, len(nums) - 1)
print(Solution().sortArray([4, 7, 5, 2, 6, 1, 3]))