程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 網頁編程 >> PHP編程 >> PHP綜合 >> PHP簡單選擇排序算法實例

PHP簡單選擇排序算法實例

編輯:PHP綜合

簡單的選擇排序算法:通過n-i次關鍵字間的比較,從n-i+1個記錄中選出關鍵字最小的記錄,並和第i(1<=i<=n)個記錄交換

復制代碼 代碼如下:
<?php
    class Sort{
        /**
         * 簡單的選擇排序
         *
         * @param unknown_type $arr
         */
        public function selectSort(&$arr) {
            $len=count($arr);
            for ($i=0;$i<$len;$i++) {
                $min=$i;
                for ($j=$i+1;$j<=$len-1;$j++) {
                    if ($arr[$min]>$arr[$j]) {//如果找到比$arr[$min]較小的值,則將該下標賦給$min
                        $min=$j;
                    }
                }
                if ($min!=$i){//若$min不等於$i,說明找到了最小值,則交換
                    $this->swap($arr[$i],$arr[$min]);
                }
            }
        }
        /**
         * 將$a和$b兩個值進行位置交換
         */
        public function swap(&$a,&$b) {
            $temp=$a;
            $a=$b;
            $b=$temp;
        }
    }
    $arr=array(4,6,1,2,9,8,7,3,5);
    $test=new Sort();
    $test->selectSort($arr);//簡單的選擇排序
//    var_dump($arr);
?>

簡單選擇排序的特點:交換移動數據次數相當少,從而節約了相應的時間
簡單選擇排序的時間復雜度分析:
無論最好最差的情況,其比較次數都是一樣多,第i趟排序需要進行n-i次關鍵字的比較,此時需要比較n(n-1)/2次。所以最終的時間復雜度是O(n^2)
盡管與冒泡排序同為O(n^2),但選擇排序的性能還是略優於冒泡排序的。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved