Nolan's Notes
0%

SelectionSort

Posted on Edited on In ,

选择排序

原理： 在一列数字中，选出最小数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。(以下都是升序排列，即从小到大排列)

举例说明： $arr = array(6, 3, 8, 2, 9, 1);

第一轮：

第一次比较， 第一个数 6 与（3, 8, 2, 9, 1)中 3 比较，6大，当前最小数为3，位置为 1

第二次比较， 最小数字 3 与（3, 8, 2, 9, 1)中 8 比较，3小，当前最小数为3，位置为 1

第三次比较， 最小数字 3 与（3, 8, 2, 9, 1)中 2 比较，3大，当前最小数为2，位置为 3

第四次比较， 最小数字 2 与（3, 8, 2, 9, 1)中 9 比较，2小，当前最小数为2，位置为 3

第五次比较， 最小数字 2 与（3, 8, 2, 9, 1)中 1 比较，2大，当前最小数为1，位置为 5

第一轮比较完成后，确定最小数为1，小于第一个数6，交换位置上的数，交换后结果为 1 3 8 2 9 6

总结：第一轮比较，可以确定第一个位置的最小值。

第二轮：

第一次比较， 3与（8， 2, 9, 6）中 8 比较，3小，当前最小数为3，位置为 1

第二次比较， 3与（8， 2, 9, 6）中 2 比较，3大，当前最小数为2，位置为 3

第三次比较， 2与（8， 2, 9, 6）中 9 比较，2小，当前最小数为2，位置为 3

第四次比较， 2与（8， 2, 9, 6）中 6 比较，2小，当前最小数为2，位置为 3

第二轮比较完成后，确定最小数为2，小于第二个数3，交换位置上的数，交换后结果为 1 2 8 3 9 6

总结：第二轮比较，可以确定第二个位置的最小值。至此确定了前两个位置上的数。

第三轮：

第一次比较， 8与（ 3, 9, 6）中 3 比较，8大，当前最小数为3，位置为3

第二次比较， 3与（ 3, 9, 6）中 9 比较，3小，当前最小数为3，位置为3

第三次比较， 6与（ 3, 9, 6）中 6 比较，3小，当前最小数为3，位置为3

第三轮比较完成后，确定最小数为3，小于第三个数8，交换位置上的数，交换后结果为 1 2 3 8 9 6

总结：第三轮比较，可以确定第三个位置的最小值。至此确定了前三个位置上的数。

第四轮

第一次比较， 8与（ 9, 6）中 9 比较，8小，当前最小数为8，位置为 3

第二次比较， 8与（ 9, 6）中 6 比较，8大，当前最小数为6，位置为 5

第四轮比较完成后，确定最小数为6，小于第四个数8交换位置上的数，交换后结果为 1 2 3 6 9 8

总结：第四轮比较，可以确定第四个个位置的最小值。至此确定了前四个位置上的数。

第五轮：

第一次比较， 9与 8 比较，9大，当前最小数为8，位置为5

第五轮比较完成后，确定最小数为8，小于第五个数9，交换位置上的数，交换后结果为 1 2 3 6 8 9

总结：第五轮比较，可以确定第五个个位置的最小值。至此确定了前5个位置上的数。

##总结

###综合以上五轮比较，每一轮比较都可以确定一个位置，对于N个数，比较N-1轮可以确定N个位置上的数，因为确定了N-1个位置，最后一个位置也就确定了。每i轮需要排序的次数为 N-i

PHP实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function selection_sort($arr)
{
    for ($i=0;$i<count($arr)-1;$i++){   // N个数,需要进行N-1轮次, 每轮次需要进行 (N-第几轮次) 次比较

        $minIndex = $i;

        for ($j=$i+1;$j<count($arr);$j++){  //j代表未排列好的第二个值开始到结尾
            if($arr[$j] <$arr[$minIndex]  ){
                $minIndex = $j;
            }
        }
        if($i != $minIndex){
            $temp = $arr[$i];
            $arr[$i] = $arr[$minIndex];
            $arr[$minIndex] = $temp;
            unset($temp);
        }

    }
    return $arr;

}

echo "<pre>";
$arr = array(6, 3, 8, 2, 9, 1);
$result = selection_sort($arr);
print_r($result);

GOLANG实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func sort_selection(arr []int) []int{

	for i:=0;i<len(arr);i++{
		minIndex := i
		for j:=i+1;j<len(arr) ;j++  {
			if arr[minIndex] > arr[j]{
				minIndex = j
			}
		}
		if(i != minIndex){
			arr[i],arr[minIndex] = arr[minIndex],arr[i]
		}
	}
	return arr
}

func main() {
	arr := [...]int{6,3,8,2,9,1}
	slice := arr[:]
	fmt.Println(slice)
	fmt.Println()
	fmt.Println(sort_selection(slice))
}