Examples to explain several commonly used sorting algorithms in JavaScript

JavaScript is a popular programming language used to create interactivity on web pages. Sorting is one of the important algorithms in computer science, and sorting in JavaScript is also a skill that must be mastered. In this article, we will introduce several commonly used sorting algorithms in JavaScript and how to implement them.

1. Bubble sort

Bubble sort is a simple and intuitive sorting algorithm. Its basic idea is to compare two adjacent elements each time, and if their order is incorrect, swap their positions. After each round of sorting, the largest element is moved to the end of the array. This process is repeated until the entire array is sorted.

The following is the JavaScript implementation of bubble sorting:

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

In the above code, we use nested loops to compare adjacent elements in sequence. If the current element is greater than the next element, swap them s position. In each iteration of the loop, the largest element is moved to the end of the array. The time complexity of this algorithm is O(n^2).

2. Selection sort

Selection sort is another simple sorting algorithm. Its basic idea is to select the smallest element in the array each time and put it into The last digit of the sorted sequence. The time complexity of selection sort is also O(n^2).

The following is the JavaScript implementation of selection sort:

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

In the above code, we use two nested loops to find the minimum value and swap it to the end of the sorted array.

3. Insertion sort

Insertion sort is a simple but efficient sorting algorithm. Its basic idea is to insert an element to be sorted into an already sorted element. in sequence. For an unordered sequence, we always start from the first element, take out one element from left to right, and then insert it into the appropriate position of the ordered sequence. Until all elements are fetched, the sorting process is completed.

The following is the JavaScript implementation of insertion sort:

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

In the above code, we use a while loop to move the sorted elements to the right to make room for new elements to be inserted. The time complexity of this algorithm is O(n^2).

4. Quick sort

Quick sort is a commonly used and efficient sorting algorithm. The basic idea is to choose a base number and compare all numbers in the sequence with this base number. Place the numbers smaller than the base number to the left of the base number, and the numbers larger than the base number to the right of the base number, and then recursively process the left and right subsequences.

The following is the JavaScript implementation of quick sort:

function quickSort(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));
}

In the above code, we first select a benchmark number, then traverse the entire sequence, and put the numbers smaller than the benchmark number into an array. Put numbers larger than the base number into another array. Finally, we recursively process the left and right arrays and merge them with the base number. The time complexity of this algorithm is O(nlogn).

Summary

This article introduces several common sorting algorithms and their implementation in JavaScript. Whether it is bubble sort, selection sort or insertion sort, they are all very basic and easy-to-understand sorting algorithms, suitable for beginners to learn and understand. If you have a more in-depth and comprehensive study of sorting algorithms, you can also try to use some advanced sorting algorithms, such as merge sort, heap sort, etc.

The above is the detailed content of Examples to explain several commonly used sorting algorithms in JavaScript. For more information, please follow other related articles on the PHP Chinese website!