乐趣区

关于前端:选择排序

抉择排序

原文链接:https://note.noxussj.top/?source=sifo

什么是抉择排序(selectSort)?

抉择排序就是在一个排列中划分为有序区和无序区,有序区在右边,无序区在左边。首先在无序区中找到最小元素,寄存到有序区的起始地位,而后再从残余的无序区中持续寻找最小元素,而后放到有序区的开端。以此类推,直到无序区没有元素可排列。


算法步骤

  1. 首先在数组中查找出最小的元素
  2. 把以后最小元素放在数组的第一位
  3. 持续查找数组中最小的元素(不蕴含方才找过的最小元素)
  4. 把以后最小元素放在数组的第二位
  5. 以此类推,执行 n – 1 轮
  6. 实现排序

动画演示链接

https://visualgo.net/zh/sorting


根底案例

  • 工夫复杂度:O (n ^ 2)
  • 空间复杂度:O (1)
    Array.prototype.selectSort = function () {for (let i = 0; i < this.length - 1; i++) {
            let indexMin = i
    
            for (let j = i; j < this.length; j++) {if (this[j] < this[indexMin]) {indexMin = j}
            }
    
            if (indexMin !== i) {const temp = this[i]
                this[i] = this[indexMin]
                this[indexMin] = temp
            }
        }
    }
    
    const arr = [5, 4, 3, 2, 1]
    
    arr.selectSort() // [1, 2, 3, 4, 5]

因为存在两个嵌套循环,所以工夫复杂度是 O (n ^ 2),而工夫复杂度是 O (1),因为没有应用线性增长的数据结构。


原文链接:https://note.noxussj.top/?source=sifo

退出移动版