Summary of JS sorting algorithm

This time I will bring you a summary of the JS sorting algorithm. What are the precautions when using the JS sorting algorithm? The following is a practical case, let’s take a look.

You can find a lot of questions about sorting algorithms on the Internet, but the pure JS version is relatively scattered. I specially sorted it out during the previous interview, with a comparison of sorting efficiency

1.Bubble sort

var bubbleSort = function(arr) {
  for (var i = 0, len = arr.length; i < len - 1; i++) {
    for (var j = i + 1; j < len; j++) {
      if (arr[i] > arr[j]) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
};

2.Selection sort

var selectSort = function(arr) {
  var min;
  for (var i = 0; i < arr.length - 1; i++) {
    min = i;
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[min] > arr[j]) {
        min = j;
      }
    }
    if (i != min) {
      swap(arr, i, min);
    }
    console.log(i + 1, ": " + arr);
  }
  return arr;
};
function swap(arr, index1, index2) {
  var temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
};

3.Insertion sort

var insertSort = function(arr) {
  var len = arr.length,
    key;
  for (var i = 1; i < len; i++) {
    var j = i;
    key = arr[j];
    while (--j > -1) {
      if (arr[j] > key) {
        arr[j + 1] = arr[j];
      } else {
        break;
      }
    }
    arr[j + 1] = key;
  }
  return arr;
};

4.Hill sort

function shellSort(arr) {
  if (arr.length < 2) {
    return arr;
  };
  var n = arr.length;
  for (gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap /= 2)) {
    for (i = gap; i < n; ++i) {
      for (j = i - gap; j >= 0 && arr[j + gap] < arr[j]; j -= gap) {
        temp = arr[j];
        arr[j] = arr[j + gap];
        arr[j + gap] = temp;
      }
    }
  }
  return arr;
};

5. Merge sort

function merge(left, right) {
  var result = [];
  while (left.length > 0 && right.length > 0) {
    if (left[0] < right[0]) {
      // shift()方法用于把数组的第一个元素从其中删除，并返回第一个元素的值
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  return result.concat(left).concat(right);
}
function mergeSort(arr) {
  if (arr.length == 1) {
    return arr;
  }
  var middle = Math.floor(arr.length / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

6. Quick sort

var quickSort = function(arr) {　　
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);　
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];　　
  for (var i = 0; i < arr.length; i++) {　　　
    if (arr[i] < pivot) {　　　　　　
      left.push(arr[i]);　　　　
    } else {　　　　　　
      right.push(arr[i]);　　　　
    }　
  }　　
  return quickSort(left).concat([pivot], quickSort(right));
};

Comparison of algorithm efficiency

-------------- ------------------------------------------------
| Sorting algorithm | Average case | Best case | Worst case | Stability |
---------------------------- ----------------------------------
| Bubble sort | O(n²) | O( n) | O(n²) | Stable |
---------------------------------------- --------------------------
| Selection sort | O(n²) | O(n²) | O(n²) | Unstable |
------------------------------------------------- ------------------
| Insertion sort | O(n²) | O(n) | O(n²) | Stable |
------ -------------------------------------------------- -------
| Hill sort| O(nlogn)~O(n²) | O(n^1.5) | O(n²) | Unstable|
------ -------------------------------------------------- ------
| Merge sort | O(nlogn) | O(nlogn) | O(nlogn) | Stable |
---------------- --------------------------------------------------
| Quick sort | O(nlogn) | O(nlogn) | O(n²) | Unstable|
-------------------------- ----------------------------------------

I believe you have read the case in this article After mastering the method, please pay attention to other related articles on the php Chinese website for more exciting content!

Recommended reading:

How to choose the jQuery version

##Detailed explanation of the three types of $() in jQuery

H5 title writing problem

The above is the detailed content of Summary of JS sorting algorithm. For more information, please follow other related articles on the PHP Chinese website!