Insert sort _Python with PHP implementation version of recommended
- 2020-06-01 10:09:28
- OfStack
Insert sort Python implementation
import random
a=[random.randint(1,999) for x in range(0,36)]
# Direct insertion sort algorithm
def insertionSort(a):
for i in range(1,len(a)):
# If the subscript for i Is less than the subscript is i-1 , then subscript is i Put the elements in the right place
if a[i] < a[i-1]:
tmp = a[i]
j = i-1
# Looking for a[i] The appropriate location and will a[i-1] to a[i] The elements of the new position move back in order
while j >= 0 and tmp < a[j]:
a[j+1] = a[j]
j = j-1
# will a[i] Put it in a new position
a[j+1] = tmp
insertionSort(a)
print(a)
Insertion sort PHP implementation
<?php
// Generate an array to sort
$a = [];
for($i=0;$i<36;$i++){
array_push($a,mt_rand(1,999));
}
shuffle($a);
/**
* Insertion sort insertion sort
* @param [type] $a A reference to an array to be sorted
* @return null
*/
function insertionSort(&$a){
for($i = 1;$i<count($a);$i++){
// If the subscript for i Is less than the subscript is i-1 , then subscript is i Put the elements in the right place
if($a[$i] < $a[$i-1]){
$tmp = $a[$i];
// Looking for a[i] The appropriate location and will a[i-1] to a[i] The elements of the new position move back in order
for($j = $i-1; $j>=0 && $tmp<$a[$j];$j--)
$a[$j+1] = $a[$j];
// will a[i] Put it in a new position
$a[$j+1] = $tmp;
}
}
}
insertionSort($a);
var_dump($a);
Insertion sort time complexity analysis
The insertion sort algorithm has a time complexity of O (n2), but the insertion sort performs better than bubbling and selection sort.