首页 > 代码库 > 快速排序算法回顾 --冒泡排序Bubble Sort和快速排序Quick Sort（Python实现）
快速排序算法回顾 --冒泡排序Bubble Sort和快速排序Quick Sort（Python实现）
冒泡排序的过程是首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。以此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称为第一趟冒泡排序，接着第二趟对前面n-1个关键字进行同样操作，……
快速排序是对冒泡排序的一种改进，通过一趟排序将记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，可分别对这两部分记录以递归的方法继续进行排序，以达到整个序列有序。
单趟Partition()函数过程请看下面动图：
用Python进行实现：
#coding=utf-8import timea=[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 j+=1 i-=1#快速排序-------------------------------------------------------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)#---------------------------------------------------------------start_time=time.time()BubbleSort(a)QuickSort(b)use_time=time.time()-start_timeprint ‘Time used: ‘+str(use_time)print aprint b[1:]
参考书目：《数据结构：C语言版》， 严蔚敏，吴伟民编著， 清华大学出版社
快速排序算法回顾 --冒泡排序Bubble Sort和快速排序Quick Sort（Python实现）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。