PHP sorting algorithm Simple Selection Sort (Simple Selection Sort)

This article mainly introduces the PHP sorting algorithm Simple Selection Sort (Simple Selection Sort). It analyzes the principles and related implementation techniques of the Simple Selection Sort algorithm in detail in the form of examples. Friends who need it can refer to it

The example in this article describes the Simple Selection Sort of the PHP sorting algorithm. Share it with everyone for your reference, the details are as follows:

Basic idea:

Through n - i comparisons between keywords, from n - Select the record with the smallest keyword among the i 1 records and exchange it with the i-th (1 <= i <= n) record. After executing n-1 times, the sorting of the record sequence is completed.

Algorithm implementation:

<?php
//简单选择排序
//交换函数
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//简单选择排序算法
function SelectSort(array &$arr){
  $count = count($arr);
  for($i = 0;$i < $count - 1;$i ++){
    //记录第$i个元素后的所有元素最小值下标
    $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);

Running result:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

Complexity analysis:

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

In the worst case, that is, the initial state of the records to be sorted is that the first record is the largest, and subsequent records are arranged in ascending order, then the number of records that need to be moved is at most 3 (n-1). The number of comparisons required during simple selection sorting has nothing to do with the arrangement of the record sequence to be sorted in the initial state. When i=1, n-1 comparisons are required; when i=2, n-2 comparisons are required; and so on, the total number of comparisons required is (n-1) (n-2) ... 2 1=n(n-1)/2, that is, the time complexity of the comparison operation is O(n^2), and the time complexity of the move operation is O(n).

Simple selection sort is unstable sorting.

This article is referenced from "Dahua Data Structure". It is only recorded here for future reference. Please don't criticize!

Related recommendations:

PHP sorting algorithm Straight Insertion Sort

PHP sorting algorithm Hill sorting ( Shell Sort)

The above is the detailed content of PHP sorting algorithm Simple Selection Sort (Simple Selection Sort). For more information, please follow other related articles on the PHP Chinese website!