快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为较小和较大的2个子序列,然后递归地排序两个子序列。
每次迭代,比flag大的放右边,比flag小的放左边,重点在partition上
def quicksort(nums, l, r):
if l < r:
p = partition(nums, l, r)
quicksort(nums, l, p-1)
quicksort(nums, p+1, r)
return nums
def partition(nums, l, r):
flag = nums[l]
i, j = l + 1, r
while True:
#从右往左找比flag小的
while i <= j and nums[j] >= flag:
j -= 1
#从左往右找比flag小的
while i <= j and nums[i] <= flag:
i += 1
if i <= j:
nums[i], nums[j] = nums[j], nums[i]
else:
break
nums[l], nums[j] = nums[j], nums[l]
return j
class quicksort:
def quicksort(self, nums, l, r):
if l < r:
p = self.partition(nums, l, r)
self.quicksort(nums, l, p-1)
self.quicksort(nums, p+1, r)
return nums
def partition(self, nums, l, r):
flag = nums[r]
i = l - 1
for j in range(l, r):
if nums[j] <= flag:
i += 1
nums[i], nums[j] = nums[j], nums[i]
i += 1
nums[i], nums[r] = nums[r], nums[i]
return i
每轮把数组等量地一分为二,直到分到只有一个数。然后再有序地合并,重点在merge上。
class mergesort:
def mergesort(self, nums):
if len(nums) <= 1: return nums
mid = len(nums) // 2
left = self.mergesort(nums[:mid])
right = self.mergesort(nums[mid:])
return self.merge(left, right)
def merge(self, left, right):
l, r = 0, 0
res = []
while l < len(left) and r < len(right):
if left[l] < right[r]:
res.append(left[l])
l += 1
else:
res.append(right[r])
r += 1
res += left[l:]
res += right[r:]
return res
class bubblesort:
def bubblesort(self, nums):
for _ in range(len(nums)):
for j in range(len(nums)-1):
if nums[j] > nums[j+1]:
nums[j], nums[j+1] = nums[j+1], nums[j]
return nums
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。