算法基本和常見排序算法有哪些

本篇內(nèi)容主要講解“算法基本和常見排序算法有哪些”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“算法基本和常見排序算法有哪些”吧!

創(chuàng)新互聯(lián)建站服務(wù)項目包括城關(guān)網(wǎng)站建設(shè)、城關(guān)網(wǎng)站制作、城關(guān)網(wǎng)頁制作以及城關(guān)網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，城關(guān)網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到城關(guān)省份的部分城市，未來相信會繼續(xù)擴大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

算法基本和7大常見排序算法

算法5大特征
有窮，確切，輸入項，輸出項，可行性
時間復(fù)雜度:執(zhí)行算法所需要的計算工作量,一般來說，計算機算法是問題規(guī)模n的函數(shù)f(n),算法的時間復(fù)雜度因此記做 T(n)=O(f(n))
問題的規(guī)模越大，算法執(zhí)行的時間的增長率與f(n) 的增長率正相關(guān)，稱作漸進時間復(fù)雜度(Asympotic Time Complexity)

計算方式：

1.計算次數(shù)公式
 1+2+3+.......+n;

<?php$sum=0;for($i=1;$i<=$n;$i++){
sum+=$i;
}?>

計算n次，時間復(fù)雜度為O(n)
2.用常數(shù)1來取代所有時間中所有加法常數(shù) 比如O(3) 記做O(1)

<?phpfunction test($n){echo $n;echo $n;echo $n;
}?>

O(3) 記做O(1)
3.在修改后的運算次數(shù)函數(shù)中，只保留最高階項
   n^2+n+1 則記做O(n^2)
4.如果最高階存在且不是1，則去除與這個項相乘的常數(shù)
  2n^2+3n+1 記做O(n^2)

常數(shù)階:O(1)
  線性階:O(n)
  平(立)方階:O(n^2),O(n^3)

<?php$sum=0;for($i=1;$i<=$n;$i++){for($j=1;$j<=$n;$j++){$sum+=$j;
}
}?>

兩層循環(huán) O(n^2) 三層O(n^3)
  特殊平方階:O(n^2/2+n/2)-> O(n^2)

for(){for(){

}
}for(){

}echo $a+$b;

n^2+n+1->O(n^2)

算法基本和常見排序算法有哪些

最壞情況:最壞情況下的運行時間,一種保證,如果沒特殊說明,說的時間復(fù)雜度即為最壞情況下的時間復(fù)雜度

平均情況:期望的運行時間三門峽婦科醫(yī)院http://www.smxrlyy.com/

空間復(fù)雜度:算法需要消耗的內(nèi)存空間,記作S(n)=O(f(n))

包括程序代碼所占用的空間,

輸入數(shù)據(jù)所占用的空間和

輔助變量所占用的空間

這3個方面

計算和表示方法與時間復(fù)雜度類似,一般用復(fù)雜度的漸進性表示

-------------------

排序算法及其時間復(fù)雜度空間復(fù)雜度

1.冒泡排序

function BubbleSort($arr)
{    $len = count($arr);    while ($len > 1) {        $changed = false;        for ($i = 0; $i < $len - 1; $i++) {            if ($arr[$i] > $arr[$i + 1]) {                $tmp = $arr[$i];                $arr[$i] = $arr[$i + 1];                $arr[$i + 1] = $tmp;                $changed = true;
            }
        }        if (!$changed) {            return $arr;
        }        $len--;

    }    return $arr;
}

 內(nèi)部循環(huán)每一輪將最大的沉到尾部

時間復(fù)雜度:O(n^2),平均O(n^2)
空間復(fù)雜度:O(1)

屬于穩(wěn)定，原地排序算法

2.選擇排序

每次從待排序的序列中取出最小或者最大的元素放在序列的起始位置，直到待排序的數(shù)據(jù)元素排完

<?php$arr=[8,7,6,4,3,10,1,-1];$len=count($arr);for($i=0;$i<$len;$i++){    $min_key=$i;    for($j=$i+1;$j<$len;$j++){        if($arr[$j]<$arr[$min_key]){            $min_key=$j;
        }
    }    if($min_key!=$i){        $tmp=$arr[$i];        $arr[$i]=$arr[$min_key];        $arr[$min_key]=$tmp;
    } 
}?>

比較時間:T = （n-1)+ (n -2)+(n - 3).... + 1; ===>> T = [n*(n-1) ] / 2；
交換時間:最好的情況全部元素已經(jīng)有序，則 交換次數(shù)為0,最差的情況，全部元素逆序，就要交換 n-1 次
所以最優(yōu)的時間復(fù)雜度 和最差的時間復(fù)雜度 和平均時間復(fù)雜度  都為:O(n^2)
空間復(fù)雜度:O(1)

3.快速排序

選擇一個基數(shù)，通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的2部分，一部分比這個基數(shù)都要小，一部分比這個基數(shù)都要大，然后按照此方法再去處理這2部分

時間復(fù)雜度:最差 O(n^2) ,平均 O(nlogn)

空間復(fù)雜度:最差O(n),平均 O(logn)

<?phpfunction quick_sort(&$s, $l, $r)
{    if ($l < $r)
    {        //Swap(s[$l], s[($l + r) / 2]); //將中間的這個數(shù)和第一個數(shù)交換 參見注1
        $i = $l; $j = $r; $x = $s[$l];        while ($i < $j)
        {            while($i < $j && $s[$j] >= $x) // 從右向左找第一個小于x的數(shù)
                $j--;            if($i < $j)                $s[$i++] = $s[$j];            while($i < $j && $s[$i] <$x) // 從左向右找第一個大于等于x的數(shù)
                $i++;            if($i < $j)                $s[$j--] = $s[$i];
        }        $s[$i] = $x;
        quick_sort($s, $l, $i - 1); // 遞歸調(diào)用
        quick_sort($s, $i + 1, $r);
    }
}$arr=array(6,1,2,7,9,3,4,5,10,8);print_r($arr);
quick_sort($arr,0,count($arr)-1);print_r($arr);

或者借用php函數(shù)

<?php    //待排序數(shù)組
    $arr=array(6,3,8,7,4,2,5,1,0,-3,-1);    //函數(shù)實現(xiàn)快速排序
    function quick_sort($arr)
    {        //判斷參數(shù)是否是一個數(shù)組
        if(!is_array($arr)) return false;        //遞歸出口:數(shù)組長度為1，直接返回數(shù)組
        $length=count($arr);        if($length<=1) return $arr;        //數(shù)組元素有多個,則定義兩個空數(shù)組
        $left=$right=array();        //使用for循環(huán)進行遍歷，把第一個元素當(dāng)做比較的對象
        for($i=1;$i<$length;$i++)
        {            //判斷當(dāng)前元素的大小
            if($arr[$i]<$arr[0]){                $left[]=$arr[$i];
            }else{                $right[]=$arr[$i];
            }
        }        //遞歸調(diào)用
        $left=quick_sort($left);        $right=quick_sort($right);        //將所有的結(jié)果合并
        return array_merge($left,array($arr[0]),$right);
    }    //調(diào)用
    echo "";    print_r(quick_sort($arr));    ?>

 4.插入排序

將一組數(shù)據(jù)分成兩組，分別將其稱為有序組與待插入組；
每次從待插入組中取出一個元素，與有序組的元素進行比較，并找到合適的位置，將該元素插到有序組當(dāng)中
就這樣，每次插入一個元素，有序組增加，待插入組減少
直到待插入組元素個數(shù)為0,當(dāng)然，插入過程中涉及到了元素的交換

   時間復(fù)雜度:O (n^2) ,空間復(fù)雜度:O(1)

$arr=[6,1,7,8,12,0,20,-1,3,9,-11,9,8,0,6];function insertsort(&$arr){    $len=count($arr);    for($i=1;$i<$len;$i++){        $tmp=$arr[$i];        $j=$i;        while($j>0 && $tmp<$arr[$j-1]){            $arr[$j]=$arr[$j-1];//若不是合適位置，有序組元素向后移動
            $j--;

        }        $arr[$j]=$tmp;//找到合適位置，將元素插入    }

}echo "";print_r($arr);
insertsort($arr);print_r($arr);

參考：http://blog.csdn.net/llzk_/article/details/51628574

 5.希爾排序

希爾排序也是一種插入排序,它是簡單插入排序經(jīng)過改進之后的一個更高效的版本,也稱為縮小增量排序,同時該算法是沖破O(n^2）的第一批算法之一
大致思路:先比較距離遠的元素,而不是像簡單交換排序算法那樣先比較相鄰的元素，這樣可以快速減少大量的無序情況，
從而減輕后續(xù)的工作,被比較的元素之間的距離逐步減少,直到減少為1，這時的排序變成了相鄰元素的互換

排序中對于增量序列的選擇十分重要，直接影響到希爾排序的性能

時間復(fù)雜度 O(N^2)

function shellsort(&$arr){    $len=count($arr);    for($gap=intval($len/2);$gap>0;$gap=intval($gap/2)){        for($i=$gap;$i<$len;$i++){            $j=$i;            while($j-$gap>=0 && $arr[$j]<$arr[$j-$gap]){                //交換法
                $tmp=$arr[$j];                $arr[$j]=$arr[$j-$gap];                $arr[$j-$gap]=$tmp;                $j-=$gap;
            }
        }

    }
}function shellsort1(&$arr){    $len=count($arr);    for($gap=intval($len/2);$gap>0;$gap=intval($gap/2)){        for($i=$gap;$i<$len;$i++){            $j=$i;            $tmp=$arr[$j];            if($arr[$j]<$arr[$j-$gap]){                while($j-$gap>=0 && $arr[$j] <$arr[$j-$gap]){                    //移動
                    $arr[$j]=$arr[$j-$gap];                    $j-=$gap;
                }                $arr[$j]=$tmp;
            }
        }
    }
}$arr=[3,2,-1,0,5,2,1,7,6,4];echo "";print_r($arr);
shellsort1($arr);print_r($arr);

 可參考:https://www.cnblogs.com/chengxiao/p/6104371.html

6.歸并排序

function mergeSort(&$arr,$l,$r){    if($l>=$r) return;    $mid=intval(($l+$r)/2);
    mergeSort($arr,$l,$mid);
    mergeSort($arr,$mid+1,$r);
    _merge($arr,$l,$mid,$r);

}//對$arr[$l,$mid] ,arr[$mid+1,$r] 排序，對于元素少的時候可以采用插入排序優(yōu)化function _merge(&$arr,$l,$mid,$r){    if($l>=$r) return;    $tmp=[];    $i=$l;    $j=$mid+1;    while($i<=$mid && $j<=$r){        if($arr[$i] <$arr[$j]){            $tmp[]=$arr[$i];            $i++;
        }else{            $tmp[]=$arr[$j];            $j++;
        }
    }    while($i<=$mid){        $tmp[]=$arr[$i];        $i++;
    }    while($j<=$r){        $tmp[]=$arr[$j];        $j++;
    }    foreach($tmp as $k=>$v){       $arr[$l++]=$v;
    }

}

到此，相信大家對“算法基本和常見排序算法有哪些”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

新聞標(biāo)題：算法基本和常見排序算法有哪些
文章來源：http://muchs.cn/article2/picgic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、定制網(wǎng)站、動態(tài)網(wǎng)站、外貿(mào)建站、網(wǎng)站導(dǎo)航、品牌網(wǎng)站設(shè)計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

營銷型網(wǎng)站建設(shè)