PHP simple selection sorting algorithm learning

This article mainly introduces the PHP Simple Selection Sort algorithm in detail, which has certain reference value. Interested friends can refer to it.

The examples in this article are shared with you. The specific code for PHP simple selection sorting is for your reference. The specific content is 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 (1 <= i <= n) record. After 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);

##Complexity analysis:

In a simple selection sort process, fewer records are moved. 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 comparison operation is O(n^2), and the time complexity of move operation is O(n).

Simple selection sort is unstable sorting.

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

The above is the entire content of this article. I hope it will be helpful to everyone's study. I also hope that everyone will support the php Chinese website.

Articles you may be interested in:

Detailed explanation of WeChat Tiaoyitiao PHP code implementation

Explanation of the WeChat sharing to Moments and recording the number of sharing functions implemented by php

Explanation of PHP parsing xml format data tool class example

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