时间:2021-05-26
从学习数据结构开始就接触各种算法基础,但是自从应付完考试之后就再也没有练习过,当在开发的时候也是什么时候使用什么时候去查一下,现在在学习JavaScript,趁这个时间再把各种基础算法整理一遍,分别以JS和PHP语法的方式编写代码。
1.冒泡排序
原理:临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束
时间复杂度:平均情况:O(n2) 最好情况:O(n) 最坏情况:O(n2)
空间复杂度:O(1)
稳定性:稳定
2.简单选择排序
原理:通过n-i次关键字之间的比较,从n-i+1 个记录中选择关键字最小的记录,并和第i(1<=i<=n)个记录交换 简单选择排序的性能要略优于冒泡排序
时间复杂度:平均情况:O(n2) 最好情况:O(n) 最坏情况:O(n2)
空间复杂度:O(1)
稳定性:不稳定
3.直接插入排序
原理:将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。 比冒泡法和选择排序的性能要更好一些
时间复杂度:平均情况:O(n2) 最好情况:O(n) 最坏情况:O(n2)
空间复杂度:O(1)
稳定性:稳定
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 <= 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 (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } 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_num = $arr[0];//选择一个标尺 选择第一个元素 //初始化两个数组 $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_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(n√n) 最好情况:O(nlog2n) 最坏情况: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(h<length/3) { h=3*h+1;//设置间隔 } 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;//设置间隔 } 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.归并排序
原理:假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后两两归并,得到(不小于n/2的最小整数)个长度为2或1的有序子序列,再两两归并,...如此重复,直至得到一个长度为n的有序序列为止
时间复杂度:平均情况:O(nlog2n) 最好情况:O(nlog2n) 最坏情况:O(nlog2n)
空间复杂度:O(1)
稳定性:稳定
//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);//求得数组长度 mSort($arr, 0, $len-1); } //实际实现归并排序的程序 function mSort(&$arr, $left, $right) { if($left < $right) { //说明子序列内存在多余1个的元素,那么需要拆分,分别排序,合并 //计算拆分的位置,长度/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; $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内排序好的部分,写入到$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个元素的次大值.如此反复执行,便能得到一个有序序列了
时间复杂度:平均情况:O(nlog2n) 最好情况:O(nlog2n) 最坏情况:O(nlog2n)
空间复杂度:O(1)
稳定性:不稳定
8.基数排序
原理:将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。
时间复杂度:平均情况:O(d(r+n)) 最好情况:O(d(n+rd)) 最坏情况:O(d(r+n)) r:关键字的基数 d:长度 n:关键字个数
空间复杂度:O(rd+n)
稳定性:稳定
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例讲述了PHP排序算法之基数排序(RadixSort)。分享给大家供大家参考,具体如下:基数排序在《大话数据结构》中并未讲到,但是为了凑齐八大排序算法,我
冒泡排序在八大排序中,冒泡排序是最为出名的排序算法之一!冒泡排序的代码还是相当简单的,两层循环,外层是冒泡轮数,里层是依次比较,这个算法的时间复杂度为O(n2)
如何用Python实现八大排序算法1、插入排序描述插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于
Python实现八大排序算法,具体内容如下1、插入排序描述插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算
选择排序,作为八大经典算法之一,虽不如插入,快速,希尔等排序高效,但其结构简单,思路清晰,适合新手理解算法,了解排序,适合数据较少时的排序情况。如下是选择排序的