人人都会的选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

1. 算法步骤

严蔚敏版《数据结构》中对选择排序的基本思想描述为：每一趟在n-i+1(i=1,2,...,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。

具体来说，假设长度为n的数组arr，要按照从小到大排序，那么先从n个数字中找到最小值min1，如果最小值min1的位置不在数组的最左端(也就是min1不等于arr[0])，则将最小值min1和arr[0]交换，接着在剩下的n-1个数字中找到最小值min2，如果最小值min2不等于arr[1]，则交换这两个数字，依次类推，直到数组arr有序排列。算法的时间复杂度为O(n²)。
简而言之，就是每次都从剩下部分（未排序部分）把最小值找出来。

2. 代码实现

PHP代码实现

<?php

function mySort($arr)
{
    # code...
    $len = count($arr);
    for($i = 0;$i < $len;$i++){
        for($j = $i + 1;$j < $len;$j++){
            if($arr[$i] > $arr[$j]){
                $temp = $arr[$i];
                $arr[$i] = $arr[$j];
                $arr[$j] = $temp;
            }
        }
    }
    return $arr;
}

$data = [9,7,4,1,6,5];
var_dump(mySort($data));

JavaScript 代码实现

function mySort(arr) {
    var len = arr.length;
    for(var i = 0;i < len;i++){
        for(var j = i + 1; j < len;j++){
            if(arr[i] > arr[j]){
                var temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}
var data = [2,7,4,8,1,9];
console.log(mySort(data))

3. 小结

1. 时间复杂度：O(n²)，其中n为数组的长度。
2. 空间复杂度：O(1)