手机版

用Javascript实现快速排序的算法详解

时间:2021-09-08 来源:互联网 编辑:宝哥软件园 浏览:

目前最常见的排序算法大概有七八种,其中‘Quicksort’应用比较广泛,速度也比较快。它是由图灵奖获得者霍尔(1934-)在1960年提出的。

“快速排序”的思路很简单,整个排序过程只需要三个步骤:

(1)在数据集中,选择一个元素作为“透视”。

(2)所有小于“基准”的元素都移到“基准”的左边;所有大于基准的元素都移动到基准的右侧。

(3)对“基准”的左右子集重复步骤1和步骤2,直到所有子集只剩下一个元素。

例如,有一个数据集{85,24,63,45,17,31,96,50}。怎么排序?

第一步是选择中间元素45作为“参考”。(参考值可以任意选择,但选择中间值更容易理解。)

第二步,将每个元素依次与“基准”进行比较,形成两个子集,一个“小于45”,另一个“大于或等于45”。

第三步:对两个子集重复第一步和第二步,直到所有子集中只剩下一个元素。

参考在线数据,上述算法是用Javascript语言实现的。

首先,定义一个快速排序函数,它的参数是一个数组。

var quick sort=function(arr){ };然后,检查数组中的元素数量,如果小于或等于1,则返回。

var quick sort=function(arr){ if(arr . length=1){ return arr;}};然后,选择“pivot”,将其从原始数组中分离出来,然后定义两个空数组来存储左右两个子集。

var quick sort=function(arr){ if(arr . length=1){ return arr;} var Pivotindex=Math . floor(arr . length/2);var pivot=arr.splice(pivotIndex,1)[0];var left=[];var right=[];};然后,开始遍历数组。小于基准的元素放在左边的子集中,大于基准的元素放在右边的子集中。

var quick sort=function(arr){ if(arr . length=1){ return arr;} var Pivotindex=Math . floor(arr . length/2);var pivot=arr.splice(pivotIndex,1)[0];var left=[];var right=[];for(var I=0;一、长度;I){ if(arr[I]pivot){ left . push(arr[I]);} else { right . push(arr[I]);}}};最后,使用递归重复这个过程,就可以得到排序后的数组。

var quick sort=function(arr){ if(arr . length=1){ return arr;} var Pivotindex=Math . floor(arr . length/2);var pivot=arr.splice(pivotIndex,1);var left=[];var right=[];for(var I=0;一、长度;I){ if(arr[I]pivot){ left . push(arr[I]);} else { right . push(arr[I]);} }返回快速排序(左)。concat(透视、快速排序(右));};var dataArray=[85,24,63,45,17,31,96,50];console.log(dataArray.join(','));console.log(快速排序(数据数组))。join(',');希望这篇文章对你的javascript编程有所帮助。

版权声明:用Javascript实现快速排序的算法详解是由宝哥软件园云端程序自动收集整理而来。如果本文侵犯了你的权益,请联系本站底部QQ或者邮箱删除。