如何使用快速排序

这篇文章主要介绍“如何使用快速排序”，在日常操作中，相信很多人在如何使用快速排序问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”如何使用快速排序”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

创新互联长期为上千多家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为柳城企业提供专业的成都网站设计、网站制作，柳城网站改版等技术服务。拥有10年丰富建站经验和众多成功案例,为您定制开发。

 快速排序
快速排序是什么 快速排序是图灵奖得主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进行递归调用。
方法一

function quickSort(arr) {       if (arr.length<=1) {return arr;}       var left = [],         right = [],         baseDot =Math.round(arr.length/2),         base =arr.splice(baseDot, 1)[0];        for (var i =0; i 
实现一个quickSort的封装，并且定义left和right，找到数组的基准点baseDot和对应的基数base，然后遍历数组的每一项和base进行对比，最后递归调用，给出一个跳出条件if (arr.length <= 1) {return arr;}
方法二
function quickSort(array, left, right) {       var length =array.length;         left =typeof left ==='number'? left :0,         right =typeof right ==='number'? right : length-1;          if (left < right) {             var index = left -1;             for (var i = left; i <= right; i++) {                 if (array[i] <= array[right]) {                     index++;                     var temp = array[index];                     array[index] = array[i];                     array[i] = temp;                 }             }             quickSort(array, left, index -1);             quickSort(array, index +1, right);         }         return array;     }
快速排序的基本思想就是分治法
引自wikipedia 在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
快速排序的改进方法：三路快排
定义
三路快速排序是快速排序的的一个优化版本， 将数组分成三段， 即小于基准元素、 等于 基准元素和大于基准元素， 这样可以比较高效的处理数组中存在相同元素的情况,其它特征与快速排序基本相同。
我这里简单概括一下思路，有兴趣的同学可到上面的链接上阅读：[快速排序及优化(Java实现)][Java]
随机选取基准值base(支点随机选取),参考[快速排序算法的优化思路总结][Link 1]
配合着使用插入排序(当问题规模较小时，近乎有序时，插入排序表现的很好)
当大量数据，且重复数多时，用三路快排
                               console.time("test0")      function qSort(arr) {       if(arr.length == 0) {        return [];       }       var left = [];       var right = [];       var pivot = arr[0];       for(var i = 1; i < arr.length; i++) { // 注意这里的起始值，因为有一个作为flag了        if(arr[i] < pivot) {         left.push(arr[i]);        } else {         right.push(arr[i]);        }       }       return [...qSort(left), pivot, ...qSort(right)];      }      console.log(qSort([9, 4, 10, 3, 1, 1, 0, 10, 8, 3, 9, 9, 4, 10, 10, 9, 9, 9, 1, 0]));      console.timeEnd("test0")                console.time("test1")      function qSort3(arr) {       //三路快排       if(arr.length == 0) {        return [];       }       var left = [];       var center = [];       var right = [];       var pivot = arr[0];    //偷懒，直接取第一个,实际取值情况 参考[快速排序算法的优化思路总结]       for(var i = 0; i < arr.length; i++) {              if(arr[i] < pivot) {         left.push(arr[i]);        } else if(arr[i] == pivot) {         center.push(arr[i]);        } else {         right.push(arr[i]);        }       }       return [...qSort3(left), ...center, ...qSort3(right)];      }      console.log(qSort3([9, 4, 10, 3, 1, 1, 0, 10, 8, 3, 9, 9, 4, 10, 10, 9, 9, 9, 1, 0]))      console.timeEnd("test1")                          
可以看到对有重复数据的数据优化还是很可观的。
到此，关于“如何使用快速排序”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注创新互联网站，小编会继续努力为大家带来更多实用的文章！
            
            
                        

            网页题目：如何使用快速排序            

            文章转载：http://shouzuofang.com/article/igdojs.html