常见算法之快速排序

算法原理

快速排序是对冒泡排序的改进，采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到序列不可再分，最终得到一个有序的序列。

单指针实现

def partition(arr, low, high):
    i = low  
    pivot = arr[high]

    for j in range(low, high):
        print(data[low:high])
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i = i + 1
    arr[i], arr[high] = arr[high], arr[i]
    return i

def quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)

        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)
    return arr 
  

双指针实现

def quick_sort(arr,left,right):
    if left < right:
        temp = arr[left]
        i,j = left,right
        while i < j:
            while arr[j] >= temp and i < j:
                j -= 1
            while arr[i] <= temp and i < j:
                i += 1

            if i < j:
                arr[i],arr[j] = arr[j],arr[i]
        
        arr[i],arr[left] = arr[left],arr[i]
        print(arr)
        quick_sort(arr,left,i-1)
        quick_sort(arr,i+1,right)
    return arr
    ```