## Preface

Recently, I've been （ Enter into ） Ten （ door ） Algorithm , I can only take notes for a little comfort , Record and share here , It will be summarized into a series later . such as 「 Recursion and backtracking 」、「 Depth and breadth first 」、「 Dynamic programming 」、「 Two point search 」 and 「 greedy 」 etc. .

## Bubble sort （Bubble Sort）

### Basic idea of bubble sorting

Given an array , We pour all the elements in the array into the pool , These elements will be compared with each other , In order of size, one by one, it surfaced like bubbles .

### Bubble sort implementation

Every round , Start with the messy array header , Every two elements are compared in size and exchanged , Until the largest or smallest element in this round is placed at the end of the array , Then repeat the process , Until all the elements are in place . among , The core operation is to compare elements with each other .

### Bubble sorting example analysis

Given array `[2, 1, 7, 9, 5, 8]`

, From left to right 、 Sort from small to large .

### Bubble sorting problem solving ideas

Bubble from left to right , Move the larger number to the right .

- First, the pointer points to the first number , Compare the size of the first number and the second number , because
`2`

Than`1`

Big , So swap two ,`[1, 2, 7, 9, 5, 8]`

. - Next, the pointer moves one step forward , Compare
`2`

and`7`

, because`2`

Than`7`

Small , Both remain stationary ,`[1, 2, 7, 9, 5, 8]`

. up to now ,`7`

It's the largest number . - The pointer continues to move forward , Compare
`7`

and`9`

, because`7`

Than`9`

Small , Both remain stationary ,`[1, 2, 7, 9, 5, 8]`

. Now? ,`9`

Became the largest number . - Further back , Compare
`9`

and`5`

, Obviously ,`9`

Than`5`

Big , Exchange their positions ,`[1, 2, 7, 5, 9, 8]`

. - Last , Compare
`9`

and`8`

,`9`

Than`8`

Big , Exchange their positions ,`[1, 2, 7, 5, 8, 9]`

. After the first round of pairwise comparison ,`9`

The largest number appears at the end of the array like a bubble . - Next, let's make a second round of comparison , Re point the pointer to the first element , Repeat the above , Last , The array becomes ：
`[1, 2, 5, 7, 8, 9]`

. - In a new round of comparison , Judge whether there was a pairwise exchange in the last round of comparison , If an exchange doesn't happen , It proves that the array is in order .

### Bubble sort code example

```
// Bubble sort algorithm
const bubbleSort = function (arr) {
const len = arr.length
// Mark whether each round occurs to exchange
let hasChange = true
// If there is no exchange, it is already in order , Just jump out of the outer layer
for (let i = 0; i < len && hasChange; i++) {
hasChange = false
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
hasChange = true
}
}
}
}
const arr = [2, 1, 7, 9, 5, 8]
bubbleSort(arr)
console.log('arr: ', arr)
```

### Analysis of bubble sort algorithm

#### Bubble sort space complexity

Suppose the number of elements in the array is `n`

, Because in the whole sorting process , We exchange elements directly in a given array , So the spatial complexity is `O(1)`

.

#### Bubble sort time complexity

The given array has been arranged in order

- under these circumstances , We just need to do
`n−1`

The second comparison , The number of pairwise exchanges is`0`

, The time complexity is`O(n)`

. This is the best case . - The given array is arranged in reverse order . under these circumstances , We need to do
`n(n-1)/2`

Compare it to , The time complexity is`O(n2)`

. This is the worst case scenario . - The given array is messy . under these circumstances , The average time complexity is
`O(n2)`

.

thus it can be seen , The time complexity of bubble sorting is `O(n2)`

. It's a stable sort algorithm .（ Stability means that if there are two equal numbers in the array , Then the relative positions of these two equal numbers before and after sorting remain unchanged .）

## Insertion sort （Insertion Sort）

### The basic idea of insertion sort

Continuously insert numbers that have not been ordered into the ordered parts .

### Insert sort feature

In bubble sorting , After each round of sorting , The numbers at the back end of the array are in good order ; For insert sort , After each round of sorting , The numbers at the front of the array are in good order .

### Insert sorting example analysis

An array `[2, 1, 7, 9, 5, 8]`

Insert sort .

### Insert sorting problem solving ideas

- First, divide the array into left and right parts , On the left is the ordered part , On the right is the part that hasn't been arranged yet , At first , The ordered part on the left has only the first element
`2`

. Next , We deal with the elements on the right one by one , Put them on the left .

- First look
`1`

, because`1`

Than`2`

Small , Need to put`1`

Insert into`2`

In front of , It's easy to do , Just switch positions in pairs ,`[1, 2, 7, 9, 5, 8]`

. - then , We are going to put
`7`

Insert into the left part , because`7`

Have more than`2`

big , That means it's the biggest element right now , Keep the position ,`[1, 2, 7, 9, 5, 8]`

. - Empathy ,
`9`

There is no need to change the position ,`[1, 2, 7, 9, 5, 8`

]. - Next , How to make
`5`

Insert in place . Compare first`5`

and`9`

, because`5`

Than`9`

Small , In exchange ,`[1, 2, 7, 5, 9, 8`

], continue , because`5`

Than`7`

Small , In exchange ,`[1, 2, 5, 7, 9, 8]`

, Last , because`5`

Than`2`

Big , This round is over . - The last number is
`8`

, because`8`

Than`9`

Small , In exchange ,`[1, 2, 5, 7, 8, 9]`

, Compare again`7`

and`8`

, Find out`8`

Than`7`

Big , This round is over . Here we are , Insert sort complete .

### Insert sort code example

```
// Insertion sort
const insertionSort = function (arr) {
const len = arr.length
for (let i = 1; i < len; i++) {
let current = arr[i]
for (let j = i - 1; j >= 0; j--) {
// current Less than j The value pointing to the left of , take j Point to the left and shift the value one bit to the right
if (current < arr[j]) {
arr[j + 1] = arr[j]
} else {
// Otherwise it would be current Insert into j Location , Jump out of the inner loop
arr[j] = current
break
}
}
}
}
const arr = [2, 1, 7, 9, 5, 8]
insertionSort(arr)
console.log('arr: ', arr)
```

### Insert sort algorithm analysis

#### Insert sort space complexity

Suppose the number of elements in the array is `n`

, Because in the whole sorting process , Is to exchange elements directly in a given array , The space complexity is `O(1)`

.

#### Insert sort time complexity

- The given array has been arranged in order . Just do it
`n-1`

The second comparison , The number of pairwise exchanges is`0`

, The time complexity is`O(n)`

. This is the best case . - The given array is arranged in reverse order . under these circumstances , We need to do
`n(n-1)/2`

Compare it to , The time complexity is`O(n2)`

. This is the worst case scenario . - The given array is messy . under these circumstances , The average time complexity is
`O(n2)`

.

thus it can be seen , It's the same as bubbling , The time complexity of insertion sort is `O(n2)`

, And it is also a stable sorting algorithm .

## Merge sort （Merge Sort）

### The basic idea of merge sort

The core is divide and conquer , Is to divide a complex problem into two or more identical or similar subproblems , Then divide the subproblem into smaller subproblems , Until the subproblem can be simply solved directly , The solution of the original problem is the combination of the solutions of the subproblems . Merging and sorting embody the idea of division and rule incisively and vividly .

### Merge sort implementation

First, divide the array into two sub arrays from the middle , Always recursively divide the subarray into smaller subarrays , Until there is only one element in the subarray , Just start sorting .

The way to sort is to merge two elements in size order , Then, according to the recursive return order , Constantly merge ordered subarrays , Until the end, put the whole array in order .

### Merge sort code example

```
// Merge sort
const mergeSort = function (arr, lo, hi) {
if (lo === undefined) {
lo = 0
}
if (hi === undefined) {
hi = arr.length - 1
}
// Determine if the last element is left
if (lo >= hi) return
// Divide the array into two parts from the middle
let mid = lo + Math.floor((hi - lo) / 2)
console.log('mid', mid)
// Recursively arrange the left and right sides respectively
mergeSort(arr, lo, mid)
mergeSort(arr, mid + 1, hi)
// Merge the ordered left and right halves
merge(arr, lo, mid, hi)
}
const merge = function (arr, lo, mid, hi) {
// Copy an original array
const copy = [...arr]
// Define a k The pointer indicates where to start modifying the original array ,
// i The pointer indicates the starting position of the left half
// j The pointer is the actual position of the right half
let k = lo
let i = lo
let j = mid + 1
while (k <= hi) {
if (i > mid) {
arr[k++] = copy[j++]
} else if (j > hi) {
arr[k++] = copy[i++]
} else if (copy[j] < copy[i]) {
arr[k++] = copy[j++]
} else {
arr[k++] = copy[i++]
}
}
}
const arr = [2, 1, 7, 9, 5, 8]
mergeSort(arr)
console.log('arr: ', arr)
```

among ,`While`

Statements are , There are four possible situations .

- The numbers on the left half are processed , Only the number left on the right half , Just copy the numbers on the right half one by one .
- The numbers on the right half are processed , Only the number left , Just copy the numbers on the left half one by one .
- The number on the right is less than the number on the left , Copy the number on the right to the appropriate location ,
`j`

The pointer moves forward one bit . - The number on the left is less than the number on the right , Copy the number on the left to the appropriate location ,
`i`

The pointer moves forward one bit .

### Example analysis of merging and sorting

Use the merge sort algorithm to sort the array `[2, 1, 7, 9, 5, 8]`

Sort .

### Merging and sorting problem solving ideas

First, keep slicing the array , Until each subarray contains only one element .

Next, the cut sub arrays are merged recursively in size order , The order of recursion is similar to the forward traversal in a binary tree .

- Merge
`[2]`

and`[1]`

by`[1, 2]`

. - Subarray
`[1, 2]`

and`[7]`

Merge . - On the right , Merge
`[9]`

and`[5]`

. - Then merge
`[5, 9]`

and`[8]`

. - Final merger
`[1, 2, 7]`

and`[5, 8, 9]`

become`[1, 2, 5, 8, 9]`

, You can put the whole array in order .

Merge array `[1, 2, 7]`

and `[5, 8, 9]`

The operation steps are as follows .

- Put the array
`[1, 2, 7]`

use`L`

Express ,`[5, 8, 9]`

use`R`

Express . - When merging , Open up and allocate a new array
`T`

Save results , The array size should be the sum of the lengths of the two sub arrays - Then subscript
`i`

、`j`

、`k`

Point to the starting point of each array . - Next , Compare subscripts i and j Element pointed to
`L[i]`

and`R[j]`

, Put in subscripts in order of size`k`

Where to point ,`1`

Less than`5`

. - Move
`i`

and`k`

, Continue to compare`L[i]`

and`R[j]`

,`2`

Than`5`

Small . `i`

and`k`

Keep moving forward ,`5`

Than`7`

Small .- Move
`j`

and`k`

, Continue to compare`L[i]`

and R[j],`7`

Than`8`

Small . - Now , The array on the left has been processed , Just put the remaining elements of the right array into the result array .

The reason why the merger can succeed , The prerequisite must be that both subarrays are ordered separately .

### Merge sort algorithm analysis

#### Merge sort space complexity

Because of the merger n Elements need to be allocated a size of `n`

Extra array of , After the merger , The space of this array will be freed , So the spatial complexity of the algorithm is `O(n)`

. Merge sort is also a stable sort algorithm .

#### Merge sort time complexity

Merging algorithm is a recursive process .

give an example ： The number of elements in the array is `n`

, The time complexity is `T(n)`

Function of .

solution ： Scale this to `n`

The problem is divided into two scales, namely `n/2`

The sub problem of , The time complexity of each subproblem is `T(n/2)`

, So the complexity of the two subproblems is `2×T(n/2)`

. When both subproblems are solved , That is, the two subarrays are in order , They need to be combined , Altogether n Elements , You have to do the most every time `n-1`

The second comparison , So the complexity of merging is `O(n)`

. From this, we get the recursive complexity formula ：`T(n) = 2×T(n/2) + O(n)`

.

For formula solving , Constantly call a scale `n`

The problem is broken down into `n/2`

The problem of , Until the scale is `1`

. If `n`

be equal to `2`

, Just once in a while ; If `n`

be equal to `4`

, Need points `2`

Time . The number of times here is classified according to the change of scale .

And so on , For scale `n`

The problem of , All in all `log(n)`

Slice the size of the layer . On every floor , We all have to merge , The elements involved are actually all the elements in the array , therefore , The merge complexity of each layer is `O(n)`

, So the overall complexity is `O(nlogn)`

.

## Quick sort （Quick Sort）

### The basic idea of quick sort

Quick sort also adopts the idea of divide and conquer .

### Fast sort implementation

Filter the original array into two smaller and larger sub arrays , Then recursively sort the two sub arrays .

** give an example **： Put all the students in the class in a row in order of height .

** solution **： The teacher first randomly selected the students A, Let all other students and students A Shorter than tall , Than A The short ones are all standing A Left side , Than A The tall ones are all standing in A To the right of . Next , The teacher chose the students from the left to the right B With my classmates C, Then continue to filter and arrange .

In the process of dividing into smaller and larger sub arrays , How to select a reference value （ That is, students A、B、C etc. ） Especially the key .

### Quick sort to achieve example analysis

An array `[2,1,7,9,5,8]`

Sort .

### Quick sorting problem solving ideas

- According to the idea of quick sort , First, filter the array into two smaller and larger sub arrays .
- Randomly select a number from the array as the reference value , such as
`7`

, So the original array is divided into two sub arrays . Be careful ： Quick sort is to perform various exchange operations directly in the original array , So when the subarray is split , The arrangement in the original array has also been changed . - Next , Select... From the smaller subarray
`2`

As a reference value , Select... In a larger subarray`8`

As a reference value , Continue to split subarrays . - Continue to make the number of elements greater than
`1`

Subarray of , When the number of elements in all subarrays is`1`

When , The original array is also ordered .

### Quick sort code example

```
// Quick sort
const quickSort = function (arr, lo, hi) {
if (lo === undefined) {
lo = 0
}
if (hi === undefined) {
hi = arr.length - 1
}
// Determine if there is only one element left , yes , Then return directly
if (lo >= hi) return
// utilize partition Function to find a random reference point
const p = partition(arr, lo, hi)
// Recursively sorts the number of left and right halves of the base point
quickSort(arr, lo, p - 1)
quickSort(arr, p + 1, hi)
}
// Swap array positions
const swap = function (arr, i, j) {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}
// Get the location index randomly
const randomPos = function (lo, hi) {
return lo + Math.floor(Math.random() * (hi - lo))
}
const partition = function (arr, lo, hi) {
const pos = randomPos(lo, hi)
console.log('pos: ', pos)
swap(arr, pos, hi)
let i = lo
let j = lo
// Compare each number with the reference value from left to right , If it is smaller than the reference value , Then put it in the pointer i Point to
// After the cycle ,i The number before the pointer is smaller than the reference value
while (j < hi) {
if (arr[j] <= arr[hi]) {
swap(arr, i++, j)
}
j++
}
// The reference value at the end is placed in the pointer i The location of , i The number after the pointer is larger than the reference value
swap(arr, i, j)
// Return pointer i, Position as reference point
return i
}
const arr = [2, 1, 7, 9, 5, 8]
quickSort(arr)
console.log(arr)
```

### Quick sort algorithm analysis

#### Time complexity of quick sorting

1、 Best case ： The selected benchmark values are all the middle numbers of the current subarray .

Such segmentation , It can guarantee that for a scale of `n`

The problem of , Can be uniformly decomposed into two scales of `n/2`

Sub problem （ Merge sort also uses the same division method ）, Time complexity is ： `T(n)=2xT(n/2) + O(n)`

.

Size it to `n`

The problem of `n/2`

Two sub questions of , And the benchmark `n-1`

Compare it to , The complexity is `O(n)`

. Obviously , In the best case , The complexity of quick sorting is also `O(nlogn)`

.

2、 The worst ： The benchmark value selects the maximum and minimum value in the subarray .

Each time, the subarray is divided into two smaller subarrays , The length of one of them is `1`

, The other one is only shorter than the atomic array `1`

.

give an example ： For arrays , The benchmark values for each selection are `9、8、7、5、2`

.

solution ： The partitioning process is similar to the bubble sorting process .

The algorithm complexity is `O(n^2)`

.

Tips ： The worst case can be avoided by randomly selecting the reference value .

#### Quick sort space complexity

Unlike merge sort , Quick sort in the process of each recursion , Just open up `O(1)`

To complete the exchange operation and realize the direct modification of the array , Because the number of recursion is `logn`

, Therefore, its overall space complexity depends entirely on the number of times to stack , therefore , Its spatial complexity is `O(logn)`

.