快速排序的介绍
快速排序(quick sort)的采用了分治的策略。
先来看一个 我更想称之为伪快排的快排代码
def quick_sort(array): if len(array) < 2: return array else: pivot = array[0] less_than_pivot = [x for x in array if x <= pivot] more_than_pivot = [x for x in array if x > pivot] return quick_sort(less_than_pivot) + [pivot] + quick_sort(more_than_pivot)
这段代码最关键的是pivot这个参数，这段代码里取序列的第一个元素，然后以这个元素为分组的基准，利用列表解析式使得它左边的值都比它小，右边的值都比它大。然后再分别对这些序列进行递归排序。
这段代码虽然短小利于理解，但是其效率很低，主要体现在以下方面：
QuickSort by Alvin def 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 myList myList = [49,38,65,97,76,13,27,49] print("Quick Sort: ") QuickSort(myList,0,len(myList)-1) print(myList)
原文：https://www.cnblogs.com/zknublx/p/11965400.html