Implement sorting algorithm using JS

This time I will bring you the use of JS to implement the sorting algorithm and the use of JS to implement the sorting algorithm. Notes What are the following? Let’s take a look at the actual cases.

Some common js sorting algorithm implementations, non-original, used for recording

Bubble sort

Time complexity: O(n^2) ;
Fastest: when the data is in positive sequence
Slowest: when the data is in reverse sequence

function bubbleSort(arr) {  var len = arr.length;  for (var i = 0; i < len; i++) {    for (var j = 0; j < len - 1 - i; i++) {         // 相邻元素两两对比，元素交换
        if (arr[j] > arr[j + 1]) {            var temp = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = temp;
        }
    }
  }  return arr;
}

Selection sort

Time complexity: O(n ^2)
The most stable sorting algorithm

function selectionSort(arr) {  var len = arr.length;  var minIndex, temp;   // 寻找最小的数，将索引保存
  for (var i = 0; i < len - 1; i++) {
    minIndex = i;    for (var j = i + 1; j < len; j++) {        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }  return arr;
}

Insertion sort

Time complexity: O(n^2);
Poker sort

function insertionSort(arr) {  var len = arr.length;  var preIndex, current;  for (var i = 1; i < len; i++) {
    preIndex = i - 1;
    current = arr[i];    while (preIndex >= 0 && arr[preIndex] > current) {
        arr[preIndex + 1] = arr[preIndex];
        preIndex--;
    }
    arr[preIndex + 1] = current;
  }  return arr;
}

Hill Sorting

Time complexity: O(n log n);

function shellSort(arr) {  var len = arr.length, temp, gap = 1;  //动态定义间隔序列
  while (gap < len / 3) {
    gap = gap * 3 + 1;
  }  for (gap; gap > 0; gap = Math.floor(gap / 3)) {    for (var i = gap; i < len; i++) {
        temp = arr[i];        for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
            arr[j + gap] = arr[j];
        }
        arr[j + gap] = temp;
    }
  }  return arr;
}

Merge sort

Time complexity: O(n log n);

function mergeSort(arr) {  var len = arr.length;  if (len < 2) {    return arr;
  }  var middle = Math.floor(len / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle);  return merge(mergeSort(left), mergeSort(right));  function merge(left, right) {    var result = [];    while (left.length && right.length) {        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }    while (left.length)
        result.push(left.shift());    while (right.length)
        result.push(right.shift());    return result;
  }
}

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the php Chinese website!

Recommended reading:

Strategy Pattern of Javascript

Proxy Pattern of Javascript

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