Introduction to bubbling, binary insertion, and quick sort algorithms

jacklove
Release: 2023-03-31 12:28:01
Original
2121 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.

'; } 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.

'; 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 'arr:'.implode(',', $arr).'
'; } 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.

'; } 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!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!