PHP Simple Selection Sorting (Simple Selection Sort) Algorithm Learning

In this paper, we share the specific code of PHP simple selection sorting for your reference, and the specific contents are as follows

Basic ideas:

By comparing the keywords between n-i times, the record with the smallest keyword was selected from the records of n-i + 1, and compared with the records of i (1 < = i < = n) records are exchanged, and the sequence of records is sorted after n-1.

Algorithm implementation:

<?php

// Simple selection sort 

// Commutative function 
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
// Simple selection sorting algorithm 
function SelectSort(array &$arr){
  $count = count($arr);
  for($i = 0;$i < $count - 1;$i ++){
    // Record number $i Minimum value subscript of all elements after 10 elements 
    $min = $i;
    for($j = $i + 1;$j < $count;$j ++){
      if($arr[$j] < $arr[$min]){
        $min = $j;
      }
    }

    if($min != $i){
      swap($arr,$min,$i);
    }
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
SelectSort($arr);
var_dump($arr);

Complexity analysis:

In the process of simple selection and sorting, the number of times to move records is relatively small. In the best case, that is, the initial state of the records to be sorted is already in positive order, so there is no need to move the records.

In the worst case, that is, the initial state of the records to be sorted is the largest according to the first record, and the subsequent records are arranged from small to large, the maximum number of times to move the records is 3 (n-1). The number of comparisons required in the simple selection sorting process is independent of the arrangement of record sequences to be sorted in the initial state. When i=1, n-1 comparison is needed. When i=2, n-2 comparisons are required. By analogy, the total number of comparisons needed is (n-1) + (n-2) + … +2+1=n (n-1)/2, that is, the time complexity of comparison operation is O (n ^ 2), and the time complexity of movement operation is O (n).

Simple selection sort is unstable sort.

This blog is referenced from "Dahua Data Structure", which is only recorded here, which is convenient for future reference. Don't spray it!