30秒学会 JavaScript 片段 – Selection sort

Definition

Selection sort is an in-place comparison sorting algorithm. It divides the input array into a sorted and an unsorted subarray. It then repeatedly finds the minimum element in the unsorted subarray and swaps it with the leftmost element in the unsorted subarray, moving the subarray boundaries one element to the right.

Implementation

• Use the spread operator (...) to clone the original array, arr.
• Use a for loop to iterate over elements in the array.
• Use Array.prototype.slice() and Array.prototype.reduce() to find the index of the minimum element in the subarray to the right of the current index. Perform a swap, if necessary.

代码实现

const selectionSort = arr => {
  const a = [...arr];
  for (let i = 0; i < a.length; i++) {
    const min = a
      .slice(i + 1)
      .reduce((acc, val, j) => (val < a[acc] ? j + i + 1 : acc), i);
    if (min !== i) [a[i], a[min]] = [a[min], a[i]];
  }
  return a;
};

selectionSort([5, 1, 4, 2, 3]); // [1, 2, 3, 4, 5]

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/selection-sort