Selection Sort，selectionsort_PHP教程
- WBOY原創
- 2016-07-13 10:14:52863瀏覽
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> ?>
void selection_sort(int array[],int k)
{
int i,j,m,t;
for(i=0;i
for(j=i+1;jif(array[j]
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]);
}
void selection_sort(int array[],int k)
{
int i,j,m,t;
for(i=0;i
for(j=i+1;jif(array[j]
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]);
}