选择排序-oN2

选择排序

选择排序同样也是一个复杂度为O(N^2)的算法。和冒泡排序一样，它包含有嵌套的两个循环，这导致了二次方的复杂度。

选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

外循环（行{2}）迭代数组，并控制迭代轮次（数组的第N个值——下一个最小值）。我们假设本迭代轮次的第一个值为数组最小值（行{3}）。然后，从当前i的值开始至数组结束（行{4}），我们比较是否位置j的值比当前最小值小（行{5}）；如果是，则改变最小值至新最小值（行{6}）。当内循环结束（行{4}），将得出数组第N小的值。最后，如果该最小值和原最小值不同（行{7}），则交换其值。

[5, 4, 3, 2, 1] --->实例

和冒泡排序区别

区别：

实现方式不同：选择排序在每个迭代中找到未排序部分中的最小值，并将其与已排序部分的末尾交换位置，而冒泡排序在每个迭代中将最大值“冒泡”到已排序部分的末尾。
性能不同：选择排序的最坏时间复杂度为O(n^2)，但它通常比冒泡排序快。冒泡排序的最坏时间复杂度也为O(n^2)，但它通常比选择排序慢，因为它需要进行更多的交换操作。
交换次数不同：选择排序在每个迭代中仅交换一次元素，而冒泡排序在每个迭代中可能要交换多次元素，因此选择排序需要更少的交换操作。

实现

基本思想是在未排序的部分中找到最小元素并将其放在已排序的末尾

具体地说，算法从数组的第一个元素开始遍历，将其视为最小值，然后在未排序部分中查找更小的值，找到后交换位置。重复此过程直到整个数组都被排序。

时间复杂度为O(n^2)，因为对于每个未排序元素，都需要在剩余的未排序部分中查找最小元素。

function selectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      debugger
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 找到的没排序好的最小值
    if (minIndex !== i) {
      swap(arr, i, minIndex);
    }
  }
  return arr;
}

function swap(array, index1, index2) {
  const aux = array[index1];
  array[index1] = array[index2];
  array[index2] = aux;
}

const arr = [10, 8, 10, 2, 3, 5, 7, 8, 9, 1, 3, 4, 5];
console.log(selectionSort(arr)); // [1, 2, 3, 3, 4, 5, 5, 7, 8, 8, 9, 10, 10]

选择排序​

和冒泡排序区别​

实现​

选择排序

和冒泡排序区别

实现