Home >Backend Development >PHP Tutorial >php bubble sort quick sort

php bubble sort quick sort

WBOY
WBOYOriginal
2016-07-29 09:10:01837browse

/******
1) Bubble sorting: 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 ​​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>$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>$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>$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>));

The above introduces PHP bubble sort and quick sort, including insertion sort. I hope it will be helpful to friends who are interested in PHP tutorials.

Statement:
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