您现在的位置是：首页 > Python

当前栏目

python 快排

Python 排序

2023-03-02 10:32:05 时间

**快排**:讲序列分成左右两部分，在每个部分中选一个基准，比基准小的放到它前面，比基准大的放到它后面。  
左右两个指针，同时向中间移动，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

猜你喜欢

最长无重复子串
写技术博客的一些心得分享
Java 多线程（七）：线程池
Java 多线程（五）：锁（三）
Java 多线程（四）：锁（二）
Java 多线程（三）：锁（一）
Java 多线程（二）：并发编程的三大特性
线性时间非比较类排序
Java 多线程（一）：基础
合并k个已排序的链表
HDFS 高可用分布式环境搭建
合并两个有序数组
连续子数组的最大和
HDFS 分布式环境搭建
容器盛水问题
大数加法
HDFS 伪分布式环境搭建
设计LRU缓存结构
两数之和
使用单调栈来解决的一些问题

zl程序教程

当前栏目

python 快排

相关文章