Improved direct insertion sort_PHP tutorial

The basic idea of ​​Straight Insertion Sorting is to regard n elements to be sorted as an ordered list and an unordered list. At the beginning, the ordered list contains only one element, and the unordered list contains n -1 element. During the sorting process, take out the first element from the unordered list each time and insert it into the appropriate position in the ordered list to make it a new ordered list. Repeat n-1 times to complete the sorting. process.
The specific implementation process of inserting a[i] into a[0], a[1],...,a[i-1] is: first assign a[i] to variable t, and then assign t sequentially Compare with a[i-1], a[i-2],... and move the element larger than t one position to the right until a certain j (0<=j<=i-1) is found, such that a[j]<=t or j is (-1), assign t to a[j+1].
Improved methods
A method in which search comparison operations and record move operations are performed alternately.
Specific methods:
Compare the keywords of record R[i] to be inserted with the keywords of record R[j] (j=i-1, i-2,...,1) in the ordered area from right to left:
① If the keyword of R[j] is greater than the keyword of R[i], move R[j] back one position;
②If the keyword of R[j] is less than or equal to the keyword of R[i], the search process ends, and j+1 is the insertion position of R[i].
Records with keywords larger than those of R[i] have been moved back, so the position of j+1 has been vacated. As long as R[i] is directly inserted into this position, a direct insertion sort can be completed.
That is, the comparison starts from the end of the new sequence and is shifted;
php code:
[php]
echo '

'; 

$arr = array(90,5,3,9,2,6,10,30,0,0,0,0,0); 

print_r(insertSort($arr)); 



function insertSort($arr){ 

$res = array();//Space to be inserted 

$res[0] = $arr[0];//Put the first character in first 

for($i=1;$i
          $c = count($res);//Calculate the number of loops 

for($j=$c;$j>=0;$j--){ 

If($res[$j-1]<=$arr[$i]){//$j-1 is the value to be compared, $j is the vacant bit to be inserted 

                    $res[$j] ​​= $arr[$i]; 

                    break;//The value has been inserted, end the for loop of this value 

              }else{ 

                  $res[$j] ​​= $res[$j-1];//Shift backwards 

                                                                                                                                     
         } 

}  

Return $res; 

} 

?> 

Author: dats0407 



http://www.bkjia.com/PHPjc/478117.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/478117.htmlTechArticleThe basic idea of ​​Straight Insertion Sorting is: treat n elements to be sorted as a An ordered list and an unordered list. The ordered list contains only one element at the beginning...