PHP learning implementation of insertion sort

The main content of this article is to use PHP to implement insertion sort. It is a simple but classic algorithm question. I wonder if you remember it. Let’s review it with the editor.

Basic idea of ​​insertion sort: Divide the array into two areas (sorted area and unsorted area). Assume that the first element of the array is in the sorted area. The first element All elements after that are in the unsorted section. A double-layer loop is used when sorting. The outer loop is used to take out the elements to be sorted from the unsorted part and gradually reduce the unsorted part. The inner loop is used to find the insertion position from the sorted part (that is, continuously from the sorted part). Look for elements that are larger than the elements to be sorted), and then move the elements of the larger sorted area backward. The final result of the backward movement is that the last element of the sorted area element occupies the original position of the element to be sorted, and the middle of the sorted area is empty. out a position), and finally insert the element to be sorted into the empty space left after the element is moved.

//插入排序
function insert_sort($arr) {
    //获取数组单元个数
    $count = count($arr);
    //外层循环用于从未排序区域中取出待排序元素
    for ($i=1; $i < $count; $i++) {
        //获取当前需要插入已排序区域的元素值
        $temp = $arr[$i];
        //内层循环用于从已排序区域寻找待排序元素的插入位置
        for ($j=$i-1; $j >= 0; $j--) {
            //如果$arr[$i]比已排序区域的$arr[$j]小，就后移$arr[$j]
            if ($temp < $arr[$j]) {        
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $temp;
            } else {
                //如果$arr[$i]不小于$arr[$j]，则对已排序区无需再排序
                break;
            }
        }
    }
    return $arr;
}

$arr = array(6, 19, 26, 62, 88, 99, 18, 16, 1);
var_dump(insert_sort($arr));
　　测试结果：

Related tutorials: PHP video tutorial

The above is the detailed content of PHP learning implementation of insertion sort. For more information, please follow other related articles on the PHP Chinese website!