目前最常见的排序算法大概有七八种,其中‘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编程有所帮助。