The illustration | quick sort algorithm notes

Divide and conquer

Divide and conquer is to use the principle of recursion to convert a large sample into a small sample, and then solve it

Example 1: a 1680×640 farm should be divided into squares as large as possible?

If you’re going to do it recursively, you need to identify two places, a baseline condition and a recursive condition

The problem of dividing the largest block is a problem of finding the greatest common divisor, and the method of finding the greatest common divisor is the toss and turn division, that is, the greatest common divisor is the situation that satisfies both the above length and width divided by it is positive. As for how to find the greatest common divisor:

1680/640 = 2 (residual 400) 640/400 = 1(residual 240) 400/240 = 1(residual 160) 240/160 = 1(residual 80) 160/80 = 2 (residual 0)Copy the code

We realized that this is actually a recursion, and now we’re going to build a recursive function, and there are two conditions that we have to figure out for building a recursive function, one is the baseline condition and the body of the recursion

The baseline condition, as you can see from the above, is that the length/width modulus is 0, which is x%y==0,

Let’s implement this example in code:

php:

      

function findMaxLen($len.$width){
    $m = $len%$width;
    if ($m= =0) {return $width;
    }
    return findMaxLen($width.$m);
} 

$res = findMaxLen(1680.640);
var_dump($res);
Copy the code

golang:

package main

import "fmt"

func findMaxLen(len, width int) int {
	var m int = len % width
	if m == 0 {
		return width
	}
	return findMaxLen(width, m)
}

func main(a) {
	num := findMaxLen(1680.640)
	fmt.Println(num)
}

Copy the code

python:

def findMaxLen(len,width) :
    m=len%width
    if m==0:
        return width
    return findMaxLen(width,m)

print(findMaxLen(1680.640))
Copy the code

2. Quicksort

Quicksort is a kind of sorting using recursion, randomly selecting an element as a reference, using it to divide the sample into two parts, larger than it, smaller than it, But the samples on both sides may also be out of order, so recursively call the above method on both sides, select a reference, and repeat until there is one left, so that the next one can be compared to the reference, and it is ordered

Here’s how to do it:

python:

def quicksort(array) :
    if len(array)<2:
        return array 
    pivot=array[0]
    less=[i for i in array[1:] if i<=pivot]
    greater=[i for i in array[1:] if i>pivot]
    return quicksort(less)+[pivot]+quicksort(greater)
print(quicksort([1.2.30.40.5]))
Copy the code

php:

      

function quickSort($arr){
    if (count($arr) < =1) {return $arr;
    }
    $pivot = array_shift($arr);
    $less = [];
    $greater = [];

    foreach($arr as $v) {if($pivot>$v){
            array_push($less.$v);
        }else{
            array_push($greater.$v); }}$less = quickSort($less);
    $greater = quickSort($greater);
    return array_merge($less.array($pivot), $greater);
}
$a = array(1.30.2);
$res = quickSort($a);
var_dump($res);
Copy the code

golang:

package main

import "fmt"

func main(a) {
	num := []int{1.20.3}
	fmt.Println(qsort(num))
}

func qsort(num []int) []int {
	if len(num) <= 1 {
		return num
	}
	pivot := num[0]
	var less []int
	var greater []int
	for _, value := range num[1:] {
		if value <= pivot {
			less = append(less, value)
		} else {
			greater = append(greater, value)
		}
	}
	less = qsort(less)
	greater = qsort(greater)
	res := append(less, pivot)
	res = append(res, greater...)
	return res
}

Copy the code