算法简介

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

算法步骤

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
• 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
• 重复第二步，直到所有元素均排序完毕。

代码实现

复制
1function selectionSort(arr) {
2    var len = arr.length;
3    var minIndex, temp;
4    console.time('选择排序耗时');
5    for (var i = 0; i < len - 1; i++) {
6        minIndex = i;
7        for (var j = i + 1; j < len; j++) {
8            if (arr[j] < arr[minIndex]) {     //寻找最小的数
9                minIndex = j;                 //将最小数的索引保存
10            }
11        }
12        temp = arr[i];
13        arr[i] = arr[minIndex];
14        arr[minIndex] = temp;
15    }
16    console.timeEnd('选择排序耗时');
17    return arr;
18}
19var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
20console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

算法分析

• 最佳情况：T(n) = O(n2)
• 最差情况：T(n) = O(n2)
• 平均情况：T(n) = O(n2)