快速排序(单路快排/双路快排/三路快排) Python版笔记
程序员文章站
2022-06-04 17:36:44
...
1.快速排序
时间复杂度 :最好O(nlogn)
,最坏O(n^2)
空间复杂度 :O(1)
Partition主要思想是:将小于v和大于v的部分都放到索引值i的左边
def _partition(nums,l,r):
'''
将数组第一个数视为base,目的是将所有小数放到左边,大数放到右边,返回正确分割的索引
'''
base = nums[l] #即图片的v
j = l+1
for i in range(l+1, r+1):
if nums[i] < base: #遍历数组剩下的数,如果小于base则依次放在base的后面
nums[i], nums[j] = nums[j], nums[i]
j += 1
print(nums)
nums[l], nums[j-1] = nums[j-1], nums[l] #把base值放到正确的位置
print(nums)
return j-1
def _quick_sort(nums,l,r):
if l < r:
m = _partition(nums,l,r)
_quick_sort(nums,l,m-1)
_quick_sort(nums,m+1,r)
def quick_sort(nums):
l, r = 0, len(nums)-1
_quick_sort(nums,l,r)
当待排序数组是一个近乎有序
的序列时,容易产生最坏O(n^2)的时间复杂度。
改进办法:base随机选取
def _partition_random(nums,l,r):
ind = random.randint(l,r)
nums[l], nums[ind] = nums[ind], [l]
##### 后面的内容同_partition,故省略 #####
2.双路快排
当待排序数组是一个数值重复率非常高
的序列时,容易产生最坏O(n^2)的时间复杂度。
产生下图所示的情况,左右子树不均衡:
Partition主要思想是:将小于v的部分放到指针i(i为遍历用指针)的左边,将大于v的部分都放到指针j的右边,延用随机选base的思路。等于v时使用交换的方式处理。
import random
def _partition_doubule(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
def _quick_sort(nums, l, r):
if l < r :
m = _partition_doubule(nums, l, r)
_quick_sort(nums, l, m - 1)
_quick_sort(nums, m + 1, r)
def quick_sort(nums):
l, r = 0, len(nums)-1
_quick_sort(nums,l,r)
3.三路快排
Partition主要思想是:将小于v的部分放到指针lt左边,将大于v的部分放到指针gt右边。考虑到v有重复值的情况,遇到等于v的情况,将i指针右移。
import random
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
print(nums)
nums[l], nums[lt] = nums[lt], nums[l]
print(nums)
return lt, gt
def _quick_sort(nums, l, r):
if l < r:
lt, gt = _partition(nums, l, r)
_quick_sort(nums, l, lt - 1)
_quick_sort(nums, gt, r)
def quick_sort(nums):
l, r = 0, len(nums) - 1
_quick_sort(nums, l, r)
引用:
1.快速排序时间复杂度为O(n×log(n))的证明
2.排序算法—快速排序,随机快速排序和双路快排(python版)
3.归并排序、快速排序、二路快排、三路快排python实现
4.十大经典排序算法(动图演示)
上一篇: 排序算法之——三路快排分析
下一篇: 《算法导论》第三版 2.3.1 归并排序