第一章讲的是分治算法,即DC,这一章讲的是快速排序QuickSort。作业难度已经增加了,Problem Sets做了两次一不小心只得了四分,编程作业也作了两次才作对。
这次作业是实现快速排序,并改变哨兵元素的选择方法比较性能。哨兵可以选择为第一个、最后一个元素,也可以选取首、尾、中间三个元素第二大的数字。
最后一种方法实现时可以借用list的排序方法。
代码如下:
def quickSort(arrayall):
if len(arrayall)<=1:return arrayall,0
#sel p
#p=0
#p=len(arrayall)-1
p=(len(arrayall)-1)/2
a=[(arrayall[0],0),(arrayall[p],p),(arrayall[-1],len(arrayall)-1)]
a.sort()
tmp,p=a[1]
if p!=0:
arrayall[0],arrayall[p]=arrayall[p],arrayall[0]
indi=1
for indj in range(1,len(arrayall)):
if arrayall[indj]<arrayall[0]:
arrayall[indi],arrayall[indj]=arrayall[indj],arrayall[indi]
indi+=1
arrayall[0],arrayall[indi-1]=arrayall[indi-1],arrayall[0]
arrayallp,mp=quickSort(arrayall[:indi-1])
arrayallq,mq=quickSort(arrayall[indi:])
return arrayallp+[arrayall[indi-1]]+arrayallq,mp+mq+len(arrayall)-1
f=open('QuickSort.txt','r')
listall=f.read()
listall=[int(x) for x in listall.split()]
f.close()
sortedlist,m=quickSort(listall)
print m
当然实验结果是最后一种方法性能比较优越。
分享到:
相关推荐
Algorithms for Non-negative Matrix论文描述希望帮助到大家
Algorithm-Problem-Solving-with-Algorithms-and-Data-Structures-using-Python.zip,使用python的算法和数据结构解决问题的代码,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
problem-solving-with-algorithms-and-data-structure-using-python 中文版
Chapter 1 - The Role of Algorithms in Computing Chapter 2 - Getting Started Chapter 3 - Growth of Functions Chapter 4 - Recurrences Chapter 5 - Probabilistic Analysis and Randomized ...
python-algorithms-mastering-basic-algorithms-in-the-python-language.9781430232377.53502.pdf
Chapter 1 - The Role of Algorithms in Computing Chapter 2 - Getting Started Chapter 3 - Growth of Functions Chapter 4 - Recurrences Chapter 5 - Probabilistic Analysis and Randomized ...
Beginning Algorithms----学习算法的好书,介绍各种算法!!!
python-algorithms-mastering-basic-algorithms-in-the-python-language(英文正版)1
Neo4j,用户手册,涵盖所有集成的图算法及应用场景,非常适合图算法的学习和应用
A-Comparative-Study-of-Reco-mmendation-Algorithms-in-E-Commerce-Applications
包括基本的数据结构,排序算法等。 Table of Contents Introduction to Algorithms, Second Edition Preface Part I - Foundations Chapter 1 - The Role of Algorithms in Computing Chapter 2 - Getting...
Introduction to algorithms ppt -----from USTC
Chapter 1 - The Role of Algorithms in Computing Chapter 2 - Getting Started Chapter 3 - Growth of Functions Chapter 4 - Recurrences Chapter 5 - Probabilistic Analysis and Randomized ...
Chapter 1 - The Role of Algorithms in Computing Chapter 2 - Getting Started Chapter 3 - Growth of Functions Chapter 4 - Recurrences Chapter 5 - Probabilistic Analysis and Randomized ...
Data Structures And Algorithms With Object-oriented Design Patterns In Java.chm
Data Structures and Algorithms with Object-Oriented Design Patterns in C++.rar Data Structures and Algorithms with Object-Oriented Design Patterns in C++.rar
《Introduction to Algorithms》---MIT教材 本书自第一版出版以来,已经成为世界范围内广泛使用的大学教材和专业人员的标准参考手册。本书全面论述了算法的内容,从一定深度上涵盖了算法的诸多方面,同时其讲授和...
Algorithms for hyper-parameter optimization.pdf,讲述贝叶斯算法的TPE过程的专业论文
遗传算法Python程序 Hands-On-Genetic-Algorithms-with-Python-master.zip