JavaScript快速排序实现实例教程.docx

JavaScript快速排序实现实例教程

JavaScript快速排序实现实例教程 目前最常见的排序算法大概有七八种，理解和掌握各种排序算法似乎是一个合格的程序员所必须要掌握的。今天想要和大家分享快速排序算法的Javascript的实现。 快速排序(Quicksort),又称为划分交换排序(partition-exchangesort)，最早是由东尼·霍尔提出的。 基本思想 快速排序使用分治法(Divideandconquer)策略(即分而治之，各个击破)把一个序列(list)分为两个子序列(sub-lists)。其基本步骤如下: 从数列中挑出一个元素，称为基准(pivot)。 重新排序数列，所有小于基准的元素，都移到基准的左边;所有大于基准的元素都移到基准的右边。这个分区结束之后，该基准处于数列的中间位置，称为分区(partition)操作。 对基准左边和右边的.两个子集，进行递归操作，即不断重复第一步和第二步。直到所有子集只剩下一个元素为止。 示例说明 下面我们举个示例进行排序说明，数列为[8,7,0,7,5,2,5,3,1]。 第一步:基准值选取。基准值可以任意选取，便于理解，这里我们选择中间值5作为基准。 [8,7,0,7,5,2,5,3,1] 第二步:进行分区操作。按照顺序将每个元素与基准进行比较，想成两个子集，大于5与小于5. [0,2,5,3,1,5,8,7,7] 第三步，递归操作。对两个子集不断重复第一步和第二步，直到所有子集只剩下一个元素为止。 [0,2,5,3,1]5[8,7,7][0,2,3,1,5]5[7,7,8][0,2,3,1]5,5,7,7,8[0,1,2,3]5,5,7,7,8[0,1,2,3,5,5,7,7,8] Javascript的实现 讲述了快速排序的基本思想，下面就让我们使用代码对其进行实现吧~ 第一步:定义函数quicksort,参数为一个数组。 varquicksort=function(arr){ }; 第二步:检查数组个数，小于等于1，则返回。 varquicksort=function(arr){if(arr.length<=1){returnarr; } }; 第三步:进行基准选择，定义两个空数组进行左右两个子集元素的存放。 varquicksort=function(arr){if(arr.length<=1){returnarr; }varpivotIndex=Math.floor(arr.length/2);varpivot=arr.splice(pivotIndex,1)[0];varleft=[];varright=[];for(vari=0;i<arr.length;i++){if(arr[i]<pivot){ left.push(arr[i]); }else{ right.push(arr[i]); } } }; 第四步:递归操作。对两个子集不断重复第一步和第二步，直到所有子集只剩下一个元素为止。 varquicksort=function(arr){if(arr.length<=1){returnarr; }varpivotIndex=Math.floor(arr.length/2);varpivot=arr.splice(pivotIndex,1)[0];varleft=[];varright=[];for(vari=0;i<arr.length;i++){if(arr[i]<pivot){ left.push(arr[i]); }else{ right.push(arr[i]); } }returnquicksort(left).concat([pivot],quicksort(right)); }; 第五步:quicksort函数的调用 这里可以直接定义一个数组，对函数进行调用即可。 varquicksort=function(arr){if(arr.length<=1){returnarr; }varpivotIndex=Math.floor(arr.length/2);varpivot=arr.splice(pivotIndex,1)[0];varleft=[];varright=[];for(vari=0;i<arr.length;i++){if(arr[i]<pivot){ left.push(arr[i]); }else{ right.push(arr[i]); } }returnquicksort(left).concat([pivot],quicksort(right)); };vararray=[8,7,0,7,5,2,5,3,1]; quicksort(arr