排序算法-快速排序
一、快速排序
快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。
冒泡排序在每一轮中只把1个元素冒泡到数列的一端。而快速排序则在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。
这种思路就叫作分治法。
在分治法的思想下，原数列在每一轮都被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。 每一轮的比较和交换，需要把数组中的全部元素都遍历一遍，时间复杂度是O(n)。这样的遍历一共需要多少轮呢﹖假如元素个数是n，那么平均情况下需要logn轮，因此快速排序算法总体的平均时间复杂度是O ( nlogn)。
基准元素，英文pivot，在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边。
1、双边循环法。
2、单边循环法。
1、双边循环法
首先，选定基准元素pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素。
第1次循环，从right指针开始，让指针所指向的元素和基准元素做比较。如果right>=pivot，则指针向左移动(-1);如果right<pivot，则right指针停止移动(stop)，切换到left指针。
在当前数列中，1<4，所以right直接停止移动，换到left指针，进行下一步行动。轮到left指针行动，让指针所指向的元素和基准元素做比较。如果left<=pivot，则指针向右移动(+1);如果left>pivot，则left指针停止移动(stop)。
由于left开始指向的是基准元素，判断肯定相等，所以left右移1位。
由于7>4，left指针在元素7的位置停下。这时，让left指针和right指针所指向的元素进行交换。
def partition(start,end,ll):'''比较交换过程:param start: 开始索引:param end: 结束索引:param ll: 数列:return: 左边索引'''#取第一个元素为基准元素，也可以随机pirot=ll[start]#左边元素索引left=start#右边元素索引right=end#循环while left!=right:#控制right指针比较，并左移while left<right and ll[right]>=pirot:right -=1# 控制left指针比较，并右移while left<right and ll[left]<=pirot:left+=1#交换left指针和right指针的元素if left<right:#交换ll[left],ll[right]=ll[right],ll[left]#pirot与left,right指针重合ll[start]=ll[left]ll[left]=pirotreturn leftdef quickSort(start,end,ll):#递归结束if start>=end:return#获取基准元素位置pirot=partition(start,end,ll)#根据基准元素，分成两部分递归排序quickSort(start,pirot-1,ll)quickSort(pirot+1,end,ll)if __name__ == '__main__':ll=[4,7,6,5,3,2,8,1]print('排序前：')print(ll)#调用方法排序quickSort(0,len(ll)-1,ll)print('排序后：')print(ll)
2、单边循环法
只从数组的一边对元素进行遍历和交换。
开始和双边循环法相似，首先选定基准元素pivot。同时，设置一个mark指针指向数列起始位置，这个mark指针代表小于基准元素的区域边界。接下来，从基准元素的下一个位置开始遍历数组。
如果遍历到的元素>基准元素，就继续往后遍历。
如果遍历到的元素<基准元素，则需要做两件事:
第一，把mark指针右移1位，因为小于pivot的区域边界增大了1;
第二，让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小于pivot的区域。
首先遍历到元素7，7>4，所以继续遍历。
遍历到的元素是3，3<4，所以mark指针右移1位。
随后，让元素3和mark指针所在位置的元素交换，因为元素3归属于小于pivot的区域。
def partitionSingle(start,end,ll):# 取第一个元素为基准元素，也可以随机pirot = ll[start]# 标记索引mark = startfor i in range(start+1,end+1):#判断遍历的元素<基准元素if ll[i]<pirot:#右移1位mark+=1#交换p=ll[mark]ll[mark]=ll[i]ll[i]=pll[start]=ll[mark]ll[mark]=pirotreturn markdef quickSort(start,end,ll):#递归结束if start>=end:return#获取基准元素位置pirot=partitionSingle(start,end,ll)#根据基准元素，分成两部分递归排序quickSort(start,pirot-1,ll)quickSort(pirot+1,end,ll)
很明显，partitionSingle方法只要一个循环就OK，的确比双边循环法简单多了。
桃扇骨
你的名字
系统管理员
还没有评论，来说两句吧...