Recursion: quick sort, merge sort and heap sort

Quick sort

The idea of quick sorting is very simple , Look for any element as a pacesetter , Then use the double pointer to move from left to right ,

1. First, let the right pointer point to the end of the array R=len(arr)-1, Then judge whether it is equal to the pacesetter element , If it is greater than, the right pointer will continue to move to the left , namely R -=1, Until you find a position smaller than the pacesetter
2. Then let the left pointer point to the beginning of the array , Then judge whether it is less than or equal to the pacesetter element , If it is less than, the pointer will continue to move to the right , namely L += 1, Until we find the position of the feather pacesetter
3. Finally, exchange two elements , Put the large element on the right , Put small elements on the left . The left and right pointers continue , Until the two hands meet

You can see that quick sorting is actually an operation of continuous exchange , After one round of operation , Then perform the same operation on the left and right data , Turn a big problem into a small one , So the recursive algorithm is used for fast sorting .

There are two points in quick row that are very easy to make mistakes

1. When compared with the pacesetter, the equal sign is included . This is because many data in the array may be the same as the pacesetter , In fact, the same elements as pacesetters can be placed on the left and right , Anyway, after the final sorting, it will be adjacent to the pacesetter . And it can also avoid falling into a dead cycle . For example, the following array , If you don't add an equal sign , You'll find that l and r Will not change .
   

2. The outermost loop is easier to understand , requirement i<j, If l==r Just go straight back , There's no need to sort , But there is still one in the inner circle i<j, Why is that ？ Mainly to prevent the array from crossing the boundary

3. When i And j On equal terms , This round of exchange is over , Then exchange this element with the pacesetter element , The pacesetter element is where he should be .

It is easier to understand quick sort from the perspective of binary tree , The first is to find the root node , Then divide the data into two parts according to the root node , The left side is less than or equal to the root node , The right side is greater than or equal to the root node . Then recurse down continuously .

Here's an optimization , Is to use random selection pivot, In this way, it can also have good performance in the original incremental array . If it was originally a sorted arr, Then it will degenerate into $O(n^2)$.

  def quickSort(arr, l, r):
      if l >= r:             #  Recursion ends 
          return  

      pivot_idx = random.randint(l, r)                   #  Random selection pivot
      arr[l], arr[pivot_idx] = arr[pivot_idx], arr[l]     # pivot Place to the far left 
      pivot = arr[l]                                        #  Select the leftmost as pivot

      i, j = l, r     #  Double pointer 
      while i < j:
          
          while i<j and arr[j] >= pivot:          #  Find the first one on the right <pivot The elements of 
              j -= 1
          
          while i<j and arr[i] <= pivot:           #  Find the first one on the left >pivot The elements of 
              i += 1
          
          arr[i],arr[j] = arr[j],arr[i]       #  And move it to right It's about 
      arr[l],arr[i] = arr[i],pivot

      quickSort(arr, l, i-1)          #  Recursive pair mid Sort the elements on both sides 
      quickSort(arr, i+1, r)
  
  quickSort(arr, 0, len(arr)-1)         #  Call the quick sorting function pair nums Sort 
  return nums

Merge sort

The bottom layer of merge sort is also recursive thinking , In fact, root quicksort is very similar . Merge sort has two points

1. We divide the array into two , Left and right . If we arrange on the left , Then the right side is also in order , At this time, you only need to combine the two sub arrays into one . So how to sort the left and right arrays ？ Let's first look at the array on the left , We also divide the array on the left into two parts , If these two parts are in good order , We can merge directly . Now you can see that , We put the big sorting problem , It is transformed into the sorting problem and merging problem of each word part .
   
   This process is very simple to write recursively

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:

        def mergesort(arr, l, r):
            if l >= r:
                return
            m = (l + r) // 2
            mergesort(arr,l,m) #  Left half sort 
            mergesort(arr,m+1,r) #  Sort the right half 

            #  Arrange the left and right parts of the order before merging 

            #  The range of the array on the left is l~m
            #  The range of the array on the right is m+1~r
            #  Now is to merge these two ordered arrays 
            i,j = l,m+1
            tmp = []
            while i <= m and j <= r:
                if arr[i] < arr[j]:
                    tmp.append(arr[i])
                    i += 1
                else:
                    tmp.append(arr[j])
                    j += 1
            tmp += arr[i:m+1]
            tmp += arr[j:r+1]
            for k in range(l,r+1):
                arr[k] = tmp[k-l]

        mergesort(nums, 0, len(nums)-1)         #  Call the quick sorting function pair nums Sort 
        return nums