python 快排

深碍√TFBOYSˉ_ 2022-05-08 02:42 222阅读 0赞

**快排**:讲序列分成左右两部分，在每个部分中选一个基准，比基准小的放到它前面，比基准大的放到它后面。  
左右两个指针，同时向中间移动，i++,j–,  
**实现思路**: 分成两部分需要一个partion分割函数，quicksort需要一个递归的函数

[图解参考][Link 1]  
快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)

a= [6 , 1 , 2, 7,9, 3, 4, 5,  10,  8]
    low_index = 0 
    high_index = len(a) -1

快排函数，（递归）

##
    def quick_sort(low_index, high_index):
    	if low_index < high_index:
    		middle = partion(low_index,high_index)
    		quick_sort(low_index,middle-1)
    		quick_sort(middle+1,high_index)

排序分割函数

def partion(i, j):
    	head = i
    	stand = a[i]　＃基准值
    	while  i < j :
    		#### j-- i++ until find a[j] < stand ,and a[i] > stand ,then change the value of i\j
    		＃ｊ一步步的向左挪动，直到找到比基准值小的，停下来，然后ｉ开始一步步向右挪动，直到找到比基准值大的，停下来，交换这两个值，继续向前挪动
    		
    		while i<j and a[j] >= stand:
    			j-=1
    		while i<j and a[i] <= stand :
    			i+=1
    			
    	　## 此时交换ｉ和ｊ的值
    		temp = a[j]
    		a[j] = a[i]
    		a[i] = temp
    		print "xxxxx",i,j
    	print "i,j",i,j  ### i should = j
    	assert i ==j 
    	
    	### change the middle and head 此时交换中间的和左边的基准值
    	temp_middle =a[i]
    	a[i] = stand
    	a[head] = temp_middle
    
    	 # i = j now is the middle 
    	return i

if __name__ == '__main__':
    	quick_sort(low_index,high_index)
    	print a

#### 参考 ####

[Link 1]: https://my.oschina.net/albert2011/blog/785604