javascript选择排序

选择排序法是在要排序的一组数中，选出最小（或最大）的一个数与第一个位置的数交换；在剩下的数当中找最小的与第二个位置的数交换，即顺序放在已排好序的数列的最后，如此循环，直到全部数据元素排完为止。

选择排序是一种不稳定排序，比如 [5,8,5,2,9 ], 选择排序的时间复杂度是O(n²)，不如冒泡排序，因为冒泡排序最优时间复杂度是O(n)，选择排序的另一种变体就是上次研究的堆排序，时间复杂度降为 O(n * log₂n), 两者一样是通过交换顺序，元素被分为有序区和无序区，一直比较直到无序区元素排完为止。

 function selectionSort (arr) {
   let minTempIndex = 0
   let temp = 0
   for(let i = 0; i < arr.length - 1; i++) {
     //每一轮都跟无序区第一个元素比
     minTempIndex = i
     for(let j = i + 1; j < arr.length; j++) {
        if(arr[j] < arr[minTempIndex]) {
          minTempIndex = j
        }
     }
     //内层每一轮循环完找到最小元素，进行交换操作
     //如果无序区第一个元素即最小，就不要交换了
     if(minTempIndex != i) {
      temp = arr[i]
      arr[i] = arr[minTempIndex]
      arr[minTempIndex] = temp
     }
     
   }
   console.log(arr)
 }

本文由 dealdot ＜dealdot＃163.com＞ 创作, Full Stack Developer @ DeepBlue
本文最后编辑时间为: Jun 15, 2021 at 15:53 pm
转载请注明来源