# Sorting of "beauty of algorithm series" (JS version)

wuwhs 2021-11-25 17:41:03

## 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)`.