PHP common sorting algorithm

1. Bubble sort

The basic idea ： As shown in the figure below , Think of a set of data as a row of vertical bubbles , Then compare the last number with the penultimate number , Move the big one forward . And then in the same way , Compare the penultimate number with the penultimate number , Move the big one forward , By analogy , At the end of this cycle , The first element is the largest , And then the cycle goes on , Get a second , Third ……

function BubbleSort(&$arr){    // Must be &$arr, Send an address , If it is $arr, According to the function call mechanism , Sorting will not take effect 
    $temp = 0; // Intermediate variable 
	$flag = false;
	// The outer cycle controls the number of cycles 
	for($i = 0; $i < count($arr) - 1; $i++) {
		// The inner loop controls the exchange of each cycle 
		for($j = 0; $j < count($arr) - 1 - $i; $j++) {
			if($arr[$j] > $arr[$j+1]) {
				$temp = $arr[$j];
				$arr[$j] = $arr[$j+1];
				$arr[$j+1] = $temp;
				$flag = true;
			}
		}
		if(!$flag)
			break; //  It's already orderly 
		
		$flag = false;
	}
	return $arr;
}

2. Choose the sorting method

First , Compare the first one with all the others behind , Find the smallest number , Then swap with the first number （ Of course , If it is the first smallest , Then there is no need to exchange ）, Then the cycle , namely ： Compare the second with the latter , Find the smallest number , Then interchange with the second number , By analogy , That is to say, find out the minimum remaining value every time .

function selectSort(&$arr){
    $temp = 0; //  Intermediate variable 
	// The outer loop 
	for($i=0;$i<count($arr)-1;$i++){
	    // Hypothesis number 1 $i The number is the smallest number 
	        
	    // Record the value of the assumed minimum 
	    $minVal=$arr[$i];
	    // Record the subscript of the lowest fraction of the hypothesis 
	    $minIndex=$i;
	    for($j=$i+1;$j<count($arr);$j++){
	        // If the assumed minimum , Not the smallest 
	        if($minVal>$arr[$j]){
	            $minVal=$arr[$j];
	            $minIndex=$j;
	        }
	    }
	    // Finally exchange 
	    $temp=$arr[$i];
	    $arr[$i]=$arr[$minIndex];    // Outside of the loop , Cannot appear $j
	    $arr[$minIndex]=$temp;
	}
	return $arr;
}

3. Insertion sort

The basic idea of insertion sorting is ： In the set of numbers to sort , Suppose the previous numbers are already in order , Now let's put the n The number is inserted into the preceding ordinal number , Make this n The number is also in order . So repeatedly , Until it's all in order

function insertSort(&$arr){
    // Default to the first number , That is, the subscript is 0 Number of numbers , It's already orderly 
	for($i=1;$i<count($arr);$i++){
        // Number of ready inserts 
	    $insertVal=$arr[$i];
	    // Ready to make peace first $insertIndex Compare 
	    $insertIndex=$i-1;
	    while($insertIndex>=0 && $insertVal<$arr[$insertIndex]){
	        $arr[$insertIndex+1]=$arr[$insertIndex];
	        $insertIndex--;
	    }
	    $arr[$insertIndex+1]=$insertVal;
	}
	return $arr;
}

4. Quick sort

Select a datum element , Usually select the first or last element . Through a scan , Divide the sequence to be arranged into two parts , Part smaller than the reference element , A part is greater than or equal to the datum element . At this time, the reference element is in the correct position after it is arranged , And then sort the two parts recursively in the same way .

function quickSort(&$arr) {
    // First determine whether it is necessary to continue 
	$length = count($arr);
	if($length <= 1) {
	    return $arr;
	}
	// Select the first element as the base 
	$base_num = $arr[0];
	// Traverse all elements except the ruler , Put it into two arrays according to the size relationship 
	// Initialize two arrays 
	$left_array = array();  // Less than datum 
	$right_array = array();  // Greater than the benchmark 
	for($i=1; $i<$length; $i++) {
	    if($base_num > $arr[$i]) {
	        // Put it in the left array 
	        $left_array[] = $arr[$i];
	    } else {
	        // Put it on the right 
	        $right_array[] = $arr[$i];
	    }
	}
	// Then sort the arrays on the left and right in the same way, and call this function recursively 
	$left_array = quickSort($left_array);
	$right_array = quickSort($right_array);
	// Merge 
	return array_merge($left_array, array($base_num), $right_array);
}

5. Exchange sort

Exchange sorting ideas ： It is to exchange the positions of the two values in the sequence according to the comparison results of the two values in the array , The characteristics of exchange sorting are ： Move the larger value towards the end of the array , Smaller values move towards the front of the array .

function exchangeSort($arr){
    $len = count($arr);// Get array length 
	for ($i = 0;$i < $len - 1; $i++) {
	    for ($j = $i + 1; $j < $len; $j++) {
		    if ($arr[$j] < $arr[$i]) {
			    $iTemp = $arr[$i];
			    $arr[$i] = $arr[$j];
			    $arr[$j] = $iTemp;
			}
	    }
    }
	return $arr;
}