JS及PHP代码编写八大排序算法_

1、JS及PHP代码编写八大排序算法_ 这篇文章主要为大家具体介绍了JS及PHP代码编写八大排序算法的相关资料，感爱好的小伙伴们可以参考一下 从学习数据结构开头就接触各种算法基础，但是自从应付完考试之后就再也没有练习过，当在开发的时候也是什么时候用法什么时候去查一下，现在在学习JavaScript，趁这个时间再把各种基础算法整理一遍，分别以JS和PHP语法的方式编写代码。 1.冒泡排序 原理：接近的数字两两进行比较,根据从小到大或者从大到小的挨次进行交换,这样一趟过去后,最大或最小的数字被交换到了最终一位,然后再从头开头进行两两比较交换,直到倒数其次位时结束 时间简单度：平均状况：O（n2） 最好

2、状况：O（n） 最坏状况：O（n2） 空间简单度：O（1） 稳定性：稳定 /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(arrayj arrayj+1) isSort = false; var temp = arrayj; arrayj = arrayj + 1; arrayj + 1 = temp; if(isSort) break; c

3、onsole.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.简洁

4、选择排序 原理：通过n-i次关键字之间的比较,从n-i+1 个记录中选择关键字最小的记录,并和第i(1=i=n)个记录交换 简洁选择排序的性能要略优于冒泡排序 时间简单度:平均状况：O（n2） 最好状况：O（n） 最坏状况：O（n2） 空间简单度：O（1） 稳定性：不稳定 /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(arrayj arraypos) pos

5、=j; var temp=arrayi; arrayi=arraypos; arraypos=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_

6、dump($array); ? 3.挺直插入排序 原理：将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 比冒泡法和选择排序的性能要更好一些 时间简单度：平均状况：O（n2） 最好状况：O（n） 最坏状况：O（n2） 空间简单度：O（1） 稳定性：稳定 /JavaScript var array = 23,0,32,45,56,75,43,0,34; for(var j = 0;j array.length;j+) var key = arrayj; var i = j

7、- 1; while (i -1 arrayi key) arrayi + 1 = arrayi; i = i - 1; arrayi + 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; va

8、r_dump($array); ? 4.快速排序 原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的全部数据都比另外一部分的全部数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 时间简单度:平均状况：O（nlog2n） 最好状况：O（nlog2n） 最坏状况：O（n2） 空间简单度：O（nlog2n） 稳定性：不稳定 /JavaScript 快速排序 var array = 23,0,32,45,56,75,43,0,34; var quickSort = function(arr) if (arr.length

9、= 1) return arr; /检查数组的元素个数，假如小于等于1，就返回。 var pivotIndex = Math.floor(arr.length / 2);/ var pivot = arr.splice(pivotIndex,1)0;/选择基准（pivot），并将其与原数组分别， var left = ;/定义两个空数组，用来存放一左一右的两个子集 var right = ; for (var i = 0; i arr.length; i+)/遍历数组，小于基准的元素放入左边的子集，大于基准的元素放入右边的子集。 if (arri pivot) left.push(arri);

10、 else right.push(arri); return quickSort(left).concat(pivot, quickSort(right);/用法递归不断重复这个过程，就可以得到排序后的数组。 ; var newArray=quickSort(array); console.log(newArray); - ?php $array = 23,0,32,45,56,75,43,0,34; function quick_sort($arr) /先推断是否需要连续进行 $length = count($arr); if($length = 1) return $arr; $base_

11、num = $arr0;/选择一个标尺 选择第一个元素 /初始化两个数组 $left_array = array();/小于标尺的 $right_array = array();/大于标尺的 for($i=1; $i$length; $i+) /遍历 除了标尺外的全部元素，根据大小关系放入两个数组内 if($base_num $arr$i) /放入左边数组 $left_array = $arr$i; else /放入右边 $right_array = $arr$i; /再分别对 左边 和 右边的数组进行相同的排序处理方式 /递归调用这个函数,并记录结果 $left_array = quick_

12、sort($left_array); $right_array = quick_sort($right_array); /合并左边 标尺 右边 return array_merge($left_array, array($base_num), $right_array); $newArray=quick_sort($array); var_dump($newArray); ? 5.希尔排序 原理：先将整个待排序的记录序列分割成为若干子序列分别进行挺直插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次挺直插入排序。 时间简单度:平均状况：O(nn) 最好状况：O（nlog2n） 最

13、坏状况：O（n2） 空间简单度：O（1） 稳定性：不稳定 /JavaScript 希尔排序 var array = 23,0,32,45,56,75,43,0,34; var shellSort = function (arr) var length=arr.length; var h=1; while(hlength/3) h=3*h+1;/设置间隔 while(h=1) for(var i=h; ilength; i+) for(var j=i; j=h arrjarrj-h; j-=h) var temp =arrj-h; arrj-h=arrj; arrj=temp; h=(h-1)/

14、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;/设置间隔 while($h=1) for($i=$h; $i$length; $i+) for($j=$i; $j=$h $arr$j$arr$j-$h; $j-=$h) $temp =$arr$j

15、-$h; $arr$j-$h=$arr$j; $arr$j=$temp; $h=($h-1)/3; return $arr; $newArray = shellSort($array); var_dump($newArray) ? 6.归并排序 原理：假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后两两归并,得到(不小于n/2的最小整数)个长度为2或1的有序子序列,再两两归并,.如此重复,直至得到一个长度为n的有序序列为止 时间简单度:平均状况：O(nlog2n) 最好状况：O（nlog2n） 最坏状况：O（nlog2n） 空间简单度：O（1） 稳定性：稳定 /

16、JavaScript 归并排序 function isArray1(arr) if(Ototype.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(left0right0) result.push(left

17、.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;ilen;i+) work.push(arri); work.push(); for(lim=len;lim1;)/lim为分组长度 for(j=0,k=0;klim;j+,k=k+2) workj=merge(workk,wo

18、rkk+1); workj=; lim=Math.floor(lim+1)/2); return work0; var array = 23,0,32,45,56,75,43,0,34; console.log(mergeSort(array); - ?php /归并排序 function mergeSort($arr) $len = count($arr);/求得数组长度 mSort($arr, 0, $len-1); /实际实现归并排序的程序 function mSort($arr, $left, $right) if($left $right) /说明子序列内存在多余1个的元素，那么需要

19、拆分，分别排序，合并 /计算拆分的位置，长度/2 去整 $center = floor($left+$right) / 2); /递归调用对左边进行再次排序： mSort($arr, $left, $center); /递归调用对右边进行再次排序 mSort($arr, $center+1, $right); /合并排序结果 mergeArray($arr, $left, $center, $right); /将两个有序数组合并成一个有序数组 function mergeArray($arr, $left, $center, $right) /设置两个起始位置标记 $a_i = $left;

20、$b_i = $center+1; while($a_i=$center $b_i=$right) /当数组A和数组B都没有越界时 if($arr$a_i $arr$b_i) $temp = $arr$a_i+; else $temp = $arr$b_i+; /推断 数组A内的元素是否都用完了，没有的话将其全部插入到C数组内： while($a_i = $center) $temp = $arr$a_i+; /推断 数组B内的元素是否都用完了，没有的话将其全部插入到C数组内： while($b_i = $right) $temp = $arr$b_i+; /将$arrC内排序好的部分，写入到

21、$arr内： 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.堆排序 原理：堆排序就是利用堆进行排序的方法.基本思想是:将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶 的根结点.将它移走(其实就是将其与堆数组的末尾元素交换, 此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次大值.如此反复执行,便能得到

22、一个有序序列了 时间简单度：平均状况：O(nlog2n) 最好状况：O（nlog2n） 最坏状况：O（nlog2n） 空间简单度：O（1） 稳定性：不稳定 /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); /将数组array构建成一个大顶堆 for (i = array.length - 1; i =

23、0; i-) /*把根节点交换出去*/ var temp = arrayi; arrayi = array0; array0 = temp; /*余下的数组连续构建成大顶堆*/ heapAdjust(array, 0, i - 1); return array; function heapAdjust(array, start, max) var temp = arraystart;/temp是根节点的值 for (var j = 2 * start; j max; j *= 2) if (j max arrayj arrayj + 1) /取得较大孩子的下标 +j; if (temp = a

24、rrayj) break; arraystart = arrayj; start = j; arraystart = temp; var newArray = heapSort(array); console.log(newArray); - ?php /堆排序 function heapSort($arr) #初始化大顶堆 initHeap($arr, 0, count($arr) - 1); #开头交换首尾节点,并每次削减一个末尾节点再调整堆,直到剩下一个元素 for($end = count($arr) - 1; $end 0; $end-) $temp = $arr0; $arr0 =

25、 $arr$end; $arr$end = $temp; ajustNodes($arr, 0, $end - 1); #初始化最大堆,从最终一个非叶子节点开头,最终一个非叶子节点编号为 数组长度/2 向下取整 function initHeap($arr) $len = count($arr); for($start = floor($len / 2) - 1; $start = 0; $start-) ajustNodes($arr, $start, $len - 1); #调整节点 #param $arr 待调整数组 #param $start 调整的父节点坐标 #param $end

26、待调整数组结束节点坐标 function ajustNodes($arr, $start, $end) $maxInx = $start; $len = $end + 1; #待调整部分长度 $leftChildInx = ($start + 1) * 2 - 1; #左孩子坐标 $rightChildInx = ($start + 1) * 2; #右孩子坐标 #假如待调整部分有左孩子 if($leftChildInx + 1 = $len) #猎取最小节点坐标 if($arr$maxInx $arr$leftChildInx) $maxInx = $leftChildInx; #假如待调整

27、部分有右子节点 if($rightChildInx + 1 = $len) if($arr$maxInx $arr$rightChildInx) $maxInx = $rightChildInx; #交换父节点和最大节点 if($start != $maxInx) $temp = $arr$start; $arr$start = $arr$maxInx; $arr$maxInx = $temp; #假如交换后的子节点还有子节点,连续调整 if($maxInx + 1) * 2 = $len) ajustNodes($arr, $maxInx, $end); $arr = array(23,0,

28、32,45,56,75,43,0,34); heapSort($arr); var_dump($arr); ? 8.基数排序 原理：将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能用法于整数。 时间简单度：平均状况：O(d(r+n) 最好状况：O（d(n+rd)） 最坏状况：O（d(r+n)） r:关键字的基数 d:长度 n:关键字个数 空间简单度：O（rd+n） 稳定性：稳定 ?php #基数排序,此处仅对正整数进行排序，至于负数和浮点数，需要用到补码，各位有爱好自行讨论 #计数排序 #param $arr 待排序数组 #param $digit_num 依据第几位数进行排序 function counting_sort($arr, $digit_num = false) if ($digit_num != false) #假如参数$digit_num不为空，则依据元素的第$digit_num位数进行排序 for ($i = 0; $i count($arr); $i+) $arr_temp$i = get_specific_digit($arr$i, $digit_num); else $arr_temp