首页 > 代码库 > Selection Sort

Selection Sort

2024-08-01 04:08:18   210人阅读

Red is current min. Yellow is sorted list. Blue is current item. (picture from wikipedia, a little too fast)

 

10 numbers. Sort as ascend.

 

1. Find the min of the 10 and switch it with a[0], requires 9 times of compare

2. Find the min of the rest 9 and switch it with a[1], requires 8 times of compare

. . .

 

1, 10, 9

2, 9, 8

3, 8, 7

4, 7, 6

5, 6, 5

6, 5, 4

7, 4, 3

8, 3, 2

9, 2, 1

 

In conclusion: For 10 numbers, we need 9 times of finding the min, each has one-short amount of numbers to compare.

 

Implementation in PHP:

 1 <?php 2 /* selection sort:  3     1. operate directly on the input array (&), not on a copy 4     2. sort as ascend 5  6     a is array 7     m is length of a 8     n is times of outer loop, which is finding min of the rest 9     i/j is for-loop counter10     w is for value swap11     min is min12     sub is index of array13 */14 function sortSelection(&$a){15     $m = count($a);16     $n = $m - 1;17     $min;18     $sub;19     for($i=0; $i<$n; $i++){20         $min = $a[$i];21         $sub = $i;22         for($j=$i; $j<$m; $j++){23             if($a[$j] < $min){24                 $min = $a[$j];25                 $sub = $j;26             }27             else{28                 //29             }30         }31         $a[$sub] = $a[$i];32         $a[$i] = $min;33         // echo implode(‘, ‘, $a).‘<br />‘;34     }35 }36 37 $arr = array(9, 5, 2, 7, 3, 1, 6, 4, 0, 8);38 sortSelection($arr);39 echo implode(‘, ‘, $arr);40 41 // 0, 1, 2, 3, 4, 5, 6, 7, 8, 942 ?>

 

Selection Sort


联系
我们