Implement visualizations through algorithms: visualgo.net/zh/sorting to deepen understanding.

• Basic sorting algorithm:

• Bubble sort
• Insertion sort
• Selection sort

• Merge sort
• Quick sort

## Bubble sort

### Ideas:

Bubble sort is the process of repeatedly comparing two adjacent items, starting with the first element. If the first item is larger than the second, the two items are swapped. Vice versa. Each round of operation places the largest element of that round at the end of the array. If the length of the array is n, then by the time we do n rounds, the entire array will be in order.

### implementation

``````function bubbleSort(arr) {
// Cache array length
let len = arr.length
// The outer loop takes one value from the beginning to the end of each round and compares it with all the values in the inner loop
for(let i = 0; i < len; i++) {
for(let j = 0; j < len-1; j++) {
// If the current value is greater than the latter value, the position is switched
if(arr[j]> arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr
}
Copy the code``````

### Optimization for the first time

As the outer loop progresses, the elements at the end of the array get sorted — by the time we finish the first loop, the largest elements are at the end of the array; At the end of the second cycle, the second largest element is ranked second from the bottom of the array; By the end of the third loop, the third largest element is placed at…… By the end of the NTH loop, the last n elements of the array are already sorted

``````function betterBubbleSort(arr) {
const len = arr.length
for(let i=0; i<len; i++) {// Notice the difference in this line, where we limit the scope of the inner loop
for(let j=0; j<len-1-i; j++) {if(arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
return arr
}
Copy the code``````

### Optimize the second time

``````function betterBubbleSort(arr) {
const len = arr.length

for(let i=0; i<len; i++) {// The difference here is that we add a flag bit
let flag = false
for(let j=0; j<len-1-i; j++) {if(arr[j] > arr[j+1]) {
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
// When a swap occurs, the flag bit is modified
flag = true}}// If no swap occurs, the array is in order
if(flag == false)  return arr;
}
return arr
}
Copy the code``````

## Selection sort

### Ideas:

The keyword of selection sort is “minimum” : loop through the array of numbers, find the minimum value in the current range each time, put it in the head of the current range; Then narrow down the sorting range and repeat until the array is completely sorted

### implementation

``````function selectSort(arr)  {
// Cache array length
const len = arr.length
// define minIndex, the index of the minimum value of the current interval
let minIndex
// I is the start of the current sort interval
for(let i = 0; i < len - 1; i++) {
// Initialize minIndex as the first element of the current range
minIndex = i
// I and j define the upper and lower bounds of the current interval respectively. I is the left boundary and j is the right boundary
for(let j = i; j < len; j++) {
// If the item at j is smaller than the current minimum, update the minimum index to j
if(arr[j] < arr[minIndex]) {
minIndex = j
}
}
// If the corresponding minIndex element is not the current header element, the two are swapped
if(minIndex ! == i) { [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]] } }return arr
}
Copy the code``````

## Insertion sort

### Train of thought

The core idea of insertion sort is to “find the correct position of the element in the sequence that precedes it.” In particular, all operations of insert sort are based on the premise that the sequence before the current element is ordered. Based on this premise, work backwards to find the correct position of the current element in the previous sequence.

### implementation

``````function insertSort(arr) {
// Cache array length
const len = arr.length
// Temp is used to store the current element to be inserted
let temp
// I is used to identify the index of the element being inserted each time
for(let i = 1; i < len; i++) {// j is used to help Temp find its rightful position
let j = i
temp = arr[i]
// Determine whether the element before j is larger than temp
while(j > 0 && arr[j-1] > temp) {
// If so, move the element before j back one bit to make room for temp
arr[j] = arr[j-1]
j--
}
// The final j is the correct index of temp
arr[j] = temp
}
return arr
}
Copy the code``````

## Merge sort

### Train of thought

Divide and rule — divide and rule

• Split the subproblem: Split the sorted array in half, then split each subarray in half, and repeat until each subarray has only one element.
• Solve each subproblem: Start with the smallest subarray and merge in pairs, making sure the array is sorted each time. (By “subproblem” I mean sorting each subarray.)
• Merge the solutions of the subproblems to get the solution of the big problem: when the array is merged to its original size, the result is a fully sorted array
``````function mergeSort(arr) {
const len = arr.length
// Handle boundary cases
if(len <= 1) {
return arr
}
// Calculate the split point
const mid = Math.floor(len / 2)
// Divide the left subarray recursively and merge it into an ordered array
const leftArr = mergeSort(arr.slice(0, mid))
// Divide the right subarray recursively and merge it into an ordered array
const rightArr = mergeSort(arr.slice(mid,len))
// Merge left and right ordered arrays
arr = mergeArr(leftArr, rightArr)
// Return the merged result
return arr
}

function mergeArr(arr1, arr2) {
// Initialize two Pointers to arr1 and arr2
let i = 0, j = 0
// Initialize the result array
const res = []
// Cache the length of arr1
const len1 = arr1.length
// Cache the length of arR2
const len2 = arr2.length
// Merge two subarrays
while(i < len1 && j < len2) {
if(arr1[i] < arr2[j]) {
res.push(arr1[i])
i++
} else {
res.push(arr2[j])
j++
}
}
// If one of the subarrays is merged completely first, the rest of the other subarray is directly merged
if(i<len1) {
return res.concat(arr1.slice(i))
} else {
return res.concat(arr2.slice(j))
}
}
Copy the code``````

Time complexity: O(nlogn)

## Quick sort

### Train of thought

Quicksort is basically the same as merge sort, except that it does not split up the real array and merge it into a new array. Instead, it sorts directly inside the original array.

Quicksort filters the original array into smaller and larger subarrays, and then sorts the two subarrays recursively.

### Implement a

``````function quickSort(arr) {
const len = arr.length
if(len < 1) return arr
// Select the reference point
const lineIndex = Math.floor(len / 2)
const lineValue = arr[lineIndex]
const left = []
const right = []

for(let i = 0; i < len; i++) {
if(i ! == lineIndex) {const n = arr[i]
if(n < lineIndex) {
left.push(n)
} else {
right.push(n)
}
}
}
return quickSort(left).concat(
[lineValue],
quickSort(right)
)
}
Copy the code``````

Time complexity: O(nlogn)

Space complexity: O(n)

### Realize the

``````// Quicksort entry
function quickSort(arr, left = 0, right = arr.length - 1) {
// Define recursive bounds. If the array has only one element, there is no sorting necessary
if(arr.length > 1) {
// lineIndex indicates the index bit of the next subarray partition
const lineIndex = partition(arr, left, right)
// If the length of the left subarray is not less than 1, the subarray is recursively fast-sorted
if(left < lineIndex-1) {
// The left subarray is bounded by lineIndex-1
quickSort(arr, left, lineIndex-1)}// If the length of the right subarray is not less than 1, the subarray is recursively fast-sorted
if(lineIndex<right) {
// The right subarray is bounded by lineIndex
quickSort(arr, lineIndex, right)
}
}
return arr
}
// The process of dividing left and right subarrays with reference values as the axis
function partition(arr, left, right) {
// The base value defaults to the middle element
let pivotValue = arr[Math.floor(left + (right-left)/2)]
// Initialize the left and right Pointers
let i = left
let j = right
// When the left and right Pointers do not exceed the bounds, the loop executes the following logic
while(i<=j) {
// If the left pointer points to an element less than the base value, the left pointer moves to the right
while(arr[i] < pivotValue) {
i++
}
// If the right pointer points to an element greater than the reference value, the right pointer moves to the left
while(arr[j] > pivotValue) {
j--
}

// If I <=j, it means that there is a larger element to the left or a smaller element to the right of the base value
if(i<=j) {
swap(arr, i, j)
i++
j--
}

}
// Return the left pointer index as the basis for the next subarray partition
return i
}
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}
Copy the code``````

Time complexity: O(nlogn)

Space complexity: O(1)