选择排序

选择排序（Selection Sort）

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n²)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一好就是不占用额外的内存空间。

选择排序原理示意图

算法简介

选择排序（Selection-Sort）是一种简单直观的排序算法。他的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后再从剩余未排序元素中继续寻找最小（大）元素，然后放到以排序序列的末尾。以此类推，直到所有元素均排序完毕

算法描述和实现

具体算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

  • 初始状态：无序区为R[1..n]，有序区为空；
  • 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
  • n-1趟结束，数组有序化了。

js代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function selectionSort(arr){
    let minIndex, temp
    for(let i = 0 ; i < arr.length - 1 ; i++){ // 不用比较最后一个
        minIndex = i // 默认为当前值
        for(let j = i + 1 ; j < arr.length ; j++){ // 每次从下一个数开始循环
            if(arr[j] < arr[minIndex]){ // 寻找最小数
                minIndex = j // 将最小数的索引保存
            }
        }
        temp = arr[i]    // 保存当前项
        arr[i] = arr[minIndex] // 当前项替换为最小值
        arr[minIndex] = temp // 最小索引替换为当前项
    }
    return arr
}
// var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
//  var arr = [3,1,2,4,5]
console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]