Fork me on GitHub

排序算法-选择排序

algorithm/selection_sort/banner

选择排序从数组的的开头开始,将第一个元素和其他元素进行比较。检查完所有元素后,最小的元素会被放到数组的第一个位置,然后算法会从第二个位置继续。这个过程进行到数组的倒数第二个位置时,所有的数据便完成了排序。

原理

选择排序会用到嵌套循环。外循环从数组的第一个元素移动到倒数第二个元素;内循环从第二个数组元素移动到最后一个元素,查找比当前外循环所指向的元素小的元素。每次内循环迭代后,数组中最小的值都会被赋值到合适的位置。

下面对五个元素的列表进行选择排序的简单例子。初始列表为:

E A D H B

第一次排序会找到最小值,并将它和列表的第一个元素进行交换:

A E D H B

接下查找第一个元素后面的最小值(第一个元素此时已经就位),并对它们进行交换:

A B D H E

D已经就位,因此下一步会对E H进行互换,列表已按顺序排列好如下:

A B D E H

通过下面的gif图,也许你会更好了解。

algorithm/selection_sort/selection_sort_demo

你可以直接进入旧金山大学的David Galles教授做的站点–用HTML5实现的各种排序算法的动画比较进行查看更加详细的演示。

代码实现

下面放出实现的选择排序的核心代码:

1
2
3
4
5
6
7
8
9
10
11
12
function selectionSort(arr){
var min;
for(var outer = 0 ; outer <= arr.length-2 ; ++outer ){
min = outer;
for(var inner = outer+1 ; inner <= arr.length-1 ; inner++){
if(arr[inner] < arr[min]){
min = inner;
}
}
swap(arr , outer , min); // 交换两个元素位置函数
}
}

更加详细的代码请戳demos/algorithm/selection_sort.js

<-- 本文已结束  感谢您阅读 -->
客官,且步,赏一个呗 (@ ~ @)