Organize commonly used JS sorting algorithms

This time I will bring you some commonly used JS sorting algorithms. What are the precautions for using JS sorting algorithms? Here are practical cases, let’s take a look.

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²) | No Stable|
------------------------------------------------ ------------------
| 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 will read the case in this article You have mastered the method. For more exciting information, please pay attention to other related articles on the php Chinese website!

Recommended reading:

How to use Sortable in Vue

How to use js css to achieve typing effect

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