Detailed explanation of PHP simple selection sorting case

This time I will bring you PHP simple selection sorting case details, what are the precautions for PHP simple selection sorting , the following is a practical case, let's take a look.

Basic idea:

Select keywords from n - i 1 records through n - i comparisons between keywords The smallest record is exchanged 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 results:

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.

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the php Chinese website!

Recommended reading:

Detailed explanation of the steps to use the PHP quick sort algorithm

Detailed explanation of the steps to use the PHP radix sort

The above is the detailed content of Detailed explanation of PHP simple selection sorting case. For more information, please follow other related articles on the PHP Chinese website!