merge sort
LC 148: sort a linked list
快慢指针分成两半，断开中间，分别递归排序，最后升序合并两个链表。边界条件：head==None or head.next==None
LC 23. Merge k Sorted Lists
注意边界情况
quick sort
以数组某个元素（一般选取首元素）为基准数，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。
python模版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| def partition(nums, left, right):
pivot = nums[left]#初始化一个待比较数据
i,j = left, right
while(i < j):
while(i<j and nums[j]>=pivot): #从后往前查找，直到找到一个比pivot更小的数
j-=1
nums[i] = nums[j] #将更小的数放入左边
while(i<j and nums[i]<=pivot): #从前往后找，直到找到一个比pivot更大的数
i+=1
nums[j] = nums[i] #将更大的数放入右边
#循环结束，i与j相等
nums[i] = pivot #待比较数据放入最终位置
return i #返回待比较数据最终位置
def quickSort(self, nums, low, high):
if low<high:
pivot=self.partition(nums, low, high)
self.quickSort(nums,low, pivot-1)
self.quickSort(nums, pivot+1, high)
|
215 数组中的第K个最大元素
视频讲解
期望为线性的选择算法.
函数返回时，第m+1小的元素正好在m这个 index 上。并且比它小的都在它左边，比它大的都在它右边。
避免超时：三路划分
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
|
def three_way_partition(nums, low, high):
# 随机选择基准元素并交换到最左端（避免最坏情况）
rand_pivot = random.randint(low, high)
nums[low], nums[rand_pivot] = nums[rand_pivot], nums[low]
pivot = nums[low]
# 初始化三个指针：
# [low..lt] < pivot
# [lt+1..i) == pivot
# [gt..high] > pivot
lt = low # 左区间的右边界（最后一个 < pivot 的位置）
gt = high + 1 # 右区间的左边界（第一个 > pivot 的位置）
i = low + 1 # 当前扫描指针
while i < gt:
if nums[i] < pivot:
lt += 1
nums[i], nums[lt] = nums[lt], nums[i]
i += 1
elif nums[i] > pivot:
gt -= 1
nums[i], nums[gt] = nums[gt], nums[i]
else:
i += 1
# 将基准元素交换到中间区间的起始位置
nums[low], nums[lt] = nums[lt], nums[low]
lt -= 1 # 现在 [low..lt] < pivot, [lt+1..gt-1] == pivot, [gt..high] > pivot
# 返回左区间右边界和右区间左边界
return lt, gt
|
递归函数
1
2
3
4
5
6
7
8
9
10
11
| def quickSort(self, nums, low, high,m):
if low<high:
# 调用三路划分模版
lt, gt = self.partition(nums, low, high)
# 判断目标位置所在的区间
if m <= lt: # 目标在左区间
return self.quickSort(nums, low, lt, m)
elif m >= gt: # 目标在右区间
return self.quickSort(nums, gt, high, m)
else: # 目标在中间区间（直接命中）
return nums[m]
|