Simple implementation of several sorting algorithms in JavaScript_Basic knowledge

Implementation of sorting algorithm

My JS skills are poor, so I use a method similar to JAVA and C to write the JavaScript sorting algorithm.

And I won’t talk about the algorithm principle here, just the code implementation, there may be bugs, everyone is welcome to comment on the blog for guidance.
Insertion sort

The algorithm description of Insertion-Sort is a simple and intuitive sorting algorithm. It works by constructing an ordered sequence. For unsorted data, it scans from back to front in the sorted sequence, finds the corresponding position and inserts it. In the implementation of insertion sort, in-place sorting is usually used (that is, sorting that only uses O(1) extra space). Therefore, during the scanning process from back to front, it is necessary to repeatedly and gradually shift the sorted elements backward. , providing insertion space for the latest element.

The implementation code is as follows:

function insertSort(arr) {
  if (!arr) return;
  var len = arr.length;
  if (len == 0 || len == 1) return;

  for (var i = 1, len = arr.length; i < len; i ++) {
    var stand = arr[i];
    for (var j = i - 1; j >= 0; j --) {
      if (arr[j] > stand) {
        arr[j + 1] = arr[j];
      } else {
        arr[j + 1] = stand;
        break;
      }
    }
  }

  return arr;
}

Time complexity is: O(n^2)

Of course, there is room for optimization of this algorithm, such as changing the positional algorithm of search and replacement to binary search.
Bubble sort

Classic sorting algorithm, I feel heartbroken when it comes to bubble sort. When I was an undergraduate, I wrote a required thesis on the improvement of the bubble sort algorithm. As a result, I couldn't fully implement the bubble sort algorithm after I finished writing the thesis. It was so embarrassing.

  if (!arr) return;
  var len = arr.length;
  if (len == 0 || len == 1) return;

  for (var i = 0; i < len; i ++) {
    for (var j = 0; j < len - i - 1; j ++) {
      if (arr[j] > arr[j + 1]) {
        var tmp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = tmp;
      }
    }
  }

  return arr;
}

The time complexity is: O(n^2)
Quick Sort

A very classic sorting algorithm. The sorting process is mainly divided into three steps:

1. Pick an element from the sequence, called the “pivot”;
2. Reorder the sequence so that all elements smaller than the baseline value are placed in front of the baseline, and all elements larger than the baseline value are placed behind the baseline (the same number can be placed on either side). After this partition exits, the base is in the middle of the sequence. This is called a partition operation;
3. Recursively sort the subarray of elements smaller than the base value and the subarray of elements greater than the base value.

The implementation code is as follows:

function quickSort(arr, bt, ed) {
  if (bt < ed) {
    var pivot = findPartition(arr, bt, ed);
    quickSort(arr, bt, pivot - 1);
    quickSort(arr, pivot + 1, ed);
  }
}

function findPartition(arr, bt, ed) {
  var stand = arr[bt];

  while (bt < ed) {
    while (bt < ed && arr[ed] >= stand) {
      ed --;
    }
    if (bt < ed) {
      arr[bt ++] = arr[ed];
    }
    while (bt < ed && arr[bt] <= stand) {
      bt ++;
    }
    if (bt < ed) {
      arr[ed --] = arr[bt]; 
    }
  }

  arr[bt] = stand;
  return bt;
}

The time complexity is: O(nlogn).
Merge sort

It is also a very classic sorting algorithm. I took the opportunity of learning js to review the classic sorting algorithm. For ideas on merge sort, you can refer to my blog: Merge Sort. I only write js implementation here.

function mergeSort(arr, bt, ed) {
  if (bt < ed) {
    var mid = bt + parseInt((ed - bt) / 2);
    mergeSort(arr, bt, mid);
    mergeSort(arr, mid + 1, ed);
    mergeArray(arr, bt, mid, ed);    
  }
}

function mergeArray(arr, bt, mid, ed) {
  var mArr = [];
  var i = bt, j = mid + 1;
  while (i <= mid && j <= ed) {
    if (arr[i] <= arr[j]) {
      mArr.push(arr[i++]);
    } else {
      mArr.push(arr[j ++]);
    }
  }

  if (i <= mid) {
    mArr = mArr.concat(arr.slice(i, mid + 1));
  }

  if (j <= ed) {
    mArr = mArr.concat(arr.slice(j, ed + 1));
  }

  for (var h = 0; h < mArr.length; h ++) {
    arr[bt + h] = mArr[h];
  }
}

There was another little episode when writing the merge sort: js could not automatically round up, so I later used the parseInt method, which was very cute.