以leetcode某题为背景:(所有代码均可在leetcode测试通过)
快速排序:
- 先按照字典序构造排序规则;(小写字母>大写字母>1-9);
- 分治策略实现,递归+while循环进行元素交换。
class Solution:
def minNumber(self, nums: List[int]) -> str:
def compare(x, y):
# 转为字符串按照字典序进行比较;也就是直接比大小
a = str(x) + str(y)
b = str(y) + str(x)
if a < b:
return 0
else:
return 1
def quick_sort(nums, left, right):
if left > right:
return
low = left
high = right
priority = nums[left]
while left < right:
# 这里的循环,如果nums[right] 比 priority小才能继续进行,所以大数被转移到左边
while left < right and compare(nums[right], priority):
right = right - 1
nums[right], nums[left] = priority, nums[right] # 因为这个时候的left是空出来的
while left < right and compare(priority, nums[left]):
left = left + 1
nums[left], nums[right] = priority, nums[left]
quick_sort(nums, low, left - 1)
quick_sort(nums, left + 1, high)
return nums
nums = quick_sort(nums, 0, len(nums) - 1)
nums=''.join(str(num) for num in nums)
return nums
归并排序:
class Solution:
# 典型的分治法
def minNumber(self, nums: List[int]) -> str:
def compare(x, y):
# 转为字符串按照字典序进行比较;也就是直接比大小
a = str(x) + str(y)
b = str(y) + str(x)
if a < b:
return 1
else:
return 0
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if compare(left[i], right[j]):
result.append(left[i])
i = i + 1
else:
result.append(right[j])
j = j + 1
if i < len(left):
result.extend(left[i:])
if j < len(right):
result.extend(right[j:])
print(result)
return result
# 归并排序先拆分,再对不可拆分的最小项进行排序
def merge_sort(nums):
# 边界条件,当只有一个元素时 return
if len(nums) <= 1:
return nums
mid = int(len(nums) / 2)
# 包含边界
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)
nums=merge_sort(nums)
nums=''.join([str(num) for num in nums])
return nums
堆排序:
堆排序的流程:
- 首先是建堆,大顶堆是升序,小顶堆是降序(因为建好堆之后,每次需要把堆顶也就是最小的元素移动到数组的尾部);
- 选取i=length/2处的元素开始调整;之后继续向前直到i=0;
- 调整时可能会导致下面的数据混乱,所以要继续向下调整;
- 排序的过程,每次需要把堆顶元素和未标记的叶子结点进行交换;然后重新调整;
class Solution:
def minNumber(self, nums: list[int]):
def compare(x, y):
# 转为字符串按照字典序进行比较;也就是直接比大小
a = str(x) + str(y)
b = str(y) + str(x)
if a < b:
return 0
else:
return 1
# 调整堆内元素,每次调用只完成一次调整
def adjust(nums, parent, length):
temp = nums[parent]
child = 2 * parent + 1
while child <= length:
if child < length and compare(nums[child], nums[child + 1]):
child = child + 1
if not compare(temp, nums[child]):
break
# 只会引起下级的不平衡,不会混乱
nums[parent], nums[child] = nums[child], nums[parent]
parent = child
child = child * 2 + 1
# 构造初始大顶堆
border = len(nums) // 2 - 1
for i in range(border, -1, -1):
adjust(nums, i, len(nums) - 1)
# 升序排列,大顶堆
for i in range(len(nums) - 1, 0, -1):
nums[0], nums[i] = nums[i], nums[0]
adjust(nums, 0, i - 1)
print(nums)
result=''
while nums:
result+=str(nums.pop())
return result
版权声明:本文为Andrehao原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。