概述
一、快速排序
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。
步骤为：
选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。
class Solution:
'''快速排序'''
def partition(self, low, high, nums):
'''取数组中间值作为枢轴'''
if low >= high:
return
i, j = low, high
nums[low], nums[(i + j) // 2] = nums[(i + j) // 2], nums[low]
pivot = nums[low]
while i < j:
while i < j and nums[j] >= pivot:
j -= 1
nums[i] = nums[j]
while i < j and nums[i] < pivot:
i += 1
nums[j] = nums[i]
nums[i] = pivot
return i
def quickSort(self, low, high, nums):
if low >= high:
return
pivot = self.partition(low, high, nums)
self.quickSort(low, pivot-1, nums)
self.quickSort(pivot+1, high, nums)
时间复杂度：O(nlog2n)。 最好情况（待排序列接近无序）：O(nlog2n)；最坏情况（待排序列接近有序）：O(n2)
空间复杂度：O(nlogn)
稳定性：快排是一种不稳定排序，比如基准值的前后都存在与基准值相同的元素，那么相同值就会被放在一边，这样就打乱了之前的相对顺序
比较性：因为排序时元素之间需要比较，所以是比较排序。
二、冒泡排序
归并排序
class Solution:
def mergeSort_A(self, nums: List[int]) -> int:
def merge(left, right): #传入左右两个待合并序列
res = []
i,j = 0,0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
res.append(left[i])
i+= 1
else:
res.append(right[j])
j += 1
res += left[i:] #把剩余的部分并进来
res += right[j:]
return res
def mergeSort(nums):
if len(nums) <= 1:
return nums
mid = len(nums)//2
left = mergeSort(nums[:mid])
right = mergeSort(nums[mid:])
return merge(left, right)
return mergeSort(nuts)
时间复杂度：O(nlogn)。 最好情况, 最坏情况均为O(nlogn)
空间复杂度：O(n)
特性：是一种稳定排序
总结
以上是编程之家为你收集整理的Python实现各种排序算法全部内容，希望文章能够帮你解决Python实现各种排序算法所遇到的程序开发问题。
如果您也喜欢它,动动您的小指点个赞吧
602392714
清零编程群