## Notes on common sorting algorithms in JavaScript

::::::: 2020-11-06 01:22:50
notes common sorting algorithms javascript

Sorting algorithm is mainly for arrays , therefore , Before you start to learn , We first create a new data structure to facilitate our study .

```function ArrayData () {
let ret = []
this.times = 0 // Count the execution times
this.push = (item) => {
ret.push(item)
}
this.toString = () => {
return ret.join()
}
}
const arr = [34, 11, 45, 22, 31, 99, 68, 54]```

## Bubble sort

Compare the size of two adjacent numbers , If the number in front is greater than that in the back , Then exchange the positions of these two numbers . To sort n A digital , Need experience n-1 Ergodic times .

According to the literal requirement , The code we wrote is like this

```function ArrayData () {
// ......
this.bubbleSort = function () {
let length = ret.length;
for (let i = 0; i < length; i++) {
for (let j = 0; j < length - 1; j++) {
this.times++
if (ret[j] > ret[j + 1]) {
[ret[j], ret[j + 1]] = [ret[j + 1], ret[j]]
}
}
}
}
}
let tmp = new ArrayData()
arr.forEach((item) => {
tmp.push(item)
})
tmp.bubbleSort()
console.log(tmp.times) // 56```

Obviously, this simple and crude sorting method has a lot of room for improvement , such as , We can detect every sort , If the sequence has been arranged successfully , There's no need to execute the following loop .

```function ArrayData () {
// ......
this.bubbleSort = function () {
let length = ret.length;
for (let i = 0; i < length; i++) {
let change = false
for (let j = 0; j < length - 1; j++) {
this.times++Ï
if (ret[j] > ret[j + 1]) {
[ret[j], ret[j + 1]] = [ret[j + 1], ret[j]]
change = true
}
}
if (!change) {
break
}
}
}
}
let tmp = new ArrayData()
arr.forEach((item) => {
tmp.push(item)
})
tmp.bubbleSort()
console.log(tmp.times) // 21```

In fact, there is still room for optimization . for instance , Let's say it's a total of 8 Number , The first cycle , It's going to bubble the largest number 8 position , The second cycle , It puts the second largest number in the list 7 position , therefore , There's no need to think about the last one in this cycle . Empathy , The next cycle doesn't need to consider the last two . The improved code is as follows :

```function ArrayData () {
// ......
this.bubbleSort = function () {
let length = ret.length;
for (let i = 0; i < length; i++) {
let change = false
for (let j = 0; j < length - 1 - i; j++) {
this.times++
if (ret[j] > ret[j + 1]) {
[ret[j], ret[j + 1]] = [ret[j + 1], ret[j]]
change = true
}
}
if (!change) {
break
}
}
}
}
let tmp = new ArrayData()
arr.forEach((item) => {
tmp.push(item)
})
tmp.bubbleSort()
console.log(tmp.times) // 18```

## Selection sort

Traversal array , Find the smallest number in the first place , The second cycle finds the second smallest number and places it in the second place , And so on .

```function ArrayData () {
// ......
this.selectionSort = function () {
let length = ret.length
for (let i = 0; i < length - 1; i++) {
let minIndex = i
for (let j = i; j < length; j++) {
if (ret[j] < ret[minIndex]) {
minIndex = j
}
}
if (i !== minIndex) {
[ret[i], ret[minIndex]] = [ret[minIndex], ret[i]]
}
}
}
}
let tmp = new ArrayData()
arr.forEach((item) => {
tmp.push(item)
})
tmp.selectionSort()```

## Insertion sort

Divide the array into two parts , The first part is ordered , Then insert the last part of the number into the array in front of the order . therefore , In the beginning, set the first element as the ordered part , Insert the following numbers separately .

```function ArrayData () {
// ......
this.insertSort = function () {
let length = ret.length
let j
for (let i = 1; i < length; i++) {
let currentNumber = ret[i]
for (j = i - 1; j >= 0 && ret[j] > currentNumber; j--) {
ret[j + 1] = ret[j]
}
ret[j + 1] = currentNumber
}
}
}
let tmp = new ArrayData()
arr.forEach((item) => {
tmp.push(item)
})
tmp.insertSort()```

## Quick sort

Choose a number as the base number , Ergodic sequence , Compare it Put it in front of him , Put the smaller one behind him , And then recurs the above operation to the sequence before and after the reference number , Until the length of the sequence is 1.

```function ArrayData () {
// ......
this.quickSort = function () {
quick(ret, 0, ret.length - 1);
function quick(array, left, right) {
let index
if (array.length > 1) {
index = partition(array, left, right)
if (left < index - 1) {
quick(array, left, index - 1)
}
if (right > index) {
quick(array, index, right)
}
}
return array
}
function partition(array, left, right) {
let pivot = array[Math.floor((right + left) / 2)],
i = left,
j = right;
while (i <= j) {
while (array[i] < pivot) {
i++
}
while (array[j] > pivot) {
j--
}
if (i <= j) {
swap(array, i, j);
i++;
j--;
}
}
return i
}
function swap(array, i, j) {
[array[i], array[j]] = [array[j], array[i]]
}
}
}
let tmp = new ArrayData()
arr.forEach((item) => {
tmp.push(item)
})
tmp.quickSort()```

Quick sort in one sentence . Select the first element as the reference element , utilize filter Divide the array into two arrays larger than the reference element and smaller than the reference element , And the two arrays recursively call the fast sorting function .

```function quickSort(arr) {
return arr.length <= 1 ? arr : quickSort(arr.slice(1).filter((item) => item <= arr[0])).concat(arr[0], quickSort(arr.slice(1).filter((item) => item > arr[0])))
}```

## Shell Sort

Hill sort is the grouping of arrays by a certain increment of the subscript , Insert rows into each group , As the increments decrease , Each array has more and more length , When the increment is reduced to 1 when , The whole document is just a group , The algorithm terminates .

```function ArrayData () {
// ......
this.shellSort = function () {
let length = ret.length
for (let step = Math.floor(length / 2); step > 0; step = Math.floor(step / 2)) {
for (let i = 0; i < step; i++) {
shellInsertSort(i, step)
}
}
function shellInsertSort(index, step) {
let length = ret.length
let j
for (let i = index; i < length; i += step) {
let currentNumber = ret[i]
for (j = i - step; j >= 0 && ret[j] > currentNumber; j -= step) {
ret[j + step] = ret[j]
}
ret[j + step] = currentNumber
}
}
}
}
let tmp = new ArrayData()
arr.forEach((item) => {
tmp.push(item)
})
tmp.shellSort()```

## Merge sort

Merging and sorting adopts the idea of divide and rule , Merges ordered subsequences , You get a perfectly ordered sequence . So we split the sequence into an array of no more than two elements , And then merge it .

```function ArrayData () {
// ......
this.mergeSort = function () {
ret = mergeSortFun(ret)
function mergeSortFun(arr) {
let length = arr.length
if (length <= 1) {
return arr
}
let mid = Math.floor(length / 2),
left = arr.slice(0, mid),
right = arr.slice(mid, length)
return mengeConnect(mergeSortFun(left), mergeSortFun(right))
}
function mengeConnect(left, right) {
let
leftIndex = 0,
rightIndex = 0,
result = []
while (leftIndex < left.length && rightIndex < right.length) {
result.push(left[leftIndex] < right[rightIndex] ? left[leftIndex++] : right[rightIndex++])
}
while (leftIndex < left.length) {
result.push(left[leftIndex++])
}
while (rightIndex < right.length) {
result.push(right[rightIndex++])
}
return result
}
}
}
let tmp = new ArrayData()
arr.forEach((item) => {
tmp.push(item)
})
tmp.mergeSort()```

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .