python 快速排序详解

python 快速排序详解 快速排序函数

def partition(arr,low,high): 
    i = ( low-1 )         #最小元素<索引>
    pivot = arr[high]     #选取最右边的数为基准
    
    for j in range(low , high): 
        # 判断当前元素是否小于或等于 pivot，有的话，和最小索引的值进行调换 
        if   arr[j] <= pivot: 
            i = i+1                         #有调换，i的索引值加1
            arr[i],arr[j] = arr[j],arr[i]   #把最小元素索引指向的值和 基数左边小于它的数交换。


    
    arr[i+1],arr[high] = arr[high],arr[i+1]  #把除去刚调换的值之后的索引，与最右边的数（基准数）交换 
    return ( i+1 )                          #返回索引
  
 
# arr[] --> 排序数组
# low  --> 起始索引
# high  --> 结束索引
  
# 快速排序函数
def quickSort(arr,low,high): 
    if low < high: 
  
        pi = partition(arr,low,high) 
  
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high) 
  
arr = [10, 7, 8, 9, 1, 5] 
n = len(arr) 
quickSort(arr,0,n-1) 
print ("排序后的数组:")
print(arr) 

eg：
快排过程

[10,7,8,9,1,5]   原始列表
[1,7,8,9,10,5]   将左边小于基准5的数与最小索引指向的数交换

[1,5,8,9,10,7]   将原先的基准数5 与 除去刚调换的值之后的索引7交换（索引进行了i+1 *** 作）
[1,5,7,9,10,8]   以此类推，将基准数7 为标准，判断左边的数有无小于基准数7的，没有，直接交换基准数与初始索引数，初始索引数为1+1
[1,5,7,8,10,9]  同上。


[1,5,7,8,9,10]  同上