ホームページ  >  記事  >  バックエンド開発  >  PHPクイックソートの原理、実装方法、事例分析

PHPクイックソートの原理、実装方法、事例分析

墨辰丷
墨辰丷オリジナル
2018-06-02 10:00:021379ブラウズ

この記事では主にPHPクイックソートの原理と実装方法を紹介し、サンプルの形でPHPクイックソートのアルゴリズム原理と具体的な実装テクニックを分析します。

<?php
$n = array(&#39;13&#39;,&#39;14&#39;,&#39;55&#39;,&#39;10&#39;,&#39;54&#39;,&#39;2&#39;,&#39;79&#39;,&#39;106&#39;,&#39;89&#39;,&#39;90&#39;,&#39;22&#39;,&#39;60&#39;,&#39;111&#39;,&#39;77777&#39;,&#39;-110&#39;,&#39;-10&#39;,&#39;123&#39;);
function partition($n,$left,$right)
{
  global $n;
  $pivot = $n[$left];
  $lo=$left;
  $hi=$right+1;
  while($lo+1!=$hi) {
    if($n[$lo+1]<$pivot)
      $lo++;
    else if($n[$hi-1]>$pivot)
      $hi--;
    else{
      $t=$n[$lo+1];
      $n[$lo+1]=$n[$hi-1];
      $n[$hi-1]=$t;
      $lo++;
      $hi--;
    }
  }
  $n[$left]=$n[$lo];
  $n[$lo]=$pivot;
  return $lo;
}
function quicksort($n,$left,$right)
{
  global $n;
  $dp = 0;
  if ($left<$right) {
     $dp=partition($n,$left,$right);
     quicksort($n,$left,$dp-1);
     quicksort($n,$dp+1,$right);
  }
}
quicksort($n,0,sizeof($n)-1);
print_r($n);
?>

クイックソートは、バブルソートを改良したアンチリスクアルゴリズムです。その基本的な考え方は、一方向の並べ替えによって並べ替えられるデータを 2 つの独立した部分に分割し、一方の部分のすべてのデータがもう一方の部分のすべてのデータよりも小さくなり、データの 2 つの部分が順番に並べ替えられることです。迅速に並べ替えるために、並べ替えプロセス全体を再帰的に実行して、データ全体が順序付けられたシーケンスになるようにすることができます。

ソートする配列がA[1]...A[N]であるとすると、まず任意のデータ(通常は最初のデータ)をキーデータとして選択し、それより小さいすべての数値をその前に置きます。それより大きい数字がその後ろに置かれるこのプロセスは、1 桁クイックソートと呼ばれます。クイックソートのアルゴリズムは次のとおりです:

1) 2 つの変数 I と J を設定します。ソートが開始されると、I:=1、J:=N になります。

2) 最初の配列要素をキーデータとして使用し、値を Give X に割り当てます。 、つまり交換

4)、I から後方に検索、つまり前から後ろに検索 (I: =I+1)、X より大きい最初の値を見つけ、2 つを交換します

5)、ステップを繰り返します。 I=J まで 3、4 ステップ。

クイックソートはこのプロセスを再帰的に呼び出します。このデータシーケンスを 49 を中間点として分割し、前部分と後部分でそれぞれ同様のクイックソートを実行します。これにより、高速ソートが完了します。データシーケンス全体のソート ソートし、最後にこのデータシーケンスを順序付けられたシーケンスに変換します

概要: 上記がこの記事の全内容です。皆さんの学習に役立つことを願っています。

関連する推奨事項:

php

WeChat開発アクセスインスタンスの詳細説明

php

WeChat開発アクセスインスタンスの詳細説明

PHP+MySQLはファジークエリ従業員情報機能を実装します

以上がPHPクイックソートの原理、実装方法、事例分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。