快速排序算法回顾 （Python实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了快速排序算法回顾 （Python实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2520字，纯文字阅读大概需要4分钟。

内容图文

#这个也是快速排序--------------------------------------------------
def qsort(list):
    if list==[]:
        return []
    else:
        smaller=[x for x in list[1:] if x<list[0]] #比list[0]小的部分
        bigger=[x for x in list[1:] if x>=list[0]] #比list[0]大（或相等）的部分
        return qsort(smaller)+[list[0]]+qsort(bigger)

=============================

 

冒泡排序的过程是首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。以此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称为第一趟冒泡排序，接着第二趟对前面n-1个关键字进行同样操作，……

 

 

 

 

 

 

 

 

快速排序是对冒泡排序的一种改进，通过一趟排序将记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，可分别对这两部分记录以递归的方法继续进行排序，以达到整个序列有序。

单趟Partition()函数过程请看下面动图：

 

 

 

用Python进行实现：

 

#coding=utf-8
import time

a=[49,38,65,97,76,13,27,49]
b=[-1,49,38,65,97,76,13,27,49]      #其中b[0]=-1这一位置是暂存单元，用于存放下面算法中的list[low]

#冒泡排序-------------------------------------------------------
def BubbleSort(list):
    for i in reversed(range(len(a))):
        for j in range(0,len(a)-1):
            if(list[j] > list[j+1]):
                temp=list[j]
                list[j]=list[j+1]
                list[j+1]=temp


#快速排序-------------------------------------------------------
def Partition(list,low,high):
    pivotkey=list[low]              #枢轴
    list[0]=list[low]           
    while low<high:                 #从表的两端交替地向中间扫描
        while(low<high and list[high]>=pivotkey):
            high-=1
        list[low]=list[high]        #将比枢轴记录小的移到低端
        while(low<high and list[low]<=pivotkey):
            low+=1
        list[high]=list[low]        #将比枢轴记录大的移到高端
    list[low]=list[0]               #枢轴记录到位
    return low                      #返回枢轴位置

def Qsort(list,low,high):   
    if low<high:
        pivotloc=Partition(list,low,high);      #将list一分为二
        Qsort(list,low,pivotloc-1)              #对低子表递归排序
        Qsort(list,pivotloc+1,high)             #对高子表递归排序

def QuickSort(list):
    Qsort(list,1,len(list)-1)
#这个也是快速排序--------------------------------------------------
def qsort(list):
    if list==[]:
        return []
    else:
        smaller=[x for x in list[1:] if x<list[0]] #比list[0]小的部分
        bigger=[x for x in list[1:] if x>=list[0]] #比list[0]大（或相等）的部分
        return qsort(smaller)+[list[0]]+qsort(bigger)

#---------------------------------------------------------------

start_time=time.time()
BubbleSort(a)
QuickSort(b)
use_time=time.time()-start_time
print 'Time used: '+str(use_time)
print a
print b[1:]

 

参考书目：《数据结构：C语言版》，  严蔚敏，吴伟民编著，  清华大学出版社

内容总结

以上是互联网集市为您收集整理的快速排序算法回顾 （Python实现）全部内容，希望文章能够帮你解决快速排序算法回顾 （Python实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---