编写一个快排算法对长度为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 【5，1，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))
