Leetcode algorithm interview sprint sorting algorithm theory (32)

Selection sort

Selection sort （Selection sort） It is a simple and intuitive sorting algorithm . It works as follows . First, find the minimum in the unsorted sequence （ Big ） Elements , To the beginning of the collating sequence , then , Continue to find the smallest from the remaining unsorted elements （ Big ） Elements , And then at the end of the sorted sequence . And so on , Until all the elements are sorted .

The main advantages of selective sorting are related to data movement . If an element is in the right final position , Then it will not be moved . Select sort to exchange one pair of elements at a time , At least one of them will be moved to its final position , So right. n The table of elements can be sorted at most n-1 Secondary exchange . In all sorts of sorting methods that rely entirely on swapping to move elements , Sorting by choice is a very good .

def select_sort(li):
    n = len(li)
    for i in range(n - 1):
        for j in range(i + 1, n):
            if li[j] < li[i]:
                li[i], li[j] = li[j], li[i]

Insertion sort

Insertion sort （ English ：Insertion Sort） It is a simple and intuitive sorting algorithm . It works by building an ordered sequence , For unsorted data , Scan backward and forward in sorted series , Locate and insert . Insert sort in implementation , In the process of scanning from back to front , The elements have been moved back and forth , Provide insertion space for the latest elements .

def insert_sort(li):
    n = len(li)
    for i in range(1, n):
        for j in range(i, 0, -1):
            if li[j] < li[j - 1]:
                li[j], li[j - 1] = li[j - 1], li[j]
            else:
                break

Bubble sort

Bubble sort （ English ：Bubble Sort） It's a simple sort algorithm . It iterates over the sequence to be ordered , Compare two elements at a time , If they're in the wrong order, exchange them . The work of traversing the sequence is repeated until there is no need to exchange any more , That is to say, the sequence has been sorted . The name of this algorithm comes from the fact that the smaller the elements, the more slowly “ floating ” Go to the top of the list .

The bubble sort algorithm works as follows ：

Compare adjacent elements . If the first one is bigger than the second one （ Ascending ）, Just swap them .
Do the same for each pair of adjacent elements , From the beginning of the first couple to the end of the last couple . After this step , The last element will be the maximum number .
Repeat the above steps for all elements , Except for the last one .
Keep repeating the above steps for fewer and fewer elements each time , Until there's no pair of numbers to compare .

def bubble_sort(li):
    n = len(li)
    for i in range(n):
        for j in range(n - 1 - i):
            if li[j] > li[j + 1]:
                li[j], li[j + 1] = li[j + 1], li[j]

Merge sort

The writing is still a little stumbling

def merge_sort(li, left, right):
    if left >= right: return
    mid = (left + right) // 2
    merge_sort(li, left, mid)
    merge_sort(li, mid + 1, right)
    merge(li, left, mid, right)


def merge(li, left, mid, right):
    i, j = left, mid + 1
    tmp = []
    while i <= mid and j <= right:
        if li[i] < li[j]:
            tmp.append(li[i])
            i += 1
        else:
            tmp.append(li[j])
            j += 1

    while i <= mid:
        tmp.append(li[i])
        i += 1
    while j <= right:
        tmp.append(li[j])
        j += 1
    li[left:right + 1] = tmp


li = [2, 5, 1, 3, 4, 6]
left, right = 0, len(li) - 1
merge_sort(li, left, right)

532 · Reverse alignment

Two numbers in an array if the first number is greater than the next number , Then these two numbers form a reverse order pair . Give you an array , Find the total number of reverse pairs in this array .
Generalization ： If a[i] > a[j] And i < j, a[i] and a[j] Form a reverse order pair .

from typing import (
    List,
)

class Solution:
    """ @param a: an array @return: total of reverse pairs """
    def reverse_pairs(self, a: List[int]) -> int:
        # write your code here
        left, right = 0, len(a) - 1
        self.reverse_num = 0
        self.merge_sort(a, left, right)
        return self.reverse_num


    def merge_sort(self, a, left, right):
        if left >= right:
            return
        mid = (left + right) // 2
        self.merge_sort(a, left, mid)
        self.merge_sort(a, mid + 1, right)
        self.merge(a, left, mid, right)
    

    def merge(self, a, left, mid, right):
        i, j = left, mid + 1
        tmp = []
        while i <= mid and j <= right:
            if a[i] <= a[j]:
                tmp.append(a[i])
                i += 1
            else:
                self.reverse_num += mid - i + 1
                tmp.append(a[j])
                j += 1
        while i <= mid:
            tmp.append(a[i])
            i += 1
        while j <= right:
            tmp.append(a[j])
            j += 1
        a[left:right + 1] = tmp
   

Quick sort

And in > and >= And so on , Erroneous , I can only say that I didn't understand it thoroughly .

def quick_sort(arr, left, right):
    if left >= right: return
    start, end = left, right
    pivot = arr[start]
    while left <= right:
        while left <= right and arr[left] < pivot:
            left += 1
        while left <= right and arr[right] > pivot:
            right -= 1
        if left <= right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1
    quick_sort(arr, start, right)
    quick_sort(arr, left, end)


li = [2, 5, 1, 3, 4, 6]
left, right = 0, len(li) - 1
quick_sort(li, left, right)
print(li)

1854 · Array partition III

Give you an array of integers and an integer K, Please judge whether the array can be divided into several sizes k Sequence , And meet the following conditions ：

Every number in the array appears in exactly one sequence
The numbers in a sequence are different from each other
The same elements in an array are divided into different sequences
Whether the array meeting the above conditions can be partitioned ？ If possible , return true, Otherwise return to false.

Array length is less than or equal to 10^5.

No comprehension , Just look at the answer ：

def partitionArratIII(self, array, k):
        
        length = len(array)
        if length % k != 0:
            return False
        count = collections.Counter(array)
        for key, value in count.items():
            if value >= (length // k):
                return False
        
        return True