Python实现各种排序算法

概述一、快速排序快速排序使用分治法（Divideandconquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。步骤为：挑选基准值：从数列中挑出一个元素，称为"基准"（pivot）;分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后 一、快速排序

快速排序使用分治法（divIDe and conquer）策略来把一个序列（List）分为较小和较大的2个子序列，然后递归地排序两个子序列。

步骤为：

挑选基准值：从数列中挑出一个元素，称为"基准"（pivot）;分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成;递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

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实现各种排序算法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。