DDR爱好者之家

JS及PHP代码编写八大排序算法
站长资源 2024/11/29 佚名
39 1538
DDR爱好者之家 Design By 杰米

从学习数据结构开始就接触各种算法基础，但是自从应付完考试之后就再也没有练习过，当在开发的时候也是什么时候使用什么时候去查一下，现在在学习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);
?>







以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。


                                

                                

                                     

                                
DDR爱好者之家 Design By 杰米

                            

                        

                        

                            

                                广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）

                                免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
                            

                        

                        

                            
                            
                        

                        
                        
DDR爱好者之家 Design By 杰米

                        
                        
                    

                    

                        

                            

                                

                                    

                                        

                                    

                                    

                                        

                                            
                                        

                                    

                                

                                

                                    
ddrfans.com
                                            
                                                DDR爱好者之家 
                                    

                                    

                                        

                                            
                                        

                                        

                                            
                                        

                                        

                                            
                                        

                                        

                                            
                                        

                                    

                                    

                                    

                                        

                                            8,675无损音乐
                                        

                                        

                                            1,324高清电影
                                        

                                        

                                            213破解软件
                                        

                                        

                                            70,141收录资讯

更新日志

友情链接

杰晶网络 DDR爱好者之家 南强小屋 黑松山资源网 白云城资源网
DDR爱好者之家 Design By 杰米