Commitf57eb34

authored

Merge pull requestJack-Lee-Hiter#8 from reece15/master

fix index out of range

2 parents0cbf915 +c4b94d1 commitf57eb34Copy full SHA for f57eb34

File tree

+14

-2

lines changed

+14

-2

lines changed

Lines changed: 14 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,3 +1,5 @@`
	`1`	`+# coding: utf-8`
	`2`	`+`
`1`	`3`	`defquickSort(alist):`
`2`	`4`	`quickSortHelper(alist,0,len(alist)-1)`
`3`	`5`
`@@ -16,9 +18,9 @@ def partition(alist, first, last):`
`16`	`18`	`done=False`
`17`	`19`
`18`	`20`	`whilenotdone:`
`19`		`-whilealist[leftmark]<=pivotvlueandleftmark<=rightmark:`
	`21`	`+whileleftmark<=rightmarkandalist[leftmark]<=pivotvlue:# bugfix: 先比较index, 不然数组会越界`
`20`	`22`	`leftmark+=1`
`21`		`-whilealist[rightmark]>=pivotvlueandrightmark>=leftmark:`
	`23`	`+whilerightmark>=leftmarkandalist[rightmark]>=pivotvlue:`
`22`	`24`	`rightmark-=1`
`23`	`25`
`24`	`26`	`ifleftmark>rightmark:`
`@@ -32,3 +34,13 @@ def partition(alist, first, last):`
`32`	`34`	`alist2= [1]`
`33`	`35`	`quickSort(alist2)`
`34`	`36`	`print(alist2)`
	`37`	`+`
	`38`	`+`
	`39`	`+if__name__=="__main__":`
	`40`	`+test_data= [3,2,111,3,-1,0,0,1,0,2,4]`
	`41`	`+`
	`42`	`+res_stable=sorted(test_data)`
	`43`	`+quickSort(test_data)`
	`44`	`+print(test_data)`
	`45`	`+print(res_stable)`
	`46`	`+assertall(map(lambdax:x[0]==x[1],zip(res_stable,test_data)))`

Comments

(0)