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:

 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 counter
10     w is for value swap
11     min is min
12     sub is index of array
13 */
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         for($j=$i; $j<$m; $j++){
22             if($a[$j] < $min){
23                 $min = $a[$j];
24                 $sub = $j;
25             }
26             else{
27                 $sub = $i;
28             }
29         }
30         $a[$sub] = $a[$i];
31         $a[$i] = $min;
32         // echo implode(', ', $a).'
';
33 } 34 } 35 36 $arr = array(9, 5, 2, 7, 3); 37 sortSelection($arr); 38 echo implode(', ', $arr); 39 40 // 2, 3, 5, 7, 9 41 ?>


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

void selection_sort(int array[],int k)
{
int i,j,m,t;
for(i=0;i m=i;
for(j=i+1;j<=k;j++)
if(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;i<10;i++)
scanf("%d",&a[i]);
selection_sort(a,10);
printf("排序结果为:");
for (i=0;i<10;i++)
printf("%d\n",a[i]);
}
 

void selection_sort(int array[],int k)
{
int i,j,m,t;
for(i=0;i m=i;
for(j=i+1;j<=k;j++)
if(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;i<10;i++)
scanf("%d",&a[i]);
selection_sort(a,10);
printf("排序结果为:");
for (i=0;i<10;i++)
printf("%d\n",a[i]);
}