PHP simple selection sorting algorithm learning sharing

This article mainly introduces the PHP Simple Selection Sort algorithm in detail. It has certain reference value. Interested friends can refer to it. I hope it can help everyone.

The example in this article shares the specific code of simple selection sorting in PHP for your reference. The specific content is as follows

Basic idea:

Pass n - Comparison between i keywords, select the record with the smallest keyword from n - i + 1 records, and exchange it with the i (1 <= i <= n) record, executing n-1 times Finally, 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);

Complexity analysis:

In simple selection During the 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.

Related recommendations:

Detailed explanation of direct selection sorting in the PHP sorting algorithm series

Detailed explanation of bucket sorting in the PHP sorting algorithm series_php skills

Detailed analysis of the method of implementing Hill sorting algorithm in PHP

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