快速排序的Python 简单实现

快速排序的Python 简单实现

核心思想

先从待排序的数组中找出一个数作为基准数（取第一个数即可），然后将原来的数组划分成两部分：小于基准数的左子数组和大于等于基准数的右子数组。然后对这两个子数组再递归重复上述过程，直到两个子数组的所有数都分别有序。最后返回“左子数组” + “基准数” + “右子数组”，即是最终排序好的数组。

from random import randint

def quicksort(nums):

    iflen(nums) <=1:

        return nums

    # 左子数组

    less = []

    # 右子数组

    greater = []

    # 基准数

    base= nums.pop()

    # 对原数组进行划分

    forxin nums:

        ifx

            less.append(x)

        else:

            greater.append(x)

    # 递归调用

    returnquicksort(less) + [base] + quicksort(greater)if__name__ =='__main__':

    nums = [randint(-1000,1000)forxinrange(100)]

    print (quicksort(nums))

输出：

[1,2,3,4,5,6,7,8,9,10]

快速排序算法的平均时间复杂度为O(nlogn)，通常认为在所有同数量级的排序算法中，快速排序的平均性能是最好的，这也是它被称为“快速排序”的原因。

快速排序算法相比于其他排序算法来说比较耗费空间资源，因为快速排序需要栈空间来实现递归。

快速排序的基准元素的选取非常重要，如果基准元素选取不当，可能影响排序过程的时间复杂度和空间复杂度。为了避免快速排序退化为冒泡排序以及递归栈过深等问题，通常依照“三者取中”的法则来选取基准元素。三者取中法是指在当前待排序的子序列中，将其首元素、尾元素和中间元素进行比较，在三者中取中值作为本趟排序的基准元素。