欢迎来到GM源码之家!会员签到可免费领金币,开通会员下载免金币(本站金币1:10)
广告位出租
广告位招租
php语言的7种基本的排序方法
时间:2021-07-20 来源:网络收集 作者:秩名 浏览: 次  推荐  打印

这篇文章主要为大家详细介绍了7种php基本排序实现方法,感兴趣的小伙伴们可以参考一下,本文总结了一下常用的7种排序方法,并用php语言实现。


1、直接插入排序


/* 
 * 直接插入排序,插入排序的思想是:当前插入位置之前的元素有序, 
 * 若插入当前位置的元素比有序元素最后一个元素大,则什么也不做, 
 * 否则在有序序列中找到插入的位置,并插入 
 */ 
function insertSort($arr) { 
 $len = count($arr);  
 for($i = 1; $i < $len; $i++) { 
  if($arr[$i-1] > $arr[i]) { 
   for($j = $i – 1;$j >= 0; $j— ) { 
    $tmp = $arr[$j+1]; 
    if($tmp < $arr[$j]) { 
     $arr[$j+1] = $arr[$j]; 
     $arr[$j] = $tmp; 
    }else{ 
     break; 
    }      
   }  
  } 
 }  
 return $arr; 
}

2、冒泡排序

/* 
 冒泡排序,冒泡排序思想:进行 n-1 趟冒泡排序, 每趟两两比较调整最大值到数组(子数组)末尾 
*/ 
function bubbleSort($arr) { 
 $len = count($arr); 
 for($i = 1; $i < $len; $i++) { 
  for($j = 0; $j < $len–$i; $j++) { 
   if($arr[$j] > $arr[$j+1]) { 
    $tmp = $arr[$j+1]; 
    $arr[$j+1] = $arr[$j]; 
    $arr[$j] = $tmp; 
   } 
  } 
 } 
 return $arr; 
}

3、简单选择排序

/* 
 简单选择排序, 简单排序思想:从数组第一个元素开始依次确定从小到大的元素 
*/ 
function selectSort($arr) { 
 $len = count($arr); 
 for($i = 0; $i < $len; $i++) { 
  $k = $i; 
  for($j = $i+1; $j < $len; $j++) { 
   if($arr[$k] > $arr[$j]) { 
    $k = $j; 
   } 
  } 
  if($k != $i) { 
   $tmp = $arr[$i]; 
   $arr[$i] = $arr[$k]; 
   $arr[$k] = $tmp; 
  } 
 } 
 return $arr; 
}

4、希尔排序

/* 
 希尔排序,希尔排序原理:将数组按指定步长分隔成若干子序列,然后分别对子序列进行排序(在这是直接) 
*/ 
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; 
}

5、快速排序

/* 
 * 快速排序,快排思想:通过一趟排序将待排的记录分为两个独立的部分,其中一部分的记录的关键字均不大于 
 * 另一部分记录的关键字,然后再分别对这两部分记录继续进行快速排序,以达到整个序列有序,具体做法需要 
 * 每趟排序设置一个标准关键字和分别指向头一个记录的关键字和最后一个记录的关键字的指针。 
 * quickSort($arr, 0, count($arr) -1); 
 */ 
function quickSort(&$arr,$low,$high) { 
 if($low < $high) { 
  $i = $low; 
  $j = $high; 
  $primary = $arr[$low]; 
  while($i < $j) { 
   while($i < $j && $arr[$j] >= $primary) { 
    $j–; 
   } 
   if($i < $j) { 
    $arr[$i++] = $arr[$j]; 
   } 
   while($i < $j && $arr[$i] <= $primary) { 
    $i++; 
   } 
   if($i < $j) { 
    $arr[$j–] = $arr[$i]; 
   } 
  } 
  $arr[$i] = $primary; 
  quickSort($arr, $low, $i-1); 
  quickSort($arr, $i+1, $high); 
 } 
}

6、堆排序

/* 
 堆排序 
*/ 
 
// 调整子堆的为大根堆的过程,$s为子堆的根的位置,$m为堆最后一个元素位置 
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; 
}

7、归并排序

/* 
 归并排序,这里实现的是两路归并 
*/ 
// 分别将有序的$arr1[s..m]、$arr2[m+1..n]归并为有序的$arr2[s..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; 
}

使用经验


若排序的记录数目n较小时,可以采用直接插入排序和简单选择排序,当记录本身信息量较大时,用简单选择排序方法较好。


若待排序记录按关键字基本有序,适合采用直接插入排序和冒泡排序。


若n值较大时,可以采用快速排序、堆排序和归并排序,另外快速排序被认为是内部排序方法中最好的方法。


(责任编辑:GM源码之家)

转载请注明来源:https://www.gmyuanma.com/jsjc/5696.html

相关文章
会员头像
说点什么吧
  • 全部评论(0
    还没有评论,快来抢沙发吧!

郑重声明:
本站所有内容均由互联网收集整理、网友上传,并且以计算机技术研究交流为目的,仅供大家参考、学习,不存在任何商业目的与商业用途。 若您需要商业运营或用于其他商业活动,请您购买正版授权并合法使用。
我们不承担任何技术及版权问题,且不对任何资源负法律责任。
如无法下载,联系站长索要。
如有侵犯您的版权,请及时【联系我们】我们尽快处理。