An overview of the

The sorting API provided by js is

arr.sort([compareFunction])
Copy the code

If no sorting function is provided, the elements are converted to a string and sorted in ascending charcode order from front to back, for example

[12, 2]. The sort () / / [12, 2]Copy the code

If the value returned by the function is less than 0, a will be ranked before B. If the value returned by the function is greater than 0, A will be ranked after B, otherwise unchanged.

Other sort

The other is language-independent sorting algorithm, here we will introduce three simple and three time complexity low, namely

  • Bubble sort
  • Selection sort
  • Insertion sort
  • Merge sort
  • Quick sort
  • Heap sort

The first three time complexity o(n^2), the last three o(nlogn), the relevant source code here.

The other ones are not expanded here, for example

  • Bucket sort determines a finite number of buckets, then puts the elements to be sorted into each bucket according to specific attributes, and then determines whether to sort each bucket as required. For example, inThe first K high frequency elementsThe frequency of the occurrence of an element
    • Count the frequency of each element and record the maximum frequency number N
    • Prepare n buckets and place each element into each bucket according to the number of frequencies
    • And then you count k elements from high to low frequencies
  • Topological sorting is breadth-first traversal of vertices of directed acyclic graphs

Bubble sort

Double layer traversal, outer layer to determine traversal range, inner layer comparison.

In ascending order, for example, the outer layer I decreases from the last element to the first, and the inner layer J starts at the 0th and compares with the next, swapping if the preceding one is greater than the following one, until it reaches i-1.

module.exports = (arr) => { for (let i = arr.length - 1; i > 0; i--) { for (let j = 0; j < i; j++) { if (arr[j] > arr[j + 1]) { ; [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] } } } return arr }Copy the code

Selection sort

Selection sort is similar to bubbling, but the inner comparison does not swap immediately when it needs to be adjusted. Instead, the inner comparison assumes that the 0th element is the maximum value (marked as Max) before the inner comparison, and then iterates through the elements to be sorted until the ith element is swapped with the Max element.

It doesn’t have to be switched every time, but the time complexity is the same.

module.exports = (arr) => { for (let i = arr.length - 1; i > 0; i--) { let max = 0 for (let j = 1; j <= i; j++) { if (arr[max] < arr[j]) { max = j } } ; [arr[max], arr[i]] = [arr[i], arr[max]] } return arr }Copy the code

Insertion sort

Insertion sort assumes that the 0th order, I is inserted from the first into the previous (i-1) ordered array, so that the first I becomes an ordered array.

During insertion, although the insertion position can be found through dichotomy, the actual insertion time complexity remains unchanged, and writing is more prone to error, so swap insertion is selected here.

module.exports = (arr) => { for (let i = 1; i < arr.length; I ++) {// compareInsert(arr, I)} return arr} i) { while (arr[i - 1] > arr[i] && i > 0) { ; [arr[i - 1], arr[i]] = [arr[i], arr[i - 1]] i-- } }Copy the code

Merge sort

Merge sort is a typical divide-and-conquer problem, that is, the original problem is divided into sub-problems (divide), and then solve the sub-problems to solve the big problem, and finally solve the original problem (conquer).

Merge sort divides the large array into two smaller arrays, and then recursively splits each of the smaller arrays into a subarray of length 1, and then merges the sorted smaller arrays into the larger array and finally into the sorted original array.

module.exports = (arr) => { function sort(arr1) { if(arr.length<2) return arr let mid=Math.floor((arr.length-1)/2) return merge(sort(arr.slice(0,mid+1)),sort(arr.slice(mid+1,arr.length))) } function merge(arr1, arr2) { let arr=[] while(arr1.length&&arr2.length){ arr.push(arr1[0]>arr2[0]? arr2.shift():arr1.shift()) } arr.push(... (arr1.length? arr1:arr2)) return arr } return sort(arr) }Copy the code

Quick sort

Quicksort is also divide-and-conquer, and unlike merge sort, quicksort is sort in place, and you only need to break up the big problem into smaller problems and solve them, no need for subsequent governance.

To be specific, take one reference value at a time, for example, the 0th one, put the value greater than the reference value after the reference value, and put the value less than the reference value in front, so as to ensure the order of the reference value, and the original array is divided into two parts, recursive quicksort in each interval until all ordered.

Module.exports = (arr) => {function sort(l, r) {// Exports from module. Exports = (arr) => {function sort(l, r) {// Exports from module. If (l >= r) {return} let pivot = arr[l], left = l, right = r while (left < right) { If you have something on the right that is less than pivot, move it over. While (left < right && arr[right] >= pivot) {right--} arr[left] = arr[right (left < right &&arr [left] <= pivot) {left++} arr[right] = arr[left]} left - 1) sort(left + 1, r) } sort(0, arr.length - 1) return arr }Copy the code

Heap sort

Heap data structure

A heap is a data structure that is logically a complete binary tree and physically an array.

This section is preceded by some knowledge of binary trees, which will be discussed in detail in the corresponding section.

Since array subscripts start at 0 and binary trees start at 1, we add an element, such as 0, to the array before processing. Binary trees are stored in the array in breadth-first traversal order.

If all the parents are greater than or equal to their children, the heap is called a large root heap, and the array is arr[I]>=arr[2* I] and arr[I]>=arr[2* I +1], with math.floor ((arr.length-1) / 2 as the last non-leaf node number.

Heap sort

Heap sort is the use of heap data structure to sort, that is, the top of the heap (such as the large root heap) is the most valuable characteristics can be selected in order of the first N (large) elements, or even the whole sort, heap sort is suitable for the case that does not need a complete sort, such as the KTH largest element in the array.

Before sorting, we get a normal array, so we have to build the heap and sort first

Module.exports = (arr) => {// When an array is used as a tree, an element should be added at the front, BuildMaxHeap (arr) // Start at the end of the big root heap and swap with the first element, For (let I = arr. Length-1; i > 1; i--) { ; [arr[I], arr[1]] = [arr[1], arr[I]] Shift () return arr} const heapAjust = (arr, k, I) Arr [0] = arr[k]; end) => {//arr [0] = arr[k]; Then you can overwrite this position with a larger value for (let I = 2 * k; i <= end; If (I < end &&arr [I] < arr[I + 1]) {// If (I < end &&arr [I] < arr[I + 1]) { If (arr[0] >= arr[I]) {break} else {arr[k] = arr[I] Const buildMaxHeap = (arr) => {const buildMaxHeap = (arr) => {const buildMaxHeap = (arr) => { // The last non-terminal node is: For (let I = math.floor ((arr.length-1) /2); for (let I = math.floor ((arr.length-1) /2); i > 0; i--) { heapAjust(arr, i, arr.length - 1) } }Copy the code