這篇文章主要為大家詳細(xì)介紹了JS及PHP代碼編寫八大排序算法的相關(guān)資料，感興趣的小伙伴們可以參考一下
從學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)開始就接觸各種算法基礎(chǔ)，但是自從應(yīng)付完考試之后就再也沒有練習(xí)過，當(dāng)在開發(fā)的時候也是什么時候使用什么時候去查一下，現(xiàn)在在學(xué)習(xí)JavaScript，趁這個時間再把各種基礎(chǔ)算法整理一遍，分別以JS和PHP語法的方式編寫代碼。
1.冒泡排序
原理：臨近的數(shù)字兩兩進(jìn)行比較,按照從小到大或者從大到小的順序進(jìn)行交換,這樣一趟過去后,最大或最小的數(shù)字被交換到了最后一位,然后再從頭開始進(jìn)行兩兩比較交換,直到倒數(shù)第二位時結(jié)束
時間復(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 個記錄中選擇關(guān)鍵字最小的記錄,并和第i(1<=i<=n)個記錄交換 簡單選擇排序的性能要略優(yōu)于冒泡排序
時間復(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.直接插入排序
原理：將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數(shù)增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進(jìn)行插入，直至整個序列有序為止。 比冒泡法和選擇排序的性能要更好一些
時間復(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ù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變成有序序列。
時間復(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ù)組的元素個數(shù)，如果小于等于1，就返回。
var pivotIndex = Math.floor(arr.length / 2);//
var pivot = arr.splice(pivotIndex,1)[0];//選擇"基準(zhǔn)"（pivot），并將其與原數(shù)組分離，
var left = [];//定義兩個空數(shù)組，用來存放一左一右的兩個子集
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ù)這個過程，就可以得到排序后的數(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];//選擇一個標(biāo)尺 選擇第一個元素
//初始化兩個數(shù)組
$left_array = array();//小于標(biāo)尺的
$right_array = array();//大于標(biāo)尺的
for($i=1; $i<$length; $i++) { //遍歷 除了標(biāo)尺外的所有元素，按照大小關(guān)系放入兩個數(shù)組內(nèi)
if($base_num > $arr[$i]) {
//放入左邊數(shù)組
$left_array[] = $arr[$i];
} else {
//放入右邊
$right_array[] = $arr[$i];
}
}
//再分別對 左邊 和 右邊的數(shù)組進(jìn)行相同的排序處理方式
//遞歸調(diào)用這個函數(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.希爾排序
原理：先將整個待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進(jìn)行依次直接插入排序。。
時間復(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個記錄,則可以看成n個有序的子序列,每個子序列的長度為1,然后兩兩歸并,得到(不小于n/2的最小整數(shù))個長度為2或1的有序子序列,再兩兩歸并,...如此重復(fù),直至得到一個長度為n的有序序列為止
時間復(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);
}
//實際實現(xiàn)歸并排序的程序
function mSort(&$arr, $left, $right) {
if($left < $right) {
//說明子序列內(nèi)存在多余1個的元素，那么需要拆分，分別排序，合并
//計算拆分的位置，長度/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);
}
}
//將兩個有序數(shù)組合并成一個有序數(shù)組
function mergeArray(&$arr, $left, $center, $right) {
//設(shè)置兩個起始位置標(biāo)記
$a_i = $left;
$b_i = $center+1;
while($a_i<=$center && $b_i<=$right) {
//當(dāng)數(shù)組A和數(shù)組B都沒有越界時
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)造成一個大頂堆.此時,整個序列的最大值就是堆頂 的根結(jié)點.將它移走(其實就是將其與堆數(shù)組的末尾元素交換, 此時末尾元素就是最大值),然后將剩余的n-1個序列重新構(gòu)造成一個堆,這樣就會得到n個元素的次大值.如此反復(fù)執(zhí)行,便能得到一個有序序列了
時間復(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)建成一個大頂堆
}
for (i = array.length - 1; i >= 0; i--)
{
/*把根節(jié)點交換出去*/
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é)點的值
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é)點,并每次減少一個末尾節(jié)點再調(diào)整堆,直到剩下一個元素
for($end = count($arr) - 1; $end > 0; $end--) {
$temp = $arr[0];
$arr[0] = $arr[$end];
$arr[$end] = $temp;
ajustNodes($arr, 0, $end - 1);
}
}
#初始化最大堆,從最后一個非葉子節(jié)點開始,最后一個非葉子節(jié)點編號為 數(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é)點
#@param $arr 待調(diào)整數(shù)組
#@param $start 調(diào)整的父節(jié)點坐標(biāo)
#@param $end 待調(diào)整數(shù)組結(jié)束節(jié)點坐標(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é)點坐標(biāo)
if($arr[$maxInx] < $arr[$leftChildInx]) {
$maxInx = $leftChildInx;
}
#如果待調(diào)整部分有右子節(jié)點
if($rightChildInx + 1 <= $len) {
if($arr[$maxInx] < $arr[$rightChildInx]) {
$maxInx = $rightChildInx;
}
}
}
#交換父節(jié)點和最大節(jié)點
if($start != $maxInx) {
$temp = $arr[$start];
$arr[$start] = $arr[$maxInx];
$arr[$maxInx] = $temp;
#如果交換后的子節(jié)點還有子節(jié)點,繼續(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ù)字，然后按每個位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。
時間復(fù)雜度：平均情況：O(d(r+n)) 最好情況：O（d(n+rd)） 最壞情況：O（d(r+n)） r:關(guān)鍵字的基數(shù) d:長度 n:關(guān)鍵字個數(shù)
空間復(fù)雜度：O（rd+n）
穩(wěn)定性：穩(wěn)定
<?php
#基數(shù)排序,此處僅對正整數(shù)進(jìn)行排序，至于負(fù)數(shù)和浮點數(shù)，需要用到補碼，各位有興趣自行研究
#計數(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)計每個元素出現(xiàn)次數(shù)
for ($i = 0; $i < count($arr_temp); $i++) {
$time_arr[$arr_temp[$i]]++;
}
#統(tǒng)計每個元素比其小或相等的元素出現(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排序的效率損耗
}
#計算某個數(shù)的位數(shù)
function get_digit($number) {
$i = 1;
while ($number >= pow(10, $i)) {
$i++;
}
return $i;
}
#獲取某個數(shù)字的從個位算起的第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ù)排序,以計數(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í)有所幫助
公眾號
事業(yè)單位
當(dāng)前位置：
公考類
招聘類
各類考試