python-快速排序
核心思想：取一个初始值，将数组中比该值小的放在其左边，比其大的放在右边， 再对左、右子数组进行相同操作，直到数组排好序。
def quicksort(nums):
l = 0
r = len(nums) - 1
_quicksort(nums,l,r)
def _quicksort(nums,l,r):
if l < r:
p = partition(nums,l,r)
_quicksort(nums,l,p-1)
_quicksort(nums,p+1,r)
def partition(nums,l,r):
base = nums[l]
j = l+1
for i in range(l+1,r+1):
if nums[i]<base:
nums[i],nums[j]=nums[j],nums[i]
j+=1
nums[l],nums[j-1]=nums[j-1],nums[l]
return j-1
nums = [6,2,5,3,4,8,1,7]
quicksort(nums)
print(nums)改进：随机选择初始值，避免数组有序使算法退化。从两边开始遍历，减少遍历时间。
import random
def quicksort(nums):
l = 0
r = len(nums) - 1
_quicksort(nums,l,r)
def _quicksort(nums,l,r):
if l < r:
p = partition(nums,l,r)
_quicksort(nums,l,p-1)
_quicksort(nums,p+1,r)
def partition(nums, l, r):
ind = random.randint(l, r)
nums[l], nums[ind] = nums[ind], nums[l]
base = nums[l]
i, j = l+1, r
while True:
while i <= r and nums[i] < base: # 不能改为nums[i] <= base
i += 1
while j >= l + 1 and nums[j] > base: # 不能改为nums[j] >= base.
j -= 1
if i > j:
break
else:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
nums[j], nums[l] = nums[l], nums[j]
return j
nums = [6,2,5,3,4,8,1,7]
quicksort(nums)
print(nums)改进：三路快排，用于解决数组中有较多重复的值。
import random
def quicksort(nums):
l = 0
r = len(nums) - 1
_quicksort(nums,l,r)
def _quicksort(nums,l,r):
if l < r:
lt,gt = partition(nums,l,r)
_quicksort(nums,l,lt-1)
_quicksort(nums,gt,r)
def partition(nums, l, r):
ind = random.randint(l, r)
nums[l], nums[ind] = nums[ind], nums[l]
base = nums[l]
lt = l # nums[l+1...lt] < base
gt = r + 1 # nums[gt...r] > base
i = l + 1 # nums[lt+1...i] == base
while (i < gt):
# i==gt时表示已经比较结束
if (nums[i] < base):
nums[i], nums[lt+1] = nums[lt+1], nums[i]
lt += 1
i += 1
elif (nums[i] > base):
nums[i], nums[gt-1] = nums[gt-1], nums[i]
gt -= 1
else: # nums[i] == base
i += 1
nums[l], nums[lt] = nums[lt], nums[l]
return lt, gt
nums = [6,2,5,3,4,8,1,7]
quicksort(nums)
print(nums)本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-02-19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读