Maison > développement back-end > Tutoriel Python > 使用python实现8大排序算法-快速排序

使用python实现8大排序算法-快速排序

巴扎黑
Libérer: 2016-12-03 11:23:37
original
958 Les gens l'ont consulté

快速排序的基本思想:

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序。

例:

       arr = [49,38,04,97,76,13,27,49,55,65],设置第一位49为key值,从右向左找到比key值小的数,把找到的数赋值给第一位数;

       arr = [27,38,04,97,76,13,27,49,55,65],然后从左第一位向右找到比key值大的数,把找到的数赋值给上个从右向左找到的数;

       arr = [27,38,04,97,76,13,97,49,55,65],然后从右向左,从左向右,直到left=right,跳出循环,并把key值赋值给些索引值。最后再对两边的分组进行递归。

代码:

def quick_sort(lists, left, right):
    #快速排序
    if left >= right:  #当递归调用的分组为1个数时返回列表
        return lists
    key = lists[left]  #保存key值,在一轮调用结束时,存到中间值
    low = left
    high = right  #供递归调用时使用
    while left < right:  #通过下面两个循环依次交替赋值并使key值两侧为大小分组
        while left < right and lists[right] >= key:  
            right -= 1
        lists[left] = lists[right]
        while left < right and lists[left] <= key:
            left += 1
        lists[right] = lists[left]
    lists[right] = key
    quick_sort(lists, low, left-1)  #对key值左侧进行排序分组
    quick_sort(lists, left+1, high)  #对key值右侧进行排序分组
    return lists
Copier après la connexion


Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal