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:

      

      
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 isO(n^2), and the time complexity of the move operation isO(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!