communauté Apprendre Bibliothèque d'outils Loisirs
recherche
Français
Maison > développement back-end > tutoriel php > php快速排序三种方法

php快速排序三种方法

WBOY
Libérer： 2016-07-25 08:53:52
original
1071 Les gens l'ont consulté
  2. function quick_sort($array) {
  3. if(count($array) $key = $array[0];
  4. $rightArray = array();
  5. $leftArray = array();
  6. for($i = 1; $i if($array[$i] >= $key) {
  7. $rightArray[] = $array[$i];
  8. } else {
  9. $leftArray[] = $array[$i];
  10. }
  11. }
  12. $leftArray = quick_sort($leftArray);
  13. $rightArray = quick_sort($rightArray);
  14. return array_merge($leftArray, array($key), $rightArray);
  15. }
复制代码

方法二：该算法来自算法导论，叫作Nico Lomuto方法（感兴趣goole上有详细说明）使用最经典的单方向一次遍历找到中值。 但这种算法在最坏情况下（例如值相同的数组，需要n-1次划分，每一次划分需要O(n) 时间去掉一个元素）最坏情况下为O(n*n)。 代码：

  2. function quick_sort(&$array, $start, $end) {
  3. if ($start >= $end) return;
  4. $mid = $start;
  5. for ($i = $start + 1; $i if ($array[$i] $mid++;
  6. $tmp = $array[$i];
  7. $array[$i] = $array[$mid];
  8. $array[$mid] = $tmp;
  9. }
  10. }
  11. $tmp = $array[$start];
  12. $array[$start] = $array[$mid];
  13. $array[$mid] = $tmp;
  14. quick_sort($array, $start, $mid - 1);
  15. quick_sort($array, $mid + 1, $end);
  16. }
复制代码

方法三：该方法基本上是教科书式的常见写法，首先从左向右遍历小于中间元素的跳过，同时从右向左遍历遇到大的元素跳过，然后 如果没有交叉着交换两边值，继续循环，直到找到中间点。注意该方法在处理相同元素的时候，仍旧交换，这样在最坏情况下也有O(nlogn) 效率。但下面的函数中，如果将$array[$right] > $key 改成 $array[$right] >=$key 或将 $array[$left]

  2. function quick_sort_swap(&$array, $start, $end) {
  3. if($end $key = $array[$start];
  4. $left = $start;
  5. $right = $end;
  6. while($left while($left $key)
  7. $right--;
  8. $array[$left] = $array[$right];
  9. while($left $left++;
  10. $array[$right] = $array[$left];
  11. }
  12. $array[$right] = $key;
  13. quick_sort_swap(&$array, $start, $right - 1);
  14. quick_sort_swap(&$array, $right+1, $end);
  15. }
复制代码

您可能感兴趣的文章：

  • php实用快速排序算法的实例代码
  • php关联数组排序、快速排序的实例分享
  • php实现快速排序(quick sort)的函数
  • php实现快速排序的函数
  • php冒泡排序与快速排序的例子


Étiquettes associées：
php快速排序三种方法
source：php.cn
Article précédent：php字符串编码转换函数 可以自动识别原编码 Article suivant：php编码转换方法举例
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers articles par auteur
Derniers numéros
function_exists() ne peut pas déterminer la fonction personnalisée Function test () {return true;} if (function_exists ('test')) {echo "le test est une ...
Depuis 2024-04-29 11:01:01
0
3
2253
Comment afficher la version mobile de Google Chrome Bonjour professeur, comment puis-je changer Google Chrome en version mobile ?
Depuis 2024-04-23 00:22:19
0
11
2392
La fenêtre enfant exploite la fenêtre parent, mais la sortie ne répond pas. Les deux premières phrases sont exécutables, mais la dernière ne peut pas être implémentée...
Depuis 2024-04-19 15:37:47
0
1
2005
Il n'y a aucune sortie dans la fenêtre parent document.onclick = function(){ window.opener.document.write('Je suis la sortie de la fenêt...
Depuis 2024-04-18 23:52:34
0
1
1892
Où sont les didacticiels sur la cartographie mentale CSS ? Didacticiel
Depuis 2024-04-16 10:10:18
0
0
1957
Rubriques connexes
Plus>
Recommandations populaires
Tutoriels populaires
Plus>
Tutoriels associés
Recommandations populaires
Derniers cours
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal