快速排序 and 归并排序(python)

2019-11-06 08:40:38

字体：大中小

来源：转载

供稿：网友

快速排序:

#QuickSort by Alvindef QuickSort(myList,start,end): #判断low是否小于high,如果为false,直接返回 if start < end: i,j = start,end #设置基准数 base = myList[i] while i < j: #如果列表后边的数,比基准数大或相等,则前移一位直到有比基准数小的数出现 while (i < j) and (myList[j] >= base): j = j - 1 #如找到,则把第j个元素赋值给第个元素i,此时表中i,j个元素相等 myList[i] = myList[j] #同样的方式比较前半区 while (i < j) and (myList[i] <= base): i = i + 1 myList[j] = myList[i] #做完第一轮比较之后,列表被分成了两个半区,并且i=j,需要将这个数设置回base myList[i] = base #递归前后半区 QuickSort(myList, start, i - 1) QuickSort(myList, j + 1, end) return myListmyList = [49,38,65,97,76,13,27,49]PRint("Quick Sort: ")QuickSort(myList,0,len(myList)-1)print(myList)

归并排序:

def mergesort(seq): if len(seq)<=1: return seq mid=int(len(seq)/2) left=mergesort(seq[:mid]) right=mergesort(seq[mid:]) return merge(left,right)def merge(left,right): result=[] i,j=0,0 while i<len(left) and j<len(right): if left[i]<=right[j]: result.append(left[i]) i+=1 else: result.append(right[j]) j+=1 result+=left[i:] result+=right[j:] return resultif __name__=='__main__': seq=[4,5,7,9,7,5,1,0,7,-2,3,-99,6] print(mergesort(seq))

上一篇：【Python】利用pydub库操作音频文件

下一篇：python 解一元二次方程方法汇总