Selection Sort，selectionsort

Selection Sort，selectionsort

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:

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

 

C语言 选择排序 输入k个数字,递减输出的selection_sort(array, k)程序

void selection_sort(int array[],int k)
{
int i,j,m,t;
for(i=0;im=i;
for(j=i+1;jif(array[j]m=j; //k记下目前找到的最小值所在的位置
if(m!=i){
t=array[i];
array[i]=array[m];
array[m]=t;
}
}
}
void main(){
int a[10];
for (int i=0;iscanf("%d",&a[i]);
selection_sort(a,10);
printf("排序结果为:");
for (i=0;iprintf("%d\n",a[i]);
}
 

C语言 选择排序 输入k个数字,递减输出的selection_sort(array, k)程序

void selection_sort(int array[],int k)
{
int i,j,m,t;
for(i=0;im=i;
for(j=i+1;jif(array[j]m=j; //k记下目前找到的最小值所在的位置
if(m!=i){
t=array[i];
array[i]=array[m];
array[m]=t;
}
}
}
void main(){
int a[10];
for (int i=0;iscanf("%d",&a[i]);
selection_sort(a,10);
printf("排序结果为:");
for (i=0;iprintf("%d\n",a[i]);
}