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

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