Python数据结构与算法8——快速排序

作者: 皮皮大 | 来源:发表于2019-09-22 11:47 被阅读0次

快速排序

算法思想

快速排序算法首先会在序列中随机选择一个基准值(pivot),然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别,再将其排列成以下形式:

[ 比基准值小] 基准值 [比基准值大]

接着,对两个“[ ]”中的数据进行排序之后,整体的排序便完成了。对“[ ]”里面的数据进行排序时同样也会使用快速排序,即使用递归的思想。

时间复杂度

时间复杂度nlog_2(n)
不稳定

https://www.cnblogs.com/onepixel/articles/7674659.html

代码实现

def quick_sort(data):    
    """快速排序"""    
    if len(data) >= 2:  # 递归入口及出口        
        mid = data[len(data)//2]  # 选取基准值,也可以选取第一个或最后一个元素        
        left, right = [], []  # 定义基准值左右两侧的列表        
        data.remove(mid)  # 从原始数组中移除基准值        
        for num in data:
            # 关于data中的数据,大于mid的放在left中,小于mid的放在right            
            if num >= mid:                
                right.append(num)            
            else:                
                left.append(num) 
        # 返回值中对left和right两个子列表分别递归调用函数       
        return quick_sort(left) + [mid] + quick_sort(right)    
    else:        
        return data
def quick_sort(alist, first ,last):
    # 快速排序 
    if first >= last:
        return
    
    # 先选择基准值,即第一个元素
    mid_value = alist[first]
    # 通过两个游标的从头部和尾部的移动来确定基准值的位置
    # 满足左边的比基准值小,右边的比基准值大
    low = first
    high = last
    
    while low < high:
        # 下面两个循环交替执行,不断的左右移动
        
        # 如果high指向的元素比基准值大,说明该值应该留在右边
        while low < high and alist[high] >= mid_value:
            # 同时high的指针往左移动
            high -= 1
        # 如果不满足循环条件,则说明high指向的值比基准值小,和前面low指向的值交换位置
        alist[low] = alist[high]

        # 对于左边的low指向的值小于基准值,放在左边
        while low < high and alist[low] < mid_value:
            low += 1
        # 不满足while循环则交换位置
        alist[high] = alist[low]
    # 从循环退出,low == high
    alist[low] = mid_value
    
    # 递归调用函数自身:传入下标的起始值不同,还是原来的列表
    
    # 基准值左边的列表进行快排
    quick_sort(alist,first, low-1)
    
    # 基准值右边的列表进行快排
    quick_sort(alist,low+1, last)
    
if __name__ == "__main__":
    li = [1, 9, 6, 3, 8, 4, 7, 5, 2]
    print(li)
    quick_sort(li, 0, len(li)-1)
    print(li)

《算法图解》这本书上的代码很好理解

def quicksort(array):
    # 判断只有一个元素的情况
    if len(array) < 2:
        return array
    else:
        # 指定基数
        pivot = array[0]
        # 基准数左边:从原有列表中选择出 <= 基准值的元素
        less = [i for i in array[1:] if i <= pivot]
        # 基准数右边
        greater = [i for i in array[1:] if i > pivot]
        # 调用函数自身,递归思想
        return quicksort(less) + [pivot] + quicksort(greater)
print (quicksort([10, 5, 2, 9, 3, 8, 5]))

相关文章

  • 排序算法-堆排序

    参考: Java排序算法(五):堆排序 【算法与数据结构】图说堆排序 【数据结构】排序算法:希尔、归并、快速、堆排...

  • 数据结构与算法 - 排序与搜索

    文章来源:数据结构与算法(Python) 排序与搜索排序算法(英语:Sorting algorithm)是一种能将...

  • 排序算法6:快速排序

    数据结构与算法 快速排序为应用最多的排序算法,因为快速二字而闻名。快速排序和归并排序一样,采用的都是分治思想。 分...

  • 算法与数据结构路线图

    学习算法与数据结构,深刻理解计算机科学 排序算法:插入、冒泡、选择、希尔、快速、归并、堆排序、计数排序、桶排序、基...

  • 数据结构与算法——快速排序

    数据结构与算法——快速排序 快速排序,顾名思义,它速度很快,针对一般应用中各种不同的输入都要比其他排序算法快很多,...

  • Python排序算法有哪几种?

    python排序算法有哪些?python中常见的排序算法有:插入排序、选择排序、冒泡排序、快速排序、归并排序、希尔...

  • Python数据结构与算法8——快速排序

    快速排序 算法思想 快速排序算法首先会在序列中随机选择一个基准值(pivot),然后将除了基准值以外的数分为“比基...

  • (转)排序算法

    排序算法点这里 数据结构与算法——计数排序、桶排序、基数排序

  • 算法与数据结构(六):堆排序

    title: 算法与数据结构(六):堆排序tags: [算法与数据结构, C语言, 堆排序]date: 2019-...

  • Python 算法大全

    这个库涵盖了多种算法和数据结构的介绍,比如: 排序算法(冒泡排序、希尔排序、插入排序、桶排序、合并排序、快速排序、...

网友评论

    本文标题:Python数据结构与算法8——快速排序

    本文链接:https://www.haomeiwen.com/subject/owmzectx.html