【算法学习】随机快速排序

it2022-05-06  0

要求:

编写一个快排算法对长度为n的序列进行排序,要求平均耗时为n*logn,内存占用较小。

方法:

随机选取一个数为pivot,然后遍历整个数组,小于pivot的放前面,大于pivot的放后面。然后再分别对前后两个数组进行递归调用。

eg.长度为N的序列:   【 1, 5, 3, 6, 2,10 】

STEP1:随机选取一个数为pivot,例如5

STEP2:交换pivot和第一个数【5,1,3,6,2,10】

STEP3:维护一个索引firstBigIndex,用于遍历时保存第二个数组的头索引。

STEP4: pivot和余下数组进行比较,小于pivot的置于firstBigIndex之前,大于的置于之后

a.index = 1 ,firstBigIndex = 1 【51,3,6,2,10】

1 < 5, 因此firstBigINdex往后移

b.index = 2,firstBigIndex = 2 【5,1,3,6,2,10】

3<5, firstBigIndex后移

c.index = 3,firstBigIndex = 3 【5,1,3,6,2,10】

6>5, firstBigIndex不动

d.index=4, firstBigIndex=3 【5,1,3,6,2,10】

2和fistBigIndex位置的6交换,firstBigIndex后移

5,1,3,2,6,10】

e.index = 5, firstBigIndex = 4 【5,1,3,2,6,10

5<10,firstBigindex不动

f.pivot和小数组的最后一个值(firstBigindex - 1位置处)交换

【2,1,3,5,6,10

完成基于pivot的排序,pivot前面的数都是小于该值得,后面都是大于该值的。再递归对前后两个数组进行排序即可,pivot的选举采用随机数来避免最差情况(例如,如果数组本来是从小到大排序的,每次选取第一个值作为pivot。那么数组大小在递归时的变化为n,n-1,n-2.....2,此时的耗时为O(n^2)。随机选取pivot,选取到的pivot的期望值在数组大小的中位数附件,可以保证每次递归的时候,数组大小按照一般的规模来减小。则 F(n) = 2F(n/2) + O(n), O(F(n)) = nlogn)该算法的特点是需要的额外空间小。

代码:

python:

recNum = 0 compareNum = 0 def swapSelf(listNum, Index1, Index2): tmp = listNum[Index1] listNum[Index1] = listNum[Index2] listNum[Index2] = tmp #自定义各自pivot随机选择办法 def selfRandom(numList, begin, end): #return end middle = (int)(begin + (end - begin) / 2) temp = [begin, middle, end] if (numList[temp[0]] > numList[temp[1]]): swapSelf(temp, 0, 1) if (numList[temp[0]] > numList[temp[2]]): swapSelf(temp, 0, 2) if (numList[temp[1]] > numList[temp[2]]): swapSelf(temp, 1, 2) print("temp", temp) return temp[1] def randSort(listNum, firstIndex, lastIndex): global recNum global compareNum recNum = recNum + 1 if firstIndex >= lastIndex: return compareNum = compareNum + lastIndex - firstIndex + 1 - 1 pivotIndex = selfRandom(numList, firstIndex, lastIndex) pivot = listNum[pivotIndex] swapSelf(listNum, firstIndex, pivotIndex) firstBigIndex = firstIndex + 1 index = firstIndex + 1 while(index <= lastIndex): if(listNum[index] <= pivot): swapSelf(listNum, index, firstBigIndex) firstBigIndex = firstBigIndex + 1 index = index + 1 pivotIndex = firstBigIndex - 1 swapSelf(listNum, pivotIndex, firstIndex) randSort(listNum, firstIndex, pivotIndex - 1) randSort(listNum, pivotIndex + 1, lastIndex) if __name__ == "__main__": numList = "" with open("QuickSort.txt") as f: a = f.readlines() numList = list(map(int, a)) randSort(numList, 0, len(numList) - 1) print(numList) print("compareNum", compareNum) print("listNum", len(numList))

 


最新回复(0)