這篇文章主要為大家詳細(xì)介紹了JS及PHP代碼編寫八大排序算法的相關(guān)資料，感興趣的小伙伴們可以參考一下

從學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)開始就接觸各種算法基礎(chǔ)，但是自從應(yīng)付完考試之后就再也沒有練習(xí)過，當(dāng)在開發(fā)的時(shí)候也是什么時(shí)候使用什么時(shí)候去查一下，現(xiàn)在在學(xué)習(xí)JavaScript，趁這個(gè)時(shí)間再把各種基礎(chǔ)算法整理一遍，分別以JS和PHP語法的方式編寫代碼。

1.冒泡排序

原理：臨近的數(shù)字兩兩進(jìn)行比較,按照從小到大或者從大到小的順序進(jìn)行交換,這樣一趟過去后,最大或最小的數(shù)字被交換到了最后一位,然后再從頭開始進(jìn)行兩兩比較交換,直到倒數(shù)第二位時(shí)結(jié)束

時(shí)間復(fù)雜度：平均情況：O（n2）  最好情況：O（n） 最壞情況：O（n2）

空間復(fù)雜度：O（1）

穩(wěn)定性：穩(wěn)定

//JavaScript語法

 var array = [23,0,32,45,56,75,43,0,34];

 for(var i = 0; i < array.length; i++)

 {

  var isSort = true;

  for(var j = 0; j < array.length - 1 - i; j++)

  {

  if(array[j] > array[j+1])

  {

   isSort = false;

   var temp = array[j];

   array[j] = array[j + 1];

   array[j + 1] = temp;

  }

  }

  if(isSort)

  {

  break;

  }

 }

 console.log(array);

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

<?php

 $array = [23,0,32,45,56,75,43,0,34];

 for($i = 0; $i < count($array); $i++)

 {

  $isSort = true;

  for($j = 0; $j < count($array) - 1; $j++)

  {

  if($array[$j] > $array[$j+1])

  {

   $isSort = false;

   $temp = $array[$j];

   $array[$j] = $array[$j + 1];

   $array[$j + 1] = $temp;

  }

  }

  if($isSort)

  {

  break;

  }

 }

 var_dump($array);

?>

2.簡單選擇排序

原理：通過n-i次關(guān)鍵字之間的比較,從n-i+1 個(gè)記錄中選擇關(guān)鍵字最小的記錄,并和第i(1<=i<=n)個(gè)記錄交換         簡單選擇排序的性能要略優(yōu)于冒泡排序

時(shí)間復(fù)雜度:平均情況：O（n2）  最好情況：O（n） 最壞情況：O（n2）

空間復(fù)雜度：O（1）

穩(wěn)定性：不穩(wěn)定

//JavaScript

  var array = [23,0,32,45,56,75,43,0,34];

  for(var i = 0; i < array.length - 1; i++)

  {

   var pos = i;

   for(var j = i + 1; j < array.length;j++)

   {

    if(array[j] < array[pos])

    {

     pos=j;

    }

   }

   var temp=array[i];

   array[i]=array[pos];

   array[pos]=temp;

  }

  console.log(array);

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

<?php

  $array = [23,0,32,45,56,75,43,0,34];

  for($i = 0; $i < count($array); $i++)

 {

  $pos = $i;

  for($j = $i + 1;$j < count($array); $j++)

  {

   if($array[$j] < $array[$pos])

   {

    $pos = $j;

   }

  }

  $temp = $array[$i];

  $array[$i] = $array[$pos];

  $array[$pos] = $temp;

 }

 var_dump($array);

?>

3.直接插入排序

原理：將一個(gè)記錄插入到已排序好的有序表中，從而得到一個(gè)新，記錄數(shù)增1的有序表。即：先將序列的第1個(gè)記錄看成是一個(gè)有序的子序列，然后從第2個(gè)記錄逐個(gè)進(jìn)行插入，直至整個(gè)序列有序?yàn)橹埂?            比冒泡法和選擇排序的性能要更好一些

時(shí)間復(fù)雜度：平均情況：O（n2）  最好情況：O（n） 最壞情況：O（n2）

空間復(fù)雜度：O（1）

穩(wěn)定性：穩(wěn)定

//JavaScript

  var array = [23,0,32,45,56,75,43,0,34];

  for(var j = 0;j < array.length;j++) {

   var key = array[j];

   var i = j - 1;

   while (i > -1 && array[i] > key)

   {

    array[i + 1] = array[i];

    i = i - 1;

   }

   array[i + 1] = key;

  }

  console.log(array);

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

<?php

 //直接插入排序

  $array = [23,0,32,45,56,75,43,0,34];

  for($i = 0; $i < count($array); $i++)

 {

  $key = $array[$i];

  $j= $i - 1;

  while($j > -1 && $array[$j] > $key)

  {

   $array[$j +1] = $array[$j];

   $j = $j - 1;

  }

  $array[$j + 1] = $key;

 }

 var_dump($array);

?>

4.快速排序

原理：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

時(shí)間復(fù)雜度:平均情況：O（nlog2n）  最好情況：O（nlog2n） 最壞情況：O（n2）

空間復(fù)雜度：O（nlog2n）

穩(wěn)定性：不穩(wěn)定

//JavaScript 快速排序

    var array = [23,0,32,45,56,75,43,0,34];

    var quickSort = function(arr) {

      if (arr.length <= 1) { return arr; }//檢查數(shù)組的元素個(gè)數(shù)，如果小于等于1，就返回。

      var pivotIndex = Math.floor(arr.length / 2);//

      var pivot = arr.splice(pivotIndex,1)[0];//選擇"基準(zhǔn)"（pivot），并將其與原數(shù)組分離，

      var left = [];//定義兩個(gè)空數(shù)組，用來存放一左一右的兩個(gè)子集

      var right = [];

      for (var i = 0; i < arr.length; i++)//遍歷數(shù)組，小于"基準(zhǔn)"的元素放入左邊的子集，大于基準(zhǔn)的元素放入右邊的子集。

      {

        if (arr[i] < pivot) {

          left.push(arr[i]);

        } else {

          right.push(arr[i]);

        }

      }

      return quickSort(left).concat([pivot], quickSort(right));//使用遞歸不斷重復(fù)這個(gè)過程，就可以得到排序后的數(shù)組。

    };

    var newArray=quickSort(array);

    console.log(newArray);

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

<?php

        $array = [23,0,32,45,56,75,43,0,34];

    function quick_sort($arr) {

      //先判斷是否需要繼續(xù)進(jìn)行

      $length = count($arr);

      if($length <= 1) {

        return $arr;

      }

      $base_num = $arr[0];//選擇一個(gè)標(biāo)尺 選擇第一個(gè)元素

      //初始化兩個(gè)數(shù)組

      $left_array = array();//小于標(biāo)尺的

      $right_array = array();//大于標(biāo)尺的

      for($i=1; $i<$length; $i++) {      //遍歷 除了標(biāo)尺外的所有元素，按照大小關(guān)系放入兩個(gè)數(shù)組內(nèi)

        if($base_num > $arr[$i]) {

          //放入左邊數(shù)組

          $left_array[] = $arr[$i];

        } else {

          //放入右邊

          $right_array[] = $arr[$i];

        }

      }

      //再分別對 左邊 和 右邊的數(shù)組進(jìn)行相同的排序處理方式

      //遞歸調(diào)用這個(gè)函數(shù),并記錄結(jié)果

      $left_array = quick_sort($left_array);

      $right_array = quick_sort($right_array);

      //合并左邊 標(biāo)尺 右邊

      return array_merge($left_array, array($base_num), $right_array);

    }

        $newArray=quick_sort($array);

        var_dump($newArray);

?>

5.希爾排序　　

原理：先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對全體記錄進(jìn)行依次直接插入排序。。

時(shí)間復(fù)雜度:平均情況：O(n√n)  最好情況：O（nlog2n） 最壞情況：O（n2）

空間復(fù)雜度：O（1）

穩(wěn)定性：不穩(wěn)定 

//JavaScript 希爾排序

    var array = [23,0,32,45,56,75,43,0,34];

    var shellSort = function (arr)

    {

      var length=arr.length;

      var h=1;

      while(h<length/3)

      {

        h=3*h+1;//設(shè)置間隔

      }

      while(h>=1)

      {

        for(var i=h; i<length; i++)

        {

          for(var j=i; j>=h && arr[j]<arr[j-h]; j-=h)

          {

            var temp =arr[j-h];

            arr[j-h]=arr[j];

            arr[j]=temp;

          }

        }

        h=(h-1)/3;

      }

      return arr;

    }

    var newArray = shellSort(array);

    console.log(newArray);

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

<?php

//希爾排序

    $array = [23,0,32,45,56,75,43,0,34];

    function shellSort($arr)

    {

      $length=count($arr);

      $h=1;

      while($h<$length/3)

      {

        $h=3*$h+1;//設(shè)置間隔

      }

      while($h>=1)

      {

        for($i=$h; $i<$length; $i++)

        {

          for($j=$i; $j>=$h && $arr[$j]<$arr[$j-$h]; $j-=$h)

          {

             $temp =$arr[$j-$h];

             $arr[$j-$h]=$arr[$j];

             $arr[$j]=$temp;

          }

        }

        $h=($h-1)/3;

      }

      return $arr;

    }

    $newArray = shellSort($array);

    var_dump($newArray)

?>

6.歸并排序

原理：假設(shè)初始序列含有n個(gè)記錄,則可以看成n個(gè)有序的子序列,每個(gè)子序列的長度為1,然后兩兩歸并,得到(不小于n/2的最小整數(shù))個(gè)長度為2或1的有序子序列,再兩兩歸并,...如此重復(fù),直至得到一個(gè)長度為n的有序序列為止　　　

時(shí)間復(fù)雜度:平均情況：O(nlog2n)  最好情況：O（nlog2n） 最壞情況：O（nlog2n）

空間復(fù)雜度：O（1）

穩(wěn)定性：穩(wěn)定 

//JavaScript 歸并排序

    function isArray1(arr){

      if(Object.prototype.toString.call(arr) =='[object Array]'){

        return true;

      }else{

        return false;

      }

    }

    function merge(left,right){

      var result=[];

      if(!isArray1(left)){

        left = [left];

      }

      if(!isArray1(right)){

        right = [right];

      }

      while(left.length > 0&& right.length >0){

        if(left[0]<right[0]){

          result.push(left.shift());

        }else{

          result.push(right.shift());

        }

      }

      return result.concat(left).concat(right);

    }

    function mergeSort(arr){

      var len=arr.length;

      var lim ,work=[];

      var i,j,k;

      if(len ==1){

        return arr;

      }

      for(i=0;i<len;i++){

        work.push(arr[i]);

      }

      work.push([]);

      for(lim=len;lim>1;){//lim為分組長度

        for(j=0,k=0;k<lim;j++,k=k+2){

          work[j]=merge(work[k],work[k+1]);

        }

        work[j]=[];

        lim=Math.floor((lim+1)/2);

      }

      return work[0];

    }

    var array = [23,0,32,45,56,75,43,0,34];

    console.log(mergeSort(array));

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

<?php 

   //歸并排序

    function mergeSort(&$arr) {

      $len = count($arr);//求得數(shù)組長度

      mSort($arr, 0, $len-1);

    }

    //實(shí)際實(shí)現(xiàn)歸并排序的程序

    function mSort(&$arr, $left, $right) {

      if($left < $right) {

        //說明子序列內(nèi)存在多余1個(gè)的元素，那么需要拆分，分別排序，合并

        //計(jì)算拆分的位置，長度/2 去整

        $center = floor(($left+$right) / 2);

        //遞歸調(diào)用對左邊進(jìn)行再次排序：

        mSort($arr, $left, $center);

        //遞歸調(diào)用對右邊進(jìn)行再次排序

        mSort($arr, $center+1, $right);

        //合并排序結(jié)果

        mergeArray($arr, $left, $center, $right);

      }

    }

    //將兩個(gè)有序數(shù)組合并成一個(gè)有序數(shù)組

    function mergeArray(&$arr, $left, $center, $right) {

      //設(shè)置兩個(gè)起始位置標(biāo)記

      $a_i = $left;

      $b_i = $center+1;

      while($a_i<=$center && $b_i<=$right) {

        //當(dāng)數(shù)組A和數(shù)組B都沒有越界時(shí)

        if($arr[$a_i] < $arr[$b_i]) {

          $temp[] = $arr[$a_i++];

        } else {

          $temp[] = $arr[$b_i++];

        }

      }

      //判斷 數(shù)組A內(nèi)的元素是否都用完了，沒有的話將其全部插入到C數(shù)組內(nèi)：

      while($a_i <= $center) {

        $temp[] = $arr[$a_i++];

      }

      //判斷 數(shù)組B內(nèi)的元素是否都用完了，沒有的話將其全部插入到C數(shù)組內(nèi)：

      while($b_i <= $right) {

        $temp[] = $arr[$b_i++];

      }

      //將$arrC內(nèi)排序好的部分，寫入到$arr內(nèi)：

      for($i=0, $len=count($temp); $i<$len; $i++) {

        $arr[$left+$i] = $temp[$i];

      }

    }

    $arr = array(23,0,32,45,56,75,43,0,34);

    mergeSort($arr);

    var_dump($arr);

?>

7.堆排序

原理：堆排序就是利用堆進(jìn)行排序的方法.基本思想是:將待排序的序列構(gòu)造成一個(gè)大頂堆.此時(shí),整個(gè)序列的最大值就是堆頂 的根結(jié)點(diǎn).將它移走(其實(shí)就是將其與堆數(shù)組的末尾元素交換, 此時(shí)末尾元素就是最大值),然后將剩余的n-1個(gè)序列重新構(gòu)造成一個(gè)堆,這樣就會得到n個(gè)元素的次大值.如此反復(fù)執(zhí)行,便能得到一個(gè)有序序列了

時(shí)間復(fù)雜度：平均情況：O(nlog2n)  最好情況：O（nlog2n） 最壞情況：O（nlog2n）

空間復(fù)雜度：O（1）

穩(wěn)定性：不穩(wěn)定 

//JavaScript 堆排序  

   var array = [23,0,32,45,56,75,43,0,34];

   function heapSort(array)

   {

     for (var i = Math.floor(array.length / 2); i >= 0; i--)

     {

       heapAdjust(array, i, array.length - 1); //將數(shù)組array構(gòu)建成一個(gè)大頂堆

     }

     for (i = array.length - 1; i >= 0; i--)

     {

       /*把根節(jié)點(diǎn)交換出去*/

       var temp = array[i];

       array[i] = array[0];

       array[0] = temp;

       /*余下的數(shù)組繼續(xù)構(gòu)建成大頂堆*/

       heapAdjust(array, 0, i - 1);

     }

     return array;

   }

   function heapAdjust(array, start, max)

   {

     var temp = array[start];//temp是根節(jié)點(diǎn)的值

     for (var j = 2 * start; j < max; j *= 2)

     {

       if (j < max && array[j] < array[j + 1])

       { //取得較大孩子的下標(biāo)

         ++j;

       }

       if (temp >= array[j])

         break;

       array[start] = array[j];

       start = j;

     }

     array[start] = temp;

   }

   var newArray = heapSort(array);

   console.log(newArray);

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

<?php

  //堆排序

  function heapSort(&$arr) {

    #初始化大頂堆

    initHeap($arr, 0, count($arr) - 1);

    #開始交換首尾節(jié)點(diǎn),并每次減少一個(gè)末尾節(jié)點(diǎn)再調(diào)整堆,直到剩下一個(gè)元素

    for($end = count($arr) - 1; $end > 0; $end--) {

      $temp = $arr[0];

      $arr[0] = $arr[$end];

      $arr[$end] = $temp;

      ajustNodes($arr, 0, $end - 1);

    }

  }

  #初始化最大堆,從最后一個(gè)非葉子節(jié)點(diǎn)開始,最后一個(gè)非葉子節(jié)點(diǎn)編號為 數(shù)組長度/2 向下取整

  function initHeap(&$arr) {

    $len = count($arr);

    for($start = floor($len / 2) - 1; $start >= 0; $start--) {

      ajustNodes($arr, $start, $len - 1);

    }

  }

  #調(diào)整節(jié)點(diǎn)

  #@param $arr  待調(diào)整數(shù)組

  #@param $start  調(diào)整的父節(jié)點(diǎn)坐標(biāo)

  #@param $end  待調(diào)整數(shù)組結(jié)束節(jié)點(diǎn)坐標(biāo)

  function ajustNodes(&$arr, $start, $end) {

    $maxInx = $start;

    $len = $end + 1;  #待調(diào)整部分長度

    $leftChildInx = ($start + 1) * 2 - 1;  #左孩子坐標(biāo)

    $rightChildInx = ($start + 1) * 2;  #右孩子坐標(biāo)

    #如果待調(diào)整部分有左孩子

    if($leftChildInx + 1 <= $len) {

      #獲取最小節(jié)點(diǎn)坐標(biāo)

      if($arr[$maxInx] < $arr[$leftChildInx]) {

        $maxInx = $leftChildInx;

      }

      #如果待調(diào)整部分有右子節(jié)點(diǎn)

      if($rightChildInx + 1 <= $len) {

        if($arr[$maxInx] < $arr[$rightChildInx]) {

          $maxInx = $rightChildInx;

        }

      }

    }

    #交換父節(jié)點(diǎn)和最大節(jié)點(diǎn)

    if($start != $maxInx) {

      $temp = $arr[$start];

      $arr[$start] = $arr[$maxInx];

      $arr[$maxInx] = $temp;

      #如果交換后的子節(jié)點(diǎn)還有子節(jié)點(diǎn),繼續(xù)調(diào)整

      if(($maxInx + 1) * 2 <= $len) {

        ajustNodes($arr, $maxInx, $end);

      }

    }

  }

  $arr = array(23,0,32,45,56,75,43,0,34);

  heapSort($arr);

  var_dump($arr);

?>

8.基數(shù)排序

原理：將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個(gè)位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。　　

時(shí)間復(fù)雜度：平均情況：O(d(r+n))  最好情況：O（d(n+rd)） 最壞情況：O（d(r+n)）   r:關(guān)鍵字的基數(shù)   d:長度  n:關(guān)鍵字個(gè)數(shù)

空間復(fù)雜度：O（rd+n）

穩(wěn)定性：穩(wěn)定 

<?php

   #基數(shù)排序,此處僅對正整數(shù)進(jìn)行排序，至于負(fù)數(shù)和浮點(diǎn)數(shù)，需要用到補(bǔ)碼，各位有興趣自行研究

   #計(jì)數(shù)排序

   #@param $arr 待排序數(shù)組

   #@param $digit_num 根據(jù)第幾位數(shù)進(jìn)行排序

   function counting_sort(&$arr, $digit_num = false) {

     if ($digit_num !== false) { #如果參數(shù)$digit_num不為空，則根據(jù)元素的第$digit_num位數(shù)進(jìn)行排序

       for ($i = 0; $i < count($arr); $i++) {

         $arr_temp[$i] = get_specific_digit($arr[$i], $digit_num);

       } 

     } else {

       $arr_temp = $arr;

     }

     $max = max($arr);

     $time_arr = array(); #儲存元素出現(xiàn)次數(shù)的數(shù)組

     #初始化出現(xiàn)次數(shù)數(shù)組

     for ($i = 0; $i <= $max; $i++) {

       $time_arr[$i] = 0;

     }

     #統(tǒng)計(jì)每個(gè)元素出現(xiàn)次數(shù)

     for ($i = 0; $i < count($arr_temp); $i++) {

       $time_arr[$arr_temp[$i]]++;

     }

     #統(tǒng)計(jì)每個(gè)元素比其小或相等的元素出現(xiàn)次數(shù)

     for ($i = 0; $i < count($time_arr) - 1; $i++) {

       $time_arr[$i + 1] += $time_arr[$i];

     }

     #利用出現(xiàn)次數(shù)對數(shù)組進(jìn)行排序

     for($i = count($arr) - 1; $i >= 0; $i--) {

       $sorted_arr[$time_arr[$arr_temp[$i]] - 1] = $arr[$i];

       $time_arr[$arr_temp[$i]]--;

     }

     $arr = $sorted_arr;

     ksort($arr);  #忽略這次對key排序的效率損耗

   }

   #計(jì)算某個(gè)數(shù)的位數(shù)

   function get_digit($number) {

     $i = 1;

     while ($number >= pow(10, $i)) {

      $i++;

     }

     return $i;

   }

   #獲取某個(gè)數(shù)字的從個(gè)位算起的第i位數(shù)

   function get_specific_digit($num, $i) {

     if ($num < pow(10, $i - 1)) {

       return 0;

     }

     return floor($num % pow(10, $i) / pow(10, $i - 1));

   }

   #基數(shù)排序,以計(jì)數(shù)排序作為子排序過程

   function radix_sort(&$arr) {

     #先求出數(shù)組中最大的位數(shù)

     $max = max($arr);

     $max_digit = get_digit($max);

     for ($i = 1; $i <= $max_digit; $i++) {

       counting_sort($arr, $i);

     }  

   }

   $arr = array(23,0,32,45,56,75,43,0,34);

   radix_sort($arr);

   var_dump($arr);

?>

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助