Home >Backend Development >PHP Tutorial >php bubble sort quick sort, php bubble sort_PHP tutorial
php bubble sort quick sort, php bubble sort_PHP tutorial
- WBOYOriginal
- 2016-07-12 09:03:111225browse
php bubble sort quick sort, php bubble sort
/******
1) Bubble sort: Exchange values in pairs, with the smallest value on the left, just like the lightest bubble on the top.
2) Exchange the entire column of numbers once, with the smallest number on the far left. Each time, you can get the smallest number among the remaining numbers. The "popped" numbers form an ordered interval, and the remaining numbers are The values below form an unordered interval, and the value of each element in the ordered interval is smaller than that of the unordered interval.
3) Quick sort: base number, left and right arrays, recursive call, merge.
4) Insertion sort: The sorting interval is divided into two parts, the left side is ordered and the right side is unordered. Take the first element from the right interval and insert it into the left interval. If this element is larger than the rightmost element of the left interval, leave it where it is. If this element is smaller than the rightmost element in the left range, it will be inserted at the original position of the rightmost element. At the same time, the rightmost element will be shifted one position to the right. The calculator will be reduced by one and will be compared with the previous element again until the previous element is smaller than the previous element. To insert elements as small as possible, repeat the above steps.
6) Pay attention to the processing of interval endpoint values, and the subscript of the first element of the array is 0.
***/
<span><br />$a</span>=<span>array</span>('3','8','1','4','11','7'<span>);
</span><span>print_r</span>(<span>$a</span><span>);
</span><span>$len</span> = <span>count</span>(<span>$a</span><span>);
</span><span>//</span><span>从小到大</span>
<span>for</span>(<span>$i</span>=1;<span>$i</span><<span>$len</span>;<span>$i</span>++<span>)
{
</span><span>for</span>(<span>$j</span>=<span>$len</span>-1;<span>$j</span>>=<span>$i</span>;<span>$j</span>--<span>)
</span><span>if</span>(<span>$a</span>[<span>$j</span>]<<span>$a</span>[<span>$j</span>-1<span>])
{</span><span>//</span><span>如果是从大到小的话，只要在这里的判断改成if($b[$j]>$b[$j-1])就可以了</span>
<span>$x</span>=<span>$a</span>[<span>$j</span><span>];
</span><span>$a</span>[<span>$j</span>]=<span>$a</span>[<span>$j</span>-1<span>];
</span><span>$a</span>[<span>$j</span>-1]=<span>$x</span><span>;
}
}
</span><span>print_r</span>(<span>$a</span><span>);
</span><span>//</span><span>另一种方法 从小到大</span>
<span>$b</span>=<span>array</span>('4','3','8','9','2','1'<span>);
</span><span>$len</span>=<span>count</span>(<span>$b</span><span>);
</span><span>for</span>(<span>$k</span>=1;<span>$k</span><<span>$len</span>;<span>$k</span>++<span>)
{
</span><span>for</span>(<span>$j</span>=<span>$len</span>-1,<span>$i</span>=0;<span>$i</span><<span>$len</span>-<span>$k</span>;<span>$i</span>++,<span>$j</span>--<span>)
</span><span>if</span>(<span>$b</span>[<span>$j</span>]<<span>$b</span>[<span>$j</span>-1<span>]){
</span><span>//</span><span>如果是从大到小的话，只要在这里的判断改成if($b[$j]>$b[$j-1])就可以了</span>
<span>$tmp</span>=<span>$b</span>[<span>$j</span><span>];
</span><span>$b</span>[<span>$j</span>]=<span>$b</span>[<span>$j</span>-1<span>];
</span><span>$b</span>[<span>$j</span>-1]=<span>$tmp</span><span>;
}
</span><span>print_r</span>(<span>$b</span><span>);
</span><span>echo</span> "
"<span>;
}
</span><span>//</span><span>下面的这个执行效率更高</span>
<span>function</span> maopao(<span>$arr</span><span>)
{
</span><span>$len</span> = <span>count</span>(<span>$arr</span><span>);
</span><span>for</span>(<span>$i</span>=1; <span>$i</span><<span>$len</span>; <span>$i</span>++)<span>//</span><span>最多做n-1趟排序</span>
<span> {
</span><span>$flag</span> = <span>false</span>; <span>//</span><span>本趟排序开始前，交换标志应为假</span>
<span>for</span>(<span>$j</span>=<span>$len</span>-1;<span>$j</span>>=<span>$i</span>;<span>$j</span>--<span>)
{
</span><span>if</span>(<span>$arr</span>[<span>$j</span>]<<span>$arr</span>[<span>$j</span>-1])<span>//</span><span>交换记录</span>
{<span>//</span><span>如果是从大到小的话，只要在这里的判断改成if($arr[$j]>$arr[$j-1])就可以了</span>
<span>$x</span>=<span>$arr</span>[<span>$j</span><span>];
</span><span>$arr</span>[<span>$j</span>]=<span>$arr</span>[<span>$j</span>-1<span>];
</span><span>$arr</span>[<span>$j</span>-1]=<span>$x</span><span>;
</span><span>$flag</span> = <span>true</span>;<span>//</span><span>发生了交换，故将交换标志置为真</span>
<span> }
}
</span><span>if</span>(! <span>$flag</span>)<span>//</span><span>本趟排序未发生交换，提前终止算法</span>
<span>return</span> <span>$arr</span><span>;
}
}
</span><span>$shuz</span> = <span>array</span>('2','4','1','8','5'<span>);
</span><span>$bb</span> = maopao(<span>$shuz</span><span>);
</span><span>print_r</span>(<span>$bb</span><span>);
</span><span>//</span><span> 快速排序</span>
<span>function</span> kuaisu(<span>$arr</span><span>){
</span><span>$len</span> = <span>count</span>(<span>$arr</span><span>);
</span><span>if</span>(<span>$len</span> <= 1<span>){
</span><span>return</span> <span>$arr</span><span>;
}
</span><span>$key</span> = <span>$arr</span>[0<span>];
</span><span>$left_arr</span> = <span>array</span><span>();
</span><span>$right_arr</span> = <span>array</span><span>();
</span><span>for</span>(<span>$i</span>=1; <span>$i</span><<span>$len</span>;<span>$i</span>++<span>){
</span><span>if</span>(<span>$arr</span>[<span>$i</span>] <= <span>$key</span><span>){
</span><span>$left_arr</span>[] = <span>$arr</span>[<span>$i</span><span>];
}</span><span>else</span><span>{
</span><span>$right_arr</span>[] = <span>$arr</span>[<span>$i</span><span>];
}
}
</span><span>$left_arr</span> = kuaisu(<span>$left_arr</span><span>);
</span><span>$right_arr</span> = kuaisu(<span>$right_arr</span><span>);
</span><span>return</span> <span>array_merge</span>(<span>$left_arr</span>, <span>array</span>(<span>$key</span>), <span>$right_arr</span><span>);
}
</span><span>$arr</span> = <span>array</span>(23,98,54,2,9,62,34<span>);
</span><span>print_r</span>(kuaisu(<span>$arr</span>));