Use python to implement 8 sorting algorithms-quick sort

Basic idea of ​​quick sort:

Split the data to be sorted into two independent parts through one sorting. All the data in one part is smaller than all the data in the other part, and then use this method to sort the two parts of the data. Quick sort is performed separately, and the entire sorting process can be performed recursively, so that the entire data becomes ordered.

Example:

arr = [49,38,04,97,76,13,27,49,55,65], set the first digit 49 as the key value, and find the number smaller than the key value from right to left , assign the found number to the first digit;

arr = [27,38,04,97,76,13,27,49,55,65], and then find the key value from the first digit on the left to the right For large numbers, assign the found number to the last number found from right to left;

arr = [27,38,04,97,76,13,97,49,55,65], and then proceed from right to left Left, from left to right, until left=right, break out of the loop, and assign the key value to some index value. Finally, recurse the groups on both sides.

Code:

def quick_sort(lists, left, right):  
    #快速排序  
    if left >= right:  #当递归调用的分组为1个数时返回列表  
        return lists  
    key = lists[left]  #保存key值，在一轮调用结束时，存到中间值  
    low = left  
    high = right  #供递归调用时使用  
    while left < right:  #通过下面两个循环依次交替赋值并使key值两侧为大小分组  
        while left < right and lists[right] >= key:    
            right -= 1  
        lists[left] = lists[right]  
        while left < right and lists[left] <= key:  
            left += 1  
        lists[right] = lists[left]  
    lists[right] = key  
    quick_sort(lists, low, left-1)  #对key值左侧进行排序分组  
    quick_sort(lists, left+1, high)  #对key值右侧进行排序分组  
    return lists