JIYIK CN >

Selection sort is a simple and intuitive sorting algorithm. Its basic idea is to select a maximum (or minimum) element in an unsorted sequence and put it at the end (note: this is the end of the unsorted sequence, which can be considered as the starting position of the ordered sequence).

Let's take a look at this selection process through a simple illustration.

First, record and select the first element as the default maximum value, v stores the value, and p stores the position.

v = 10, p = 0

Then start from the first position and search backward for an element greater than 10, and replace the values ​​of v and p after finding them.

v = 12, p = 2

v = 30, p = 3

Until the last element, 30 is the largest element in the unsorted sequence.

Then 30 and the last element are swapped, and 30 is no longer involved in the comparison in the next selection.

The second choice, the initial values ​​of v and p are 0 and 10

v = 10，p = 0

After searching, we finally determined that v = 15 and p = 3

Then swap 15 and 5 (because 30 is no longer in the sort order)

15 and 30 are no longer included in the sorting.

Then follow the above process to select and exchange until all elements are in order

The above is the whole process of selection sorting. The steps of sorting in words are

1) First, find the smallest (largest) element in the unsorted sequence and store it at the beginning of the sorted sequence
. 2) Then continue to find the smallest (largest) element from the remaining unsorted elements and place it at the end of the sorted sequence.
3) Repeat the second step until all elements are sorted.

Let's look at the code implementation of selection sort

/**
 * 交换函数
 */
function swap(&$arr,$a,$b){
    $t = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $t;
}
function SelectSort(&$arr){
    $end = count($arr)-1;
    do{
        $p = 0;
        for($i=0;$i<=$end;$i++){
            if($arr[$i]>$arr[$p]){
                $p = $i;
            }
        }
        swap($arr,$p,$end);
    }while(--$end>0);
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
SelectSort($arr);
print_r($arr);

We can see from the code above that selection sort is very intuitive. Its implementation idea is very simple and not complicated.

But there is one thing we need to note. Although selection sort is simple, its efficiency is lower than other sorting algorithms. Its time complexity is O(n²). So in the application, we must choose our sorting algorithm according to the actual situation.

I hope this article is helpful to you.