Sorting algorithm

Stability: The order of the two equal elements after sorting is the same as before sorting, i.e. the relative order of the equal elements before and after sorting remains the same

1. Bubble sort (got it!)

Time complexity: O (n^2)

Compare adjacent elements. If the first one is bigger than the second, swap them both.

Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end. When we do that, the last element is going to be the largest number.

Repeat this step for all elements except the last one.

Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs to compare.

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) { // Compare adjacent elements in pairs
        let temp = arr[j + 1];  // Element swap
        arr[j + 1] = arr[j]; arr[j] = temp; }}}return arr;
}

let arr = [3.2.5.7.6.1.8.4];
console.log(bubbleSort(arr));
Copy the code

Improved version

Set the flag bit to true if an exchange occurs. Set to false if there is no swap.

In this case, if flag is still false after a round of comparison, that is, there is no exchange in this round, it indicates that the data sequence has been arranged and there is no need to continue.

function bubbleSortBetter(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let flag = false;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
        flag = true; }}if(! flag)break;
  }
  return arr;
}

let arr = [3.2.5.7.6.1.8.4];
console.log(bubbleSortBetter(arr));
Copy the code

2. Insert sort (familiar!)

Time complexity: O (n^2)

Principle: By building an ordered sequence, unordered data is scanned from back to front in the sorted sequence to find the corresponding position and insert.

Treat the first element of the first to be sorted sequence as an ordered sequence and the second element to the last element as an unsorted sequence.

Scan the unordered sequence from beginning to end, inserting each scanned element into the appropriate place in the ordered sequence. (If the element to be inserted is equal to an element in the ordered sequence, the element to be inserted is inserted after the equal element.)

function insertSort(arr) {
  let len = arr.length;
  for (let i = 1; i < len; i++) {
    let cur = arr[i];
    let preIndex = i - 1;
    while (preIndex >= 0 && arr[preIndex] > cur) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = cur;
  }
  return arr;
}

let arr = [3.2.5.7.6.1.8.4];
console.log(insertSort(arr));
Copy the code

3. Selection sort – unstable (understand!)

Time complexity: O (n^2)

First find the smallest (large) element in the unsorted sequence and store it at the beginning of the sorted sequence

Find the smallest (largest) element from the remaining unsorted elements and place it at the end of the sorted sequence.

Repeat the second step until all elements are sorted.

function selectSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) { // Find the smallest number
        minIndex = j; // Find the smallest index save}}let temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

let arr = [3.2.5.7.6.1.8.4];
console.log(selectSort(arr));
Copy the code

4. Hill Sort – unstable (understand!)

Reduced incremental sort – Improved insert sort

Time complexity: O (n^1.3-2), depending on the selected increment formula

Hill sort is an improved method based on the following two properties of insertion sort:

• Insertion sort has high efficiency when it operates on almost ordered data, that is, it can achieve the efficiency of linear sort.
• But insert sort is generally inefficient because it can only move data one bit at a time;

The basic idea of Hill sorting is that the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion sorting respectively. When the records in the whole sequence are “basically ordered”, the whole records are directly inserted in sequence.

Divide the array elements into groups by increment, then group them for insertion sort, then gradually reduce the increment, and continue to insert sort by group until the increment is 1. Direct insert sort on the entire array.

Delta formula: Gap = gap / 2 or gap = gap / 3 + 1

function shellSort(arr) {
  let len = arr.length;
  for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < len; i++) {
      let cur = arr[i];
      let j = i - gap;
      while (j >= 0&& arr[j] > cur) { arr[j + gap] = arr[j]; j -= gap; } arr[j + gap] = cur; }}return arr;
}

let arr = [3.2.5.7.6.1.8.4];
console.log(shellSort(arr));
Copy the code

5. Merge sort (emphasis!)

Time complexity: O (n log n)

Space complexity: O (n)

Merge sort is an efficient sorting algorithm based on Merge operations. This algorithm is a very typical application of Divide and Conquer.

As a typical divide-and-conquer algorithm application, merge sort is implemented by two methods:

• Top-down recursion (all recursive methods can be iteratively rewritten, hence the second method);
• Bottom-up iteration;

As with select sort, merge sort performs independently of the input data, but performs much better than select sort because it is always O(nlogn) time. The trade-off is extra memory.

1. Apply for a space equal to the sum of two sorted sequences, which is used to store the combined sequence;

2. Set two Pointers, the initial positions of which are respectively the start positions of the two sorted sequences;

3. Compare the elements pointed to by the two Pointers, select the smaller element into the merge space, and move the pointer to the next position;

4. Repeat Step 3 until a pointer reaches the end of the sequence.

5. Copy all remaining elements of the other sequence directly to the end of the merged sequence.

function mergeSort(arr) {
  let len = arr.length;
  if (len < 2) {
    return arr;
  }
  let mid = Math.floor(len / 2),
    left = arr.slice(0, mid),
    right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(l, r) {
  let res = [];
  let i = 0,
    j = 0;
  while (i < l.length && j < r.length) {
    if (l[i] <= r[j]) {
      res.push(l[i++]);
    } else{ res.push(r[j++]); }}while (i < l.length) res.push(l[i++]);
  while (j < r.length) res.push(r[j++]);
  return res;
}

let arr = [3.2.5.7.6.1.8.4];
console.log(mergeSort(arr));
Copy the code

6. Quicksort – unstable (emphasis!)

Time complexity: O (n log n)

Space complexity: O (log N)

Quicksort is usually faster than other sorting algorithms that use n log2n. Quicksort is sort of recursive divide-and-conquer based on bubble sort.

Quicksort uses divide-and-conquer to divide a list into two sub-lists. The specific algorithm is described as follows:

• Pick an element from the sequence, called pivot;
• Reorder the array so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition exits, the benchmark is in the middle of the array. This is called a partition operation;
• Recursively sorts subsequences of elements less than a reference and subsequences of elements greater than a reference.

(Popular explanation) Excavation number + divide-and-conquer method:

1. I = L; j = R; The datum is dug out to form the first pit a[I].

2. J — from back to front to find the number smaller than it, after finding this number to fill the previous pit a[I]. At the same time i++

3. I++ from front to back to find the number larger than it, after finding the number also dug into the previous pit a[j]. At the same time j –

4. Repeat steps 2,3 until I ==j and fill a[I] with the reference number.

Fast platoon optimization:

Note: In the case of ordered or basically ordered arrays, the selection of fixed datum affects the efficiency of fast sorting. In order to solve the problem of basic array order, we can use random datum to solve this problem. Sorted divide-and-conquer binary trees will be very unbalanced and degenerate into nearly linked lists.

if (l < r) {
    let ranIndex = l + Math.floor(Math.random() * (r - l))
    let temp = arr[l]
    arr[l] = arr[ranIndex]
    arr[ranIndex] = temp
}
Copy the code

Complete code:

function quickSort(arr, l, r) {
  // do not write special cases
  //if(arr === null || arr.length === 0) return
  if (l < r) {
    let mid = partition(arr, l, r);
    quickSort(arr, l, mid - 1);
    quickSort(arr, mid + 1, r);
  }
  return arr;
}

function partition(arr, l, r) {
  // Select datum randomly to solve the problem of basic order array
  if (l < r) {
      let ranIndex = l + Math.floor(Math.random() * (r - l))
      let temp = arr[l]
      arr[l] = arr[ranIndex]
      arr[ranIndex] = temp
  }
  
  let pivot = arr[l];
  while (l < r) {
    while (l < r && arr[r] > pivot) r--;
    if (l < r) {
      arr[l] = arr[r];
      l++;
    }
    while (l < r && arr[l] <= pivot) l++;
    if (l < r) {
      arr[r] = arr[l];
      r--;
    }
  }
  arr[l] = pivot;
  return l;
}

let arr = [3.2.5.7.6.1.8.4];
console.log(quickSort(arr, 0, arr.length - 1));
Copy the code

7. Heap Sort – unstable (emphasis!)

Time complexity: O (n log n)

Heapsort refers to a sort algorithm designed by using heap data structure. Heap is a nearly complete binary tree structure, and also satisfies the property of heap: that is, the key value or index of the child node is always smaller (or larger) than its parent node. Heap sort is actually a selection sort, it’s a tree selection sort. Heap sort is an unstable sort and is not suitable for sorting with fewer records. Heap sort can be said to be a selection sort that uses the concept of heap to sort. There are two methods:

1. Large top heap: Each node has a value greater than or equal to the value of its children, used in ascending heap sorting;

2. Small top heap: The value of each node is less than or equal to the value of its children, used in descending order in the heap sort algorithm;

Heap storage: the heap is usually represented by an array. The subscript of the node is I (I > 1), and the subscript of the parent node is (i-1) / 2. The left and right children of the parent node are (2i + 1) and (2i + 2) respectively. The last parent is len over 2-1

Basic idea:

Taking advantage of the fact that the top of the big top heap (small top heap) records the maximum key (minimum key) makes it easy to select the maximum record (minimum record) from the disorder each time.

(1) The sequence to be sorted is constructed into a maximum heap, and the maximum value of the sequence is the root node. (2) The root node is exchanged with the last element of the sequence to be sorted; (3) the maximum heap is maintained from the root node to the previous node of the element, and so on, and finally an increasing sequence is obtained

let len;
function heapSort(arr) {
  len = arr.length;
  if (len < 1) return arr;
  // Build a maximum heap
  buildMaxHeap(arr);
  // The loop swaps the first (maximum) bit of the heap with the last, and then readjust the maximum heap
  // Write arr.length here, since n controls the number of elements in the heap and changes
  for (let i = arr.length - 1; i >= 0; i--) {
    swap(arr, 0, i);
    len--;
    heapify(arr, 0);
  }
  return arr;
}

function buildMaxHeap(arr) {
  // Initialize, I adjusts from the last parent, which is len/2-1
  for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
  //for (let i = Math.floor(len / 2 - 1); i >= 0; i--) {heapify(arr, i); }}function heapify(arr, i) {
  let l = 2 * i + 1,
    r = 2 * i + 2,
    largest = i;
  // If there is a left subtree and the left subtree is larger than the parent, then the maximum pointer is to the left subtree
  if (l < len && arr[l] > arr[largest]) {
    largest = l;
  }
  // If there is a right subtree and the right subtree is larger than the parent, then the maximum pointer is to the right subtree
  if (r < len && arr[r] > arr[largest]) {
    largest = r;
  }
  // If the parent is not the maximum, swap the parent with the maximum and recursively adjust the swap position with the parent.
  if (largest !== i) {
    swap(arr, i, largest);
    heapify(arr, largest);
  }
}

function swap(arr, i, j) {
  let temp = arr[j];
  arr[j] = arr[i];
  arr[i] = temp;
}

let arr = [3.2.5.7.6.1.8.4];
console.log(heapSort(arr));
Copy the code

Reference article:

1. Sort giFs

2. Hill sort

3. Merge sort

quicksort

5. Heap sort