PHPソートアルゴリズムの単純選択ソート(Simple Selection Sort)インスタンス分析

1917 ワード

この例では、PHPソートアルゴリズムの簡単な選択ソート(Simple Selection Sort)について説明する.皆さんの参考にしてください.具体的には以下の通りです.
基本思想:
n−i次キーワード間の比較により、n−i+1個のレコードからキーワード最小のレコードを選択し、i(1<=i<=n)個目のレコードと交換し、n−1回実行すると記録シーケンスのソートが完了する.
アルゴリズムの実装:

 
 

実行結果:

array(9) {
 [0]=>
 int(1)
 [1]=>
 int(2)
 [2]=>
 int(3)
 [3]=>
 int(4)
 [4]=>
 int(5)
 [5]=>
 int(6)
 [6]=>
 int(7)
 [7]=>
 int(8)
 [8]=>
 int(9)
}

複雑度分析:
ソートを簡単に選択する過程で、レコードを移動する回数は比較的少ない.好ましくは、ソートされるべきレコードの初期状態が既に順配列である場合、レコードを移動する必要はない.
最悪の場合、すなわち、ソート対象レコードの初期状態が1番目のレコードで最大となり、その後のレコードが小さい順から大きい順に並べられると、レコードを移動する必要がある回数は最大3(n−1)となる.単純選択ソート中に行う比較回数は、初期状態でソートされるレコードシーケンスのソート状況とは無関係である.i=1の場合、n-1回の比較が必要である.i=2の場合、n-2回の比較が必要である.順次類推すると,共通に必要な比較回数は(n−1)+(n−2)+…+2+1=n(n−1)/2であり,すなわち比較操作を行う時間複雑度はO(n^2),移動操作を行う時間複雑度はO(n)である.
単純な選択ソートは不安定なソートです.
本文は《大話データ構造》から参考して、ここでただ記録をして、便利に後で調べて、大神は噴き出さないでください!
PS:ここでは、ソートに関するプレゼンテーションツールをお勧めします.参考にしてください.
挿入/選択/バブル/マージ/ヒル/クイックソートアルゴリズムプロセスツールをオンラインアニメーションで実証します.http://tools.jb51.net/aideddesign/paixu_ys
PHPに関する内容についてもっと兴味のある読者は、「phpソートアルゴリズム総括」、「PHPデータ构造とアルゴリズム教程」、「phpプログラム设计アルゴリズム総括」、「php文字列(string)用法総括」、「PHP配列(Array)操作技巧大全」、「PHP常用遍歴アルゴリズムと技巧総括」及び「PHP数学演算技巧総括」
ここで述べたことが皆さんのPHPプログラム設計に役立つことを願っています.