【排序算法】抉择排序【JS实现】

  作者:zhanhailiang 日期:2012-12-17

令A[1…n]为有一个有n个元素的数组，选择排序的算法描述为：首先找到最小元素，将其存放在A[1]中，然后找到剩下的n-1个元素中的最小元素，将其存放在A[2]中，重复此过程直到找到第二大的元素将其存放在A[n-1]中，这种方法称为选择排序。

/****************************************************************
算法：selectionSort
输入：A[1...n]
输出：按非降序排列的数组A[1...n]
for i = 1 to n - 1
    k = i
    for j = i + 1 to n // 查找第ｉ小的元素
        if A[j] < A[k] then k = j
    end for
    if k != i then 交换A[i]与A[k]
end for
 
显而易见，选择算法所需的元素比较次数为n(n-1)/2,即时间复杂度为O(n^2)
****************************************************************/
function selectionSort(arr) {
    var length = arr.length;
    for(var i = 0; i < length; i++) {
        var k = i;
        for(var j = i + 1; j < length; j++) {
            if(arr[j] < arr[k]) {
                k = j; // 查找第i小的元素
            }   
        }   
 
        if(k !== i) {
            var temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }   
    }   
 
    return arr;
}
 
console.log(selectionSort([5, 3, 2, 5, 8, 9]));