<jupyter_start><jupyter_text>快速排序 Quick Sort<jupyter_code>import numpy as np

def test_sort(f, n):
    import numpy as np
    a=np.random.randint(0, 10, n)
    print("arr before: ", a[:10])
    print("time used: ")
    %time f(a)
    print("arr after: ", a[:10])
def quick_sort(arr):
    def __partition(arr, l , r):
        """
        对数组arr[l...r]进行分区，以第一个元素为标准，使得数组的左边都小于该元素，而数组的右边都大于该元素
        返回值p，使得arr[l.....p-1]都小于arr[p]，并且arr[p+1...r]都大于arr[p]
        """
        
        """
        （2）优化方法：每次都是以第一个元素作为标定点的话，对于完全有序的数组，
        会导致递归树深度为N，算法复杂度退化到O(N^2)。
        解决的方法：随机选择标定点。
        """
        
        """
        随机选择标定点，
        与第一个元素交换位置        
        
        rnd=np.random.randint(l, r+1)
        t=arr[rnd]
        arr[rnd]=arr[l]
        arr[l]=t
        """
        
        v=arr[l]
        j=l
        for i in range(l+1, r+1):
            if arr[i]<v:
                # 交换位置
                t=arr[i]
                arr[i]=arr[j+1]
                arr[j+1]=t
                
                j+=1
        arr[l]=arr[j]
        arr[j]=v
        return j
        
    def __quick_sort(arr, l, r):
        """
        对数组arr[l...r]前闭后闭进行快速排序
        """
        
        """
        （1）改进方法：当子数组的规模较小的时候（10-20左右），可以集成使用其他的排序方法，例如插入排序等。
        """
        if l>=r:
            return
        # 以数组arr的第一个元素为标准，返回数组arr[l...r]的分界点
        p=__partition(arr, l, r)
        # 递归地对arr[l...p-1] 和 arr[p+1...r] 分别进行快速排序
        __quick_sort(arr, l, p-1)
        __quick_sort(arr, p+1, r)
    
    __quick_sort(arr, 0, len(arr)-1)
import sys
sys.setrecursionlimit(10000)
test_sort(quick_sort, 10000)<jupyter_output>arr before:  [7 6 7 3 1 8 6 7 8 6]
time used: 
Wall time: 701 ms
arr after:  [0 0 0 0 0 0 0 0 0 0]<jupyter_text>优化方法： （1）与归并算法相似，当数组经过分区后，子数组的规模会不断减小。当子数组的规模减小到比较小的情况下（例如：子数组的长度10~20），此时，针对该子数组，可以使用其他排序方法，例如：插入排序等。 （2）由于通常是以第一个元素作为标定点，将数组进行分区。因此，极端情况下，数组是完全有序的，那么，每次分区，只是把第一个元素减掉而已，继续对剩下的子数组进行分区。因此，该情况下，递归树的深度将达到N，算法复杂度会退化到O(N^2)级别。此时的递归树是不平衡的。优化的思路是：不再以第一个元素作为标准点，而是随机选择一个元素，作为标准点。降低递归树的深度。 （3）在归并算法中，每次机会都是将数组左右均分，因此，递归树的深度为log(N)。这样的递归树是平衡树。<jupyter_code>np.random.randint(0,9)<jupyter_output><empty_output><jupyter_text>上述算法中，将小于v的放在左边，大于v的放在右边。 如果在数组中，v重复的次数非常多（例如：数组规模是百万，而每个数都是0-9之间的取值），那么，会导致，分区的时候，两个区非常不平衡。分区不平衡，就有很大可能，导致递归树深度过大，以至于退化为O(N^2)的极端情况。  在重复键值中，效率更高<jupyter_code>def quick_sort_2(arr):
    import numpy as np
    def __partition_2(arr, l, r):
        """
        随机找到标定点
        """
        rnd=np.random.randint(l, r+1)
        """
        将标定点交换到第一个元素位置
        """
        t=arr[rnd]
        arr[rnd]=arr[l]
        arr[l]=t
        
        """
        标定点v
        """
        v=arr[l]
        
        """
        注意区间闭合情况：
        arr[l+1...i) <=v
        arr(j...r] >=v
        
        i,j 这样的初始化，目的是，保证上述两个区间是空的
        """
        i=l+1
        j=r
        
        while True:
            """
            直到遇到第一个大于等于v的元素
            """
            while i<=r and arr[i]<v:
                i+=1
            
            """
            直到遇到第一个小于等于v的元素
            """
            while j>=(l+1) and arr[j]>v:
                j-=1
            
            if i>j:
                break
            
            t=arr[i]
            arr[i]=arr[j]
            arr[j]=t
            
            i+=1
            j-=1
            
        t=arr[j]
        arr[j]=v
        arr[l]=t
        return j
    
    def __quick_sort_2(arr, l, r):
        if l>=r:
            return
        
        p=__partition_2(arr, l ,r)
        
        __quick_sort_2(arr, l, p-1)
        __quick_sort_2(arr, p+1, r)
    
    __quick_sort_2(arr, 0, len(arr)-1)
test_sort(quick_sort_2, 10000)<jupyter_output>arr before:  [0 6 2 3 9 8 5 9 8 4]
time used: 
Wall time: 66 ms
arr after:  [0 0 0 0 0 0 0 0 0 0]<jupyter_text>三路快排 Quick Sort 3 Ways  在处理具有较多的重复键值数组中，效率很显著的好<jupyter_code>def quick_sort_3(arr):
    import numpy as np
    def __partition_3(arr, l, r):
        """
        随机找到标定点
        """
        rnd=np.random.randint(l, r+1)
        """
        将标定点交换到第一个元素位置
        """
        t=arr[rnd]
        arr[rnd]=arr[l]
        arr[l]=t
        
        """
        标定点v
        """
        v=arr[l]
        
        """
        arr[l+1...lt]<v
        arr[lt+1...i)==v
        arr[gt...r]>v
        """
        lt=l
        i=l+1
        gt=r+1
        
        while i<gt:
            if arr[i]<v:
                t=arr[i]
                arr[i]=arr[lt+1]
                arr[lt+1]=t
                
                i+=1
                lt+=1
            elif arr[i]==v:
                i+=1
            else:
                t=arr[i]
                arr[i]=arr[gt-1]
                arr[gt-1]=t
                
                gt-=1
        t=arr[lt]
        arr[lt]=v
        arr[l]=t
        
        lt-=1
        
        return lt,gt
    
    def __quick_sort_3(arr, l, r):
        if l>=r:
            return
        
        lt,gt=__partition_3(arr, l ,r)
        __quick_sort_3(arr, l, lt)
        __quick_sort_3(arr, gt, r)
    
    __quick_sort_3(arr, 0, len(arr)-1)
test_sort(quick_sort_3, 100000)<jupyter_output>arr before:  [2 9 4 0 9 2 8 2 5 6]
time used: 
Wall time: 226 ms
arr after:  [0 0 0 0 0 0 0 0 0 0]
StarcoderdataJupyterStructuredCleanDedup