从学习数据结构开始就接触各种算法基础，但是自从应付完考试之后就再也没有练习过，当在开发的时候也是什么时候使用什么时候去查一下，现在在学习JavaScript，趁这个时间再把各种基础算法整理一遍，分别以JS和PHP语法的方式编写代码。
1.冒泡排序@H_502_2@
原理：@H_502_2@临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束
时间复杂度：@H_502_2@平均情况：O（n2） 最好情况：O（n） 最坏情况：O（n2）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@稳定
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;">
PHP
$array = [23,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.简单选择排序@H_502_2@
原理：@H_502_2@通过n-i次关键字之间的比较,从n-i+1 个记录中选择关键字最小的记录,并和第i(1<=i<=n)个记录交换 简单选择排序的性能要略优于冒泡排序
时间复杂度:@H_502_2@平均情况：O（n2） 最好情况：O（n） 最坏情况：O（n2）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@不稳定
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;">
PHP
$array = [23,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.直接插入排序@H_502_2@
原理：@H_502_2@将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 比冒泡法和选择排序的性能要更好一些
时间复杂度：@H_502_2@平均情况：O（n2） 最好情况：O（n） 最坏情况：O（n2）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@稳定
-1 && array[i] > key)
{
array[i + 1] = array[i];
i = i - 1;
}
array[i + 1] = key;
}
console.log(array);
PHP;">
PHP
//直接插入排序
$array = [23,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.快速排序@H_502_2@
原理：@H_502_2@通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
时间复杂度:@H_502_2@平均情况：O（nlog2n） 最好情况：O（nlog2n） 最坏情况：O（n2）
空间复杂度：@H_502_2@O（nlog2n）
稳定性：@H_502_2@不稳定
快速排序
var array = [23,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;">
PHP
$array = [23,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];
}
}
//再分别对 左边 和 右边的数组进行相同的排序处理方式
//递归<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank" class="keywords">调用</a>这个<a href="https://www.jb51.cc/tag/hanshu/" target="_blank" class="keywords">函数</a>,并记录结果
$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.希尔排序 @H_502_2@
原理：@H_502_2@先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。。
时间复杂度:@H_502_2@平均情况：O(n√n) 最好情况：O（nlog2n） 最坏情况：O（n2）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@不稳定
=1)
{
for(var i=h; i=h && arr[j]
PHP;">
PHP
//希尔排序
$array = [23,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.归并排序
@H_502_2@原理：@H_502_2@假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后两两归并,得到(不小于n/2的最小整数)个长度为2或1的有序子序列,再两两归并,...如此重复,直至得到一个长度为n的有序序列为止
时间复杂度:@H_502_2@平均情况：O(nlog2n) 最好情况：O（nlog2n） 最坏情况：O（nlog2n）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@稳定
0&& right.length >0){
if(left[0]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,34];
console.log(mergeSort(array));
mSort($arr,$len-1);
}
//实际实现归并排序的程序
function mSort(&$arr,$left,$right) {
if($left < $right) {
//说明子序列内存在多余1个的元素，那么需要拆分，分别排序，合并
//计算拆分的位置，长度/2 去整
$center = floor(($left+$right) / 2);
//递归<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank" class="keywords">调用</a>对左边进行再次排序：
mSort($arr,$center);
//递归<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank" class="keywords">调用</a>对右边进行再次排序
mSort($arr,$center+1,$right);
//合并排序结果
mergeArray($arr,$center,$right);
}
}
//将两个有序数组合并成一个有序数组
function mergeArray(&$arr,$right) {
//设置两个起始位置<a href="https://www.jb51.cc/tag/biaoji/" target="_blank" class="keywords">标记</a>
$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,34);
mergeSort($arr);
var_dump($arr);
?>
7.堆排序@H_502_2@
原理：@H_502_2@堆排序就是利用堆进行排序的方法.基本思想是:将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶 的根结点.将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次大值.如此反复执行,便能得到一个有序序列了
时间复杂度：@H_502_2@平均情况：O(nlog2n) 最好情况：O（nlog2n） 最坏情况：O（nlog2n）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@不稳定
<div class="jb51code">
<pre class="brush:js;">
//JavaScript 堆排序
var array = [23,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,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);
{
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);
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);
?>
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);
{
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;">
PHP
$array = [23,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.直接插入排序@H_502_2@
原理：@H_502_2@将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 比冒泡法和选择排序的性能要更好一些
时间复杂度：@H_502_2@平均情况：O（n2） 最好情况：O（n） 最坏情况：O（n2）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@稳定
-1 && array[i] > key)
{
array[i + 1] = array[i];
i = i - 1;
}
array[i + 1] = key;
}
console.log(array);
PHP;">
PHP
//直接插入排序
$array = [23,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.快速排序@H_502_2@
原理：@H_502_2@通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
时间复杂度:@H_502_2@平均情况：O（nlog2n） 最好情况：O（nlog2n） 最坏情况：O（n2）
空间复杂度：@H_502_2@O（nlog2n）
稳定性：@H_502_2@不稳定
快速排序
var array = [23,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;">
PHP
$array = [23,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];
}
}
//再分别对 左边 和 右边的数组进行相同的排序处理方式
//递归<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank" class="keywords">调用</a>这个<a href="https://www.jb51.cc/tag/hanshu/" target="_blank" class="keywords">函数</a>,并记录结果
$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.希尔排序 @H_502_2@
原理：@H_502_2@先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。。
时间复杂度:@H_502_2@平均情况：O(n√n) 最好情况：O（nlog2n） 最坏情况：O（n2）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@不稳定
=1)
{
for(var i=h; i=h && arr[j]
PHP;">
PHP
//希尔排序
$array = [23,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.归并排序
@H_502_2@原理：@H_502_2@假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后两两归并,得到(不小于n/2的最小整数)个长度为2或1的有序子序列,再两两归并,...如此重复,直至得到一个长度为n的有序序列为止
时间复杂度:@H_502_2@平均情况：O(nlog2n) 最好情况：O（nlog2n） 最坏情况：O（nlog2n）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@稳定
0&& right.length >0){
if(left[0]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,34];
console.log(mergeSort(array));
mSort($arr,$len-1);
}
//实际实现归并排序的程序
function mSort(&$arr,$left,$right) {
if($left < $right) {
//说明子序列内存在多余1个的元素，那么需要拆分，分别排序，合并
//计算拆分的位置，长度/2 去整
$center = floor(($left+$right) / 2);
//递归<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank" class="keywords">调用</a>对左边进行再次排序：
mSort($arr,$center);
//递归<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank" class="keywords">调用</a>对右边进行再次排序
mSort($arr,$center+1,$right);
//合并排序结果
mergeArray($arr,$center,$right);
}
}
//将两个有序数组合并成一个有序数组
function mergeArray(&$arr,$right) {
//设置两个起始位置<a href="https://www.jb51.cc/tag/biaoji/" target="_blank" class="keywords">标记</a>
$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,34);
mergeSort($arr);
var_dump($arr);
?>
7.堆排序@H_502_2@
原理：@H_502_2@堆排序就是利用堆进行排序的方法.基本思想是:将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶 的根结点.将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次大值.如此反复执行,便能得到一个有序序列了
时间复杂度：@H_502_2@平均情况：O(nlog2n) 最好情况：O（nlog2n） 最坏情况：O（nlog2n）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@不稳定
<div class="jb51code">
<pre class="brush:js;">
//JavaScript 堆排序
var array = [23,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,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);
稳定性：@H_502_2@不稳定
快速排序
var array = [23,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;">
PHP
$array = [23,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];
}
}
//再分别对 左边 和 右边的数组进行相同的排序处理方式
//递归<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank" class="keywords">调用</a>这个<a href="https://www.jb51.cc/tag/hanshu/" target="_blank" class="keywords">函数</a>,并记录结果
$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.希尔排序 @H_502_2@
原理：@H_502_2@先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。。
时间复杂度:@H_502_2@平均情况：O(n√n) 最好情况：O（nlog2n） 最坏情况：O（n2）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@不稳定
=1)
{
for(var i=h; i=h && arr[j]
PHP;">
PHP
//希尔排序
$array = [23,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.归并排序
@H_502_2@原理：@H_502_2@假设初始序列含有n个记录,则可以看成n个有序的子序列,每个子序列的长度为1,然后两两归并,得到(不小于n/2的最小整数)个长度为2或1的有序子序列,再两两归并,...如此重复,直至得到一个长度为n的有序序列为止
时间复杂度:@H_502_2@平均情况：O(nlog2n) 最好情况：O（nlog2n） 最坏情况：O（nlog2n）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@稳定
0&& right.length >0){
if(left[0]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,34];
console.log(mergeSort(array));
mSort($arr,$len-1);
}
//实际实现归并排序的程序
function mSort(&$arr,$left,$right) {
if($left < $right) {
//说明子序列内存在多余1个的元素，那么需要拆分，分别排序，合并
//计算拆分的位置，长度/2 去整
$center = floor(($left+$right) / 2);
//递归<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank" class="keywords">调用</a>对左边进行再次排序：
mSort($arr,$center);
//递归<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank" class="keywords">调用</a>对右边进行再次排序
mSort($arr,$center+1,$right);
//合并排序结果
mergeArray($arr,$center,$right);
}
}
//将两个有序数组合并成一个有序数组
function mergeArray(&$arr,$right) {
//设置两个起始位置<a href="https://www.jb51.cc/tag/biaoji/" target="_blank" class="keywords">标记</a>
$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,34);
mergeSort($arr);
var_dump($arr);
?>
7.堆排序@H_502_2@
原理：@H_502_2@堆排序就是利用堆进行排序的方法.基本思想是:将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶 的根结点.将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次大值.如此反复执行,便能得到一个有序序列了
时间复杂度：@H_502_2@平均情况：O(nlog2n) 最好情况：O（nlog2n） 最坏情况：O（nlog2n）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@不稳定
<div class="jb51code">
<pre class="brush:js;">
//JavaScript 堆排序
var array = [23,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,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);
稳定性：@H_502_2@稳定
0&& right.length >0){
if(left[0]
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,34];
console.log(mergeSort(array));
PHP;">
PHP
//归并排序
function mergeSort(&$arr) {
$len = count($arr);//求得数组长度
mSort($arr,$len-1);
}
//实际实现归并排序的程序
function mSort(&$arr,$left,$right) {
if($left < $right) {
//说明子序列内存在多余1个的元素，那么需要拆分，分别排序，合并
//计算拆分的位置，长度/2 去整
$center = floor(($left+$right) / 2);
//递归<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank" class="keywords">调用</a>对左边进行再次排序：
mSort($arr,$center);
//递归<a href="https://www.jb51.cc/tag/diaoyong/" target="_blank" class="keywords">调用</a>对右边进行再次排序
mSort($arr,$center+1,$right);
//合并排序结果
mergeArray($arr,$center,$right);
}
}
//将两个有序数组合并成一个有序数组
function mergeArray(&$arr,$right) {
//设置两个起始位置<a href="https://www.jb51.cc/tag/biaoji/" target="_blank" class="keywords">标记</a>
$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,34);
mergeSort($arr);
var_dump($arr);?>
7.堆排序@H_502_2@
原理：@H_502_2@堆排序就是利用堆进行排序的方法.基本思想是:将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶 的根结点.将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次大值.如此反复执行,便能得到一个有序序列了
时间复杂度：@H_502_2@平均情况：O(nlog2n) 最好情况：O（nlog2n） 最坏情况：O（nlog2n）
空间复杂度：@H_502_2@O（1）
稳定性：@H_502_2@不稳定
<div class="jb51code">
<pre class="brush:js;">
//JavaScript 堆排序
var array = [23,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,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);
<pre class="brush:js;">
//JavaScript 堆排序
var array = [23,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,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);