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

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

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

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

計算方式：

1.計算次數公式
 1+2+3+.......+n;

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

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

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

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

常數階: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;
}
}?>

兩層循環 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)

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

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

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

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

輸入數據所占用的空間和

輔助變量所占用的空間

這3個方面

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

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

排序算法及其時間復雜度空間復雜度

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;
}

 內部循環每一輪將最大的沉到尾部

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

屬于穩定，原地排序算法

2.選擇排序

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

<?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；
交換時間:最好的情況全部元素已經有序，則 交換次數為0,最差的情況，全部元素逆序，就要交換 n-1 次
所以最優的時間復雜度 和最差的時間復雜度 和平均時間復雜度  都為:O(n^2)
空間復雜度:O(1)

3.快速排序

選擇一個基數，通過一趟排序將要排序的數據分割成獨立的2部分，一部分比這個基數都要小，一部分比這個基數都要大，然后按照此方法再去處理這2部分

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

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

<?phpfunction quick_sort(&$s, $l, $r)
{    if ($l < $r)
    {        //Swap(s[$l], s[($l + r) / 2]); //將中間的這個數和第一個數交換 參見注1
        $i = $l; $j = $r; $x = $s[$l];        while ($i < $j)
        {            while($i < $j && $s[$j] >= $x) // 從右向左找第一個小于x的數
                $j--;            if($i < $j)                $s[$i++] = $s[$j];            while($i < $j && $s[$i] <$x) // 從左向右找第一個大于等于x的數
                $i++;            if($i < $j)                $s[$j--] = $s[$i];
        }        $s[$i] = $x;
        quick_sort($s, $l, $i - 1); // 遞歸調用
        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函數

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

 4.插入排序

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

   時間復雜度:O (n^2) ,空間復雜度: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.希爾排序

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

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

時間復雜度 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] 排序，對于元素少的時候可以采用插入排序優化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;
    }

}

到此，相信大家對“算法基本和常見排序算法有哪些”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！