这篇文章主要介绍“如何使用快速排序”,在日常操作中,相信很多人在如何使用快速排序问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”如何使用快速排序”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
快速排序
快速排序是什么 快速排序是图灵奖得主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 <arr.length; i++) { if (arr[i] < base) { left.push(arr[i]) }else { right.push(arr[i]) } } return quickSort(left).concat([base], quickSort(right)); }
实现一个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]
配合着使用插入排序(当问题规模较小时,近乎有序时,插入排序表现的很好)
当大量数据,且重复数多时,用三路快排
<!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title></title> <script type="text/javascript"> 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") </script> <script type="text/javascript"> 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") </script> </head> <body> </body> </html>
可以看到对有重复数据的数据优化还是很可观的。
到此,关于“如何使用快速排序”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。