python实现快速排序详解编程语言

最近在公司的工作内容发生变化,短期内工作量变少了,这也让我有时间整理一些日常学习和工作中的收获或思路。所以申请了博客,并打算持续更新。

 

快速排序采用了分治的思想,基本思想是选取数组中一个数为基准数(一般选择数组中的第一个数),一次排序过程中,将比基准数小的都放在它左侧,比基准数大的放在它的右侧。经过这次排序后得到两个数组和一个基准数,数组1中全部元素小于基准数,数组2中的全部元素大于基准数,然后对数组1,2分别进行同样的排序(递归),最后直到剩下一个数字。

 

下面给出python代码实现

 1 def partiton(li, low, high): 
 2     key = li[low] 
 3     while low < high: 
 4         while low < high and li[high] >= key: 
 5             high -= 1 
 6         if low < high: 
 7             li[low], li[high] = li[high], li[low] 
 8  
 9         while low < high and li[low] < key: 
10             low += 1 
11         if low < high: 
12             li[high], li[low] = li[low], li[high] 
13  
14     return low 
15  
16 def quickSort(li, low, high): 
17     if low >= high: 
18         return 
19     center = partiton(li, low, high) 
20     quickSort(li, low, center - 1) 
21     quickSort(li, center + 1, high)

关于实现:

快速排序的实现有很多种,这里我给出了比较常规并且好理解的一种.低位,高位两个指针从左右两侧相向遍历list。当高位指针发现了小于基准数的元素时,便停止移动,此时开始移动低位指针,当低位指针发现了大于基准数的元素时,便停止移动,两指针交换元素值,如此循环,直至两指针相遇。

 

关于时间复杂度:

快速排序具体的运行时间和原始列表本身的排序状态有很大关系,理论上快排的时间复杂度是(nlogn),但是如果运气不好糟糕,比如说初始列表是[5,4,3,2,1],那么根据上面的方法实现过程是什么样的呢,实现过程如下:

[5,4,3,2,1] -> [4,3,2,1,5] -> [3,2,1,4,5] -> [2,1,3,4,5] -> [1,2,3,4,5]

这样的排序实现过程很眼熟,跟最简单的冒泡排序的实现过程是完全相同的,所以说快排的最坏情况是冒泡排序,时间复杂度是(n2

 

以上的实现较为通用,如果不使用python,而使用c++,java等其它编程语言实现,代码结构不会相差太多。我想到了一种比较贴合python语法特点,并且能较好的展示快排思想的实现方法。不同点是该方法时间在层递归中需要遍历2次列表,即复杂度为(2nlogn)

def qsort(lst): 
    if not lst: 
        return [] 
    return qsort([i for i in lst[1:] if i < lst[0]]) + [lst[0]] + qsort([i for i in lst[1:] if i > lst[0]])

 

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/12490.html

(0)
上一篇 2021年7月19日
下一篇 2021年7月19日

相关推荐

发表回复

登录后才能评论