Introduction to bubbling, binary insertion, and quick sort algorithms-PHP Tutorial-php.cn

Introduction to bubbling, binary insertion, and quick sort algorithms

jacklove

Release： 2023-03-31 12:28:01

Original

2229 people have browsed it

1. Bubble sorting algorithm
Process:
1. Traverse the entire array and compare every pair of adjacent elements, such as $ a[$i]>$a[$i 1] swaps positions, and each comparison eliminates a reverse order.
2. After each cycle, the number of times it needs to be cycled next time is reduced by 1.

<?php
// 冒泡排序
$arr = createarr(20);
printarr($arr);
popsort($arr);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,999));
    }
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function popsort(&$arr){
    for($i=0,$length=count($arr)-1; $i<$length; $i++){
        for($j=0; $j<$length-$i; $j++){
            if($arr[$j]>$arr[$j+1]){
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $tmp;
            }
        }
    }    
}
?>

Copy after login

2. Dichotomous insertion sort

Process:
1. First of all, the original array is an ordered sequence, $low=0 $high=count($arr)-1.
2. Compare the number to be inserted with the element in the middle of the array.
If it is larger than the middle element, $low=$mid 1 will be used as the beginning of the array for the next judgment.
If it is smaller than the middle element, $high=$mid-1 will be used as the end of the array for the next judgment.
3. Until $low>$high ends, $low is the position where the new element is inserted.
4. Move all elements starting from $low in the array backward by one, and then insert new elements at the $low position.

<?php
// 二分法插入排序
$arr = createarr(20);
$key = mt_rand(0,99);
printarr($arr);
echo &#39;key=&#39;.$key.&#39;<br>&#39;;
binsort($arr, $key);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,99));
    }
    sort($arr); // 有序序列
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function binsort(&$arr, $key){
    $low = 0;
    $high = count($arr)-1;
    while($low<=$high){
        $m = $low + (int)(($high-$low)/2);
        $mkey = $arr[$m];
        if($key>=$mkey){
            $low = $m + 1;
        }else{
            $high = $m - 1;
        }
    }
    // 移动插入位置之后的元素,插入新元素
    for($i=count($arr)-1; $i>=$low; $i--){
        $arr[$i+1] = $arr[$i];
    }
    $arr[$low] = $key;
}
?>

Copy after login

3. Quick sort
Process:
1. Find an element in the array as the key, usually The first element of the array is used as the key
2. i=0, j=array length-1
3. j-- When arr[j]4. i When arr[i]>key, arr[i] and arr[j] exchange positions
5. Repeat 3,4 until i==j, complete.
6. Execute 1, 2, 3, 4, 5 (recursively) for the left and right sets of elements separated by key.

<?php
// 快速排序
$arr = createarr(20);
printarr($arr);
quicksort($arr, 0, count($arr)-1);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,999));
    }
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function quicksort(&$arr, $low, $high){
    if($low>=$high){
        return ;
    }
    $key = $arr[$low];
    $i = $low;
    $j = $high;
    $flag = 1;
    while($i!=$j){
        switch($flag){
            case 0:
                if($arr[$i]>$key){
                    $tmp = $arr[$i];
                    $arr[$i] = $arr[$j];
                    $arr[$j] = $tmp;
                    $flag = 1;
                }else{
                    $i++;
                }
                break;
            case 1:
                if($arr[$j]<$key){
                    $tmp = $arr[$i];
                    $arr[$i] = $arr[$j];
                    $arr[$j] = $tmp;
                    $flag = 0;
                }else{
                    $j--;
                }
                break;
        }
    }
    quicksort($arr, $low, $i-1);
    quicksort($arr, $i+1, $high);
}
?>

Copy after login

This article explains bubbling, dichotomous insertion, and quick sorting algorithms. For more related content, please pay attention to the PHP Chinese website.

Related recommendations:

How to filter html tag attribute classes through php

How to use php to replace related operations of sensitive strings

About PHP traversing folders and file classes and processing classes

The above is the detailed content of Introduction to bubbling, binary insertion, and quick sort algorithms. For more information, please follow other related articles on the PHP Chinese website!