你可能不知道的快速排序：三路快排

快速排序
快速排序是什么 快速排序是图灵奖得主C. A. R. Hoare（1934--）于1960时提出来的。

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。整个排序过程只需要三步：

  • 在数据集之中，选择一个元素作为"基准"（pivot）。
  • 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
  • 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

引自wikipedia 快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

步骤
找到该数组的基准点(中间数)，并创建两个空数组left和right；
遍历数组，拿出数组中的每个数和基准点进行比较，如果比基准点小就放到left数组中，如果比基准点大就放到right数组中；
对数组left和right进行递归调用。
方法一

 
 
 
 
      
  
  
  
  1. function quickSort(arr) { 
    2.   
  
  
  
  2.       if (arr.length<=1) {return arr;} 
    3.   
  
  
  
  3.       var left = [], 
    4.   
  
  
  
  4.         right = [], 
    5.   
  
  
  
  5.         baseDot =Math.round(arr.length/2), 
    6.   
  
  
  
  6.         base =arr.splice(baseDot, 1)[0]; 
    7.   
  
  
  
  7.  
    8.   
  
  
  
  8.       for (var i =0; i   
  
  
  
  9.         if (arr[i] < base) { 
    10.   
  
  
  
  10.           left.push(arr[i]) 
    11.   
  
  
  
  11.         }else { 
    12.   
  
  
  
  12.           right.push(arr[i]) 
    13.   
  
  
  
  13.         } 
    14.   
  
  
  
  14.       } 
    15.   
  
  
  
  15.  
    16.   
  
  
  
  16.       return quickSort(left).concat([base], quickSort(right)); 
    17.   
  
  
  
  17.     } 
    18.

实现一个quickSort的封装，并且定义left和right，找到数组的基准点baseDot和对应的基数base，然后遍历数组的每一项和base进行对比，最后递归调用，给出一个跳出条件if (arr.length <= 1) {return arr;}

方法二

 
 
 
 
      
  
  
  
  1. function quickSort(array, left, right) { 
    2.   
  
  
  
  2.       var length =array.length; 
    3.   
  
  
  
  3.         left =typeof left ==='number'? left :0, 
    4.   
  
  
  
  4.         right =typeof right ==='number'? right : length-1; 
    5.   
  
  
  
  5.  
    6.   
  
  
  
  6.         if (left < right) { 
    7.   
  
  
  
  7.             var index = left -1; 
    8.   
  
  
  
  8.             for (var i = left; i <= right; i++) { 
    9.   
  
  
  
  9.                 if (array[i] <= array[right]) { 
    10.   
  
  
  
  10.                     index++; 
    11.   
  
  
  
  11.                     var temp = array[index]; 
    12.   
  
  
  
  12.                     array[index] = array[i]; 
    13.   
  
  
  
  13.                     array[i] = temp; 
    14.   
  
  
  
  14.                 } 
    15.   
  
  
  
  15.             } 
    16.   
  
  
  
  16.             quickSort(array, left, index -1); 
    17.   
  
  
  
  17.             quickSort(array, index +1, right); 
    18.   
  
  
  
  18.         } 
    19.   
  
  
  
  19.         return array; 
    20.   
  
  
  
  20.     } 
    21.

快速排序的基本思想就是分治法

引自wikipedia 在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

快速排序的改进方法：三路快排
定义
三路快速排序是快速排序的的一个优化版本， 将数组分成三段， 即小于基准元素、 等于 基准元素和大于基准元素， 这样可以比较高效的处理数组中存在相同元素的情况,其它特征与快速排序基本相同。

我这里简单概括一下思路，有兴趣的同学可到上面的链接上阅读：[快速排序及优化(Java实现)][Java]

  • 随机选取基准值base(支点随机选取),参考[快速排序算法的优化思路总结][Link 1]
  • 配合着使用插入排序(当问题规模较小时，近乎有序时，插入排序表现的很好)
  • 当大量数据，且重复数多时，用三路快排
 
 
 
 
      
  
  
  
  1.  
    2.   
  
  
  
  2.    
    3.   
  
  
  
  3.    
    4.   
  
  
  
  4.     
    5.   
  
  
  
  5.      
    6.   
  
  
  
  6.      
    7.   
  
  
  
  7.      
    8.   
  
  
  
  8.      console.time("test0") 
    9.   
  
  
  
  9.      function qSort(arr) { 
    10.   
  
  
  
  10.       if(arr.length == 0) { 
    11.   
  
  
  
  11.        return []; 
    12.   
  
  
  
  12.       } 
    13.   
  
  
  
  13.       var left = []; 
    14.   
  
  
  
  14.       var right = []; 
    15.   
  
  
  
  15.       var pivot = arr[0]; 
    16.   
  
  
  
  16.       for(var i = 1; i < arr.length; i++) { // 注意这里的起始值，因为有一个作为flag了 
    17.   
  
  
  
  17.        if(arr[i] < pivot) { 
    18.   
  
  
  
  18.         left.push(arr[i]); 
    19.   
  
  
  
  19.        } else { 
    20.   
  
  
  
  20.         right.push(arr[i]); 
    21.   
  
  
  
  21.        } 
    22.   
  
  
  
  22.       } 
    23.   
  
  
  
  23.       return [...qSort(left), pivot, ...qSort(right)]; 
    24.   
  
  
  
  24.      } 
    25.   
  
  
  
  25.      console.log(qSort([9, 4, 10, 3, 1, 1, 0, 10, 8, 3, 9, 9, 4, 10, 10, 9, 9, 9, 1, 0])); 
    26.   
  
  
  
  26.      console.timeEnd("test0") 
    27.   
  
  
  
  27.      
    28.   
  
  
  
  28.      
    29.   
  
  
  
  29.      console.time("test1") 
    30.   
  
  
  
  30.      function qSort3(arr) {       //三路快排 
    31.   
  
  
  
  31.       if(arr.length == 0) { 
    32.   
  
  
  
  32.        return []; 
    33.   
  
  
  
  33.       } 
    34.   
  
  
  
  34.       var left = []; 
    35.   
  
  
  
  35.       var center = []; 
    36.   
  
  
  
  36.       var right = []; 
    37.   
  
  
  
  37.       var pivot = arr[0];    //偷懒，直接取第一个,实际取值情况 参考[快速排序算法的优化思路总结] 
    38.   
  
  
  
  38.       for(var i = 0; i < arr.length; i++) {       
    39.   
  
  
  
  39.        if(arr[i] < pivot) { 
    40.   
  
  
  
  40.         left.push(arr[i]); 
    41.   
  
  
  
  41.        } else if(arr[i] == pivot) { 
    42.   
  
  
  
  42.         center.push(arr[i]); 
    43.   
  
  
  
  43.        } else { 
    44.   
  
  
  
  44.         right.push(arr[i]); 
    45.   
  
  
  
  45.        } 
    46.   
  
  
  
  46.       } 
    47.   
  
  
  
  47.       return [...qSort3(left), ...center, ...qSort3(right)]; 
    48.   
  
  
  
  48.      } 
    49.   
  
  
  
  49.      console.log(qSort3([9, 4, 10, 3, 1, 1, 0, 10, 8, 3, 9, 9, 4, 10, 10, 9, 9, 9, 1, 0])) 
    50.   
  
  
  
  50.      console.timeEnd("test1") 
    51.   
  
  
  
  51.      
    52.   
  
  
  
  52.     
    53.   
  
  
  
  53.    
    54.   
  
  
  
  54.     
    55.   
  
  
  
  55.     
    56.   
  
  
  
  56.    
    57.   
  
  
  
  57.    
    58.

可以看到对有重复数据的数据优化还是很可观的。

分享标题：你可能不知道的快速排序：三路快排
网站地址：http://www.shufengxianlan.com/qtweb/news17/348267.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

移动网站建设知识

分类信息网

成都网站建设　　 　奢侈品网站建设方案　　 　成都网站建设　　 　微信服务号订阅号开发　　 　自贡服务器托管　　 　成都做网站　　 　阿坝网站建设　　 　网络推广公司　　 　德阳机房　　 　成都高电机柜租用　　 　App开发　　 　崇州做网站　　 　成都网站设计制作公司　　 　成都微信开发　　 　成都搬家公司　　 　成都广告招牌制作　　 　手提袋印刷制作　　 　成都微信小程序　　 　四川和正源　　 　信衡房屋鉴定