返回首页 - Notes - 2013

选择排序


算法描述

首先找到数组中最小的元素,将它替换到数组的最前面

然后除去数组最前面已经排序过的元素,将剩下的元素当成新的数组,再次执行 “查找最小元素,然后替换到最前面” 的操作

这样最终执行完成以后,数组元素值就是从小到大依次排列的了


算法实现

Ruby

# 选排
class Array
  def select_sort!
    len  = self.length
    0.upto(len - 1) do |i|
      min = i
      (i + 1).upto(len - 1) do |j|
        min = j if self[j] < self[min]
      end
      self[i], self[min] = self[min], self[i] if min != i
    end
  end
end


# 测试
arr = (1..10).to_a.shuffle
p arr

arr.select_sort!
p arr

PHP

<?php

// 选排
function select_sort (&$arr) {
    $len = count($arr);
    for ($i = 0; $i < $len; ++$i) {
        $min = $i;
        for ($j = $i + 1; $j < $len; ++$j) {
            if ($arr[$j] < $arr[$min]) {
                $min = $j;
            }
        }
        if ($min != $i) {
            $temp = $arr[$i];
            $arr[$i] = $arr[$min];
            $arr[$min] = $temp;
        }
    }
}


// 打印数组
function print_arr ($arr) {
    echo '[';
    for ($i = 0; $i < count($arr) - 1; ++$i) {
        echo $arr[$i].' ';
    }
    echo $arr[count($arr) - 1];
    echo ']';
}


// 测试
$arr = range(1, 10);
shuffle($arr);
print_arr($arr);
echo "\n";

select_sort($arr);
print_arr($arr);
echo "\n";

date : 2013-02-21、2014-11-24