<?php
/**
* Created by PhpStorm.
* User: 63448
* Date: 2018/5/5
* Time: 22:42
*/
$arr = [3,1,13,5,7,11,2,4,14,9,150,6,12,10,8];
// 冒泡排序
/**
* 思路分析：在要排序的一组数中，对当前还未排好的序列，从前往后对相邻的两个数依次进行比较和调整，
* 让较大的数往下沉，较小的往上冒。即，每当两相邻的数比较后发现它们的排序与排序要求相反时，
* 就将它们互换。代码实现：
*/
function bubbleSort($arr) {
$length = count($arr); // 数组长度
for ($i = 1; $i < $length; $i++) { // 正向遍历数组
for ($j = $length - 1; $j >= $i ; $j--) { // 反向遍历
if ($arr[$j] < $arr[$j-1]) { // 相邻两个数比较
$iTemp = $arr[$j-1]; // 暂存较小的数
$arr[$j-1] = $arr[$j]; // 较大的放前面
$arr[$j] = $iTemp; // 较小的放后面
}
}
}
return $arr;
}
var_dump(bubbleSort($arr));
/**
* 2.选择排序
*思路分析：在要排序的一组数中，选出最小的一个数与第一个位置的数交换。
* 然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
*/
function choiceSort($arr) {
$length = count($arr); // 数组长度
for ($i = 0;$i < $length-1; $i++) { // 遍历数组
$iTemp = $arr[$i]; // 暂存当前值
$iPos = $i; // 暂存当前位置
for ($j = $i + 1;$j < $length; $j++){ // 遍历当前位置以后的数据
if ($arr[$j] < $iTemp) { // 如果有小于当前值的
$iTemp = $arr[$j]; // 暂存最小值
$iPos = $j; // 暂存位置
}
}
$arr[$iPos] = $arr[$i]; // 把当前值放到算好的位置
$arr[$i] = $iTemp; // 把当前值换成算好的值
}
return $arr;
}
var_dump(choiceSort($arr));
/**
* 3.插入排序
*思路分析：在要排序的一组数中，假设前面的数已经是排好顺序的，现在要把第n个数插到前面的有序数中，
* 使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
*/
function insertSort($arr){
$length = count($arr);
for ($i = 1;$i < $length; $i++) { // 遍历数组
$iTemp = $arr[$i]; // 获得当前值
$iPos = $i - 1; // 获得当前值的前一个位置
while (($iPos >= 0) && ($iTemp < $arr[$iPos])) { // 如果当前值小于前一个值切未到数组开始位置
$arr[$iPos + 1] = $arr[$iPos]; // 把前一个的值往后放一位
$iPos--; // 位置递减
}
$arr[$iPos+1] = $iTemp;
}
return $arr;
}
var_dump(insertSort($arr));
/**
* 4.快速排序
*思路分析：选择一个基准元素，通常选择第一个元素或者最后一个元素。
* 通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素。
* 此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。
*/
function quickSort($arr){
$length = count($arr);
$l = $r = 0;
$left = $right = array();
// 从索引的第二个开始遍历数组
for ($i = 1;$i < $length; $i++) {
// 如果值小于索引1
if ($arr[$i] < $arr[0]) {
// 装入左索引数组(小于索引1的数据)
$left[] = $arr[$i];
$l++;
} else {
// 否则装入右索引中(大于索引1的数据)
$right[] = $arr[$i];
$r++; //
}
}
// 如果左索引有值 则对左索引排序
if($l > 1) {
$left = QuickSort($left);
}
// 排序后的数组
$new_arr = $left;
// 将当前数组第一个放到最后
$new_arr[] = $arr[0];
// 如果又索引有值 则对右索引排序
if ($r > 1) {
$right = QuickSort($right);
}
// 根据右索引的长度再次增加数据
for($i = 0;$i < $r; $i++) {
$new_arr[] = $right[$i];
}
return $new_arr;
}
var_dump(quickSort($arr));
/**
* 5.希尔排序
* 思路分析：将数组按指定步长分隔成若干子序列，然后分别对子序列进行排序（在这是直接）
*/
function shellSort($arr) {
$len = count($arr);
$k = floor($len/2);
while($k > 0) {
for($i = 0; $i < $k; $i++) {
for($j = $i; $j < $len, ($j + $k) < $len; $j = $j + $k) {
if($arr[$j] > $arr[$j+$k]) {
$tmp = $arr[$j+$k];
$arr[$j+$k] = $arr[$j];
$arr[$j] = $tmp;
}
}
}
$k = floor($k/2);
}
return $arr;
}
var_dump(shellSort($arr));
/**
* 6.堆排序
* 思路分析：调整子堆的为大根堆的过程
* @param array &$arr 数组
* @param int $s 子堆的根的位置
* @param int $m 堆最后一个元素位置
* @return array
*/
function heapAdjust(&$arr, $s, $m) {
$tmp = $arr[$s];
// 在调整为大根堆的过程中可能会影响左子堆或右子堆
// for循环的作用是要保证子堆也是大根堆
for($j = 2*$s + 1; $j <= $m; $j = 2*$j + 1) {
// 找到根节点的左右孩子中的最大者，然后用这个最大者与根节点比较，
// 若大则进行调整，否则符合大根堆的 特点跳出循环
if($j < $m && $arr[$j] < $arr[$j+1]) {
$j++;
}
if($tmp >= $arr[$j] ) {
break;
}
$arr[$s] = $arr[$j];
$s = $j;
}
$arr[$s] = $tmp;
}
// 堆排序
function heapSort($arr) {
$len = count($arr);
// 依次从子堆开始调整堆为大根堆
for($i = floor($len/2-1); $i >= 0; $i--) {
heapAdjust($arr, $i, $len-1);
}
// 依次把根节点调换至最后一个位置，再次调整堆为大根堆，找到次最大值，
// 依次类推得到一个有序数组
for($n = $len-1; $n > 0; $n--) {
$tmp = $arr[$n];
$arr[$n] = $arr[0];
$arr[0] = $tmp;
heapAdjust($arr, 0, $n-1);
}
return $arr;
}
var_dump(heapSort($arr));
/**
* 7.交换法排序
* @param array $arr
* @return array
*/
function swapSort($arr){
$length = count($arr);
// 遍历数组
for ($i = 0;$i < $length - 1; $i++) {
// 获得当前索引的下一个索引
for ($j = $i + 1; $j < $length; $j++) {
// 比较相邻两个的值大小
if ($arr[$j] < $arr[$i]) {
// 暂存较小的数
$iTemp = $arr[$i];
// 较大的放前面
$arr[$i] = $arr[$j];
// 较小的放后面
$arr[$j] = $iTemp;
}
}
}
return $arr;
}
var_dump(swapSort($arr));
/**
* 8.归并排序
* 思路分析：这里实现的是两路归并(分别将有序的arr1[s..m]、arr2[m+1..n]归并为有序的$arr2[s..n])
* @param array &$arr1
* @param array &$arr2
* @param int $s
* @param int $m
* @param int $n
*/
function Merge(&$arr1, &$arr2, $s, $m, $n) {
for($k = $s,$i = $s, $j = $m+1; $i <= $m && $j <= $n; $k++) {
if($arr1[$i]<$arr1[$j]) {
$arr2[$k] = $arr1[$i++];
}else {
$arr2[$k] = $arr1[$j++];
}
}
if($i <= $m) {
for(; $i <= $m; $i++) {
$arr2[$k++] = $arr1[$i];
}
}else if($j <= $n) {
for(; $j <= $n; $j++) {
$arr2[$k++] = $arr1[$j];
}
}
}
//递归形式的两路归并
function MSort(&$arr1, &$arr2, $s, $t) {
if($s == $t) {
$arr2[$s] = $arr1[$s];
}else {
$m = floor(($s+$t)/2);
$tmp_arr = array();
MSort($arr1, $tmp_arr, $s, $m);
MSort($arr1, $tmp_arr, $m+1, $t);
Merge($tmp_arr, $arr2, $s, $m, $t);
}
}
// *对一位数组$arr[0..n-1]中的元素进行两路归并
function mergeSort($arr) {
$len = count($arr);
MSort($arr, $arr, 0, $len-1);
return $arr;
}
var_dump(mergeSort($arr));
//冒泡排序 http://www.yduba.com/biancheng-3962519476.html
//
//选择排序 http://www.yduba.com/biancheng-4732577282.html
//
//插入排序 http://www.yduba.com/biancheng-2892530909.html
//
//希尔排序 http://www.yduba.com/biancheng-5472542087.html
//
//归并排序 http://www.yduba.com/biancheng-9902519493.html
//
//快速排序 http://www.yduba.com/biancheng-0362533007.html
//
//堆排序 http://www.yduba.com/biancheng-4622548289.html
//
//计算排序 http://www.yduba.com/biancheng-1362548964.html
//
//桶排序 http://www.yduba.com/biancheng-7382573665.html
//
//基数排序 http://www.yduba.com/biancheng-6212544194.html
