30秒学会 JavaScript 片段 – Bubble sort

Definition

Bubble sort is a simple sorting algorithm that repeatedly steps through the array, compares adjacent elements and swaps them if they are in the wrong order. The pass through the array is repeated until the array is sorted.

Implementation

• Declare a variable, swapped, that indicates if any values were swapped during the current iteration.
• Use the spread operator (...) to clone the original array, arr.
• Use a for loop to iterate over the elements of the cloned array, terminating before the last element.
• Use a nested for loop to iterate over the segment of the array between 0 and i, swapping any adjacent out of order elements and setting swapped to true.
• If swapped is false after an iteration, no more changes are needed, so the cloned array is returned.

代码实现

const bubbleSort = arr => {
  let swapped = false;
  const a = [...arr];
  for (let i = 1; i < a.length; i++) {
    swapped = false;
    for (let j = 0; j < a.length - i; j++) {
      if (a[j + 1] < a[j]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) return a;
  }
  return a;
};

bubbleSort([2, 1, 4, 3]); // [1, 2, 3, 4]

Complexity

The algorithm has an average time complexity of O(n^2), where n is the size of the input array.

翻译自：https://www.30secondsofcode.org/js/s/bubble-sort