一起Lintcode!------- Sort Integers II (对几种快速排序算法的总结)


  • 太阁x英雄榜

    本贴将对几种不同思路的quicksort进行总结,以后绝对不会再入坑!

    第一种方法:前后两个指针往中间扫,碰到符合条件的进行交换。 该方法是十分常用的方法,例如quickselect以及lintcode中很多题目都是源于该方法。但是在quicksort中,由于选取pivot则坑变得很多。一定要注意。

    def quicksort(self, A, start, end):
        index = self.partition(A, start, end)
        if start < index-1:
            self.quicksort(A, start, index-1)
        if index < end :
            self.quicksort(A, index , end)
        return
    
    def partition(self, A, start, end):
        i = start
        j = end 
        pivot = A[(i+j)/2]
        while(i <= j):
            while( A[i] < pivot):
                i += 1 
            while( A[j] > pivot):
                j -= 1
            if i <= j:    
                A[i], A[j] = A[j], A[i]
                i += 1
                j -= 1
        return i
    
    def sortIntegers2(self, A):
        # Write your code here
        if(len(A) <= 1 ):
            return A
        self.quicksort(A, 0, len(A)-1)
        return A
    

    第二种写法:
    选取最右边作为pivot,然后从头到最后一个元素前的一个元素进行遍历。如果发现比pivot值小的元素,则与标记位的元素进行交换。 但是如果该序列已经为升序情况,这样算法的时间复杂度退化为n^2.

    def quicksort(self, A, start, end):
       if (start < end):
            index = self.partition(A, start, end)
            self.quicksort(A, start, index-1)
            self.quicksort(A, index + 1 , end)
      return
    
    def partition(self, A, start, end):
        pivot = A[end]
        i = start
        for j in range(start, end):
            if (A[j] < pivot):
                A[i], A[j] = A[j], A[i]
                i += 1
        A[i],A[end] = A[end], A[i]
        return i
    
    def sortIntegers2(self, A):
        # Write your code here
        if(len(A) <= 1 ):
            return A
        self.quicksort(A, 0, len(A)-1)
        return A
    

    一些有用的quicksort讲解:

    https://www.toptal.com/developers/sorting-algorithms/quick-sort-3-way
    http://www.algolist.net/Algorithms/Sorting/Quicksort
    http://me.dt.in.th/page/Quicksort/



  • 感谢LZ分享 !
    干货,mark一记!


登录后回复
 

与 BitTiger Community 的连接断开,我们正在尝试重连,请耐心等待