相思资源网 Design By www.200059.com
从学习数据结构开始就接触各种算法基础，但是自从应付完考试之后就再也没有练习过，当在开发的时候也是什么时候使用什么时候去查一下，现在在学习JavaScript，趁这个时间再把各种基础算法整理一遍，分别以JS和PHP语法的方式编写代码。
1.冒泡排序
原理：临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束
时间复杂度：平均情况：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; 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);
<"color: #800000">原理：通过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(array[j] < array[pos]) { pos=j; } } var temp=array[i]; array[i]=array[pos]; array[pos]=temp; } console.log(array);<"color: #800000">原理：将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增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 = 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);<"color: #800000">原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
时间复杂度:平均情况：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);<"color: #800000">原理：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。。
时间复杂度:平均情况：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);<"color: #800000">原理：假设初始序列含有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));<"color: #800000">原理：堆排序就是利用堆进行排序的方法.基本思想是:将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶 的根结点.将它移走(其实就是将其与堆数组的末尾元素交换, 此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次大值.如此反复执行,便能得到一个有序序列了
时间复杂度：平均情况：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 >= 0; i--) { /*把根节点交换出去*/ var temp = array[i]; array[i] = array[0]; array[0] = temp; /*余下的数组继续构建成大顶堆*/ heapAdjust(array, 0, i - 1); } return array; } function heapAdjust(array, start, max) { var temp = array[start];//temp是根节点的值 for (var j = 2 * start; j < max; j *= 2) { if (j < max && array[j] < array[j + 1]) { //取得较大孩子的下标 ++j; } if (temp >= array[j]) break; array[start] = array[j]; start = j; } array[start] = temp; } var newArray = heapSort(array); console.log(newArray);<"color: #800000">原理：将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
时间复杂度：平均情况：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 = $arr; } $max = max($arr); $time_arr = array(); #储存元素出现次数的数组 #初始化出现次数数组 for ($i = 0; $i <= $max; $i++) { $time_arr[$i] = 0; } #统计每个元素出现次数 for ($i = 0; $i < count($arr_temp); $i++) { $time_arr[$arr_temp[$i]]++; } #统计每个元素比其小或相等的元素出现次数 for ($i = 0; $i < count($time_arr) - 1; $i++) { $time_arr[$i + 1] += $time_arr[$i]; } #利用出现次数对数组进行排序 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排序的效率损耗 } #计算某个数的位数 function get_digit($number) { $i = 1; while ($number >= pow(10, $i)) { $i++; } return $i; } #获取某个数字的从个位算起的第i位数 function get_specific_digit($num, $i) { if ($num < pow(10, $i - 1)) { return 0; } return floor($num % pow(10, $i) / pow(10, $i - 1)); } #基数排序,以计数排序作为子排序过程 function radix_sort(&$arr) { #先求出数组中最大的位数 $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); ?>以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
标签：js,php,排序算法
相思资源网 Design By www.200059.com广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com相思资源网 Design By www.200059.com暂无JS及PHP代码编写八大排序算法的评论...
《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。