快速排序(Quicksort)的Javascript实现

作者: 阮一峰

日期: 2011年4月 4日

珠峰培训

日本程序员norahiko,写了一个排序算法的动画演示,非常有趣。

这个周末,我就用它当做教材,好好学习了一下各种排序算法。

排序算法(Sorting algorithm)是计算机科学最古老、最基本的课题之一。要想成为合格的程序员,就必须理解和掌握各种排序算法。

目前,最常见的排序算法大概有七八种,其中"快速排序"(Quicksort)使用得最广泛,速度也较快。它是图灵奖得主C. A. R. Hoare(1934--)于1960时提出来的。

"快速排序"的思想很简单,整个排序过程只需要三步:

  (1)在数据集之中,选择一个元素作为"基准"(pivot)。

  (2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。

  (3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

举例来说,现在有一个数据集{85, 24, 63, 45, 17, 31, 96, 50},怎么对其排序呢?

第一步,选择中间的元素45作为"基准"。(基准值可以任意选择,但是选择中间的值比较容易理解。)

第二步,按照顺序,将每个元素与"基准"进行比较,形成两个子集,一个"小于45",另一个"大于等于45"。

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

下面参照网上的资料(这里这里),用Javascript语言实现上面的算法。

首先,定义一个quickSort函数,它的参数是一个数组。

var quickSort = function(arr) {

};

然后,检查数组的元素个数,如果小于等于1,就返回。

var quickSort = function(arr) {

  if (arr.length <= 1) { return arr; }

};

接着,选择"基准"(pivot),并将其与原数组分离,再定义两个空数组,用来存放一左一右的两个子集。

var quickSort = 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 quickSort = 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 < arr.length; i++){

    if (arr[i] < pivot) {

      left.push(arr[i]);

    } else {

      right.push(arr[i]);

    }

  }

};

最后,使用递归不断重复这个过程,就可以得到排序后的数组。

var quickSort = 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 < arr.length; i++){

    if (arr[i] < pivot) {

      left.push(arr[i]);

    } else {

      right.push(arr[i]);

    }

  }

  return quickSort(left).concat([pivot], quickSort(right));

};

使用的时候,直接调用quickSort()就行了。

(完)

一灯学堂

留言(76条)

好东西!谢谢!

通俗易懂

取数组中间值的时候为什么不直接取而要Splice,如果是为了后续循环好像没必要

why I love python:

q_sort= lambda l: l if len(l)<=1 else q_sort([x for x in l[1:] if x<l[0]])+[l[0]]+q_sort([x for x in l[1:] if x<=l[0]])

相当好,感谢分享!

In Haskell

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
  let smallerSorted = quicksort [a | a <- xs, a <= x]
    biggerSorted = quicksort [a | a <- xs, a > x]
  in smallerSorted ++ [x] ++ biggerSorted

见 Learn You a Haskell for Great Good! 一书

引用reader的发言:

In Haskell

见 Learn You a Haskell for Great Good! 一书

函数式编程的确够简洁

这个太专业了吧,看不懂~~不过阮兄还是辛苦了。

大于"基准"的元素放入左边的子集,小于基准的元素放入右边的子集。

反了,应该是:

小于"基准"的元素放入左边的子集,大于基准的元素放入右边的子集。

引用wordgold的发言:

取数组中间值的时候为什么不直接取而要Splice,如果是为了后续循环好像没必要

有道理。

@Richard Lee:谢谢提醒,确实写错了,已更正。

@wordgold:想了一下,你说得对,没必要splice,只要在遍历数组的时候,只要跳过“基准”元素就行了,这样代码也更易读。谢谢。

赞,快速排序是递归的经典应用

In Erlang:

  qsort([]) ->> [];
  qsort([Pivot|T])->
    qsort([X || X <- T, X < Pivot])
    ++[Pivot]++
    qsort([X || X <- T, X > Pivot]).

可以写得列简洁些的,此类题其实初中生都能看懂.

@limon:能具体说明吗?

每排一次都要新建两个一左一右的数组,那一个非常大的数组,递归非常多次,那要消耗多少内存呢?

引用iotioa的发言:

每排一次都要新建两个一左一右的数组,那一个非常大的数组,递归非常多次,那要消耗多少内存呢?

是啊,快速排序算法的优点之一就是可以原地排序,博主这样浪费掉了这个特性。

那个排序演示很有趣~

这个不错啊,以前的那本数据结构都是伪代码~~~

那啥,Array对象不是有sort()方法吗

基本原理是实现了,但有一点不尽如人意的地方。
排序后得到的数组不是原来数组了。
如:
var a=[2,1,5,7,4,10,5];
alert(a==quickSort(a));//此处得到结果是false
一般来说,执行排序方法后,原来数组顺序就改变了,但还是原来的数组。
楼主的做法相当于返回了另一个数组。

js数组自带排序方法就是如此
alert(a==a.sort());//返回true

觉的你这个网站的技术文章太好了,加为收藏,定时拜读。

我解释下Limon提到的python的代码:

q_sort= lambda l: l if len(l)<=1 else q_sort([x for x in l[1:] if x<l[0]])+[l[0]]+q_sort([x for x in l[1:] if x<=l[0]])

首先lambda是用来动态声明一个函数的. 这个函数接受一个参数l, l很明显是python的list类型.
这个函数本身赋值给了等号左边的q_sort.

接下来分析右边的函数:
l if len(l) else 后面的部分是如果l的长度大于1就会执行

接下来分析else后面的部分:
采用l的第一个元素l[0]为"基准".
有两个+号,把三段list连接为一个list:
第一段list是小于l[0]的元素快速排序的结果
第二段list就只包含l[0]一个元素
第三段list是大于l[0]的元素快速排序的结果.
三段加起来就是最终的结果, 并且是排好序的. 其中第一段和第三段的生成过程中, 递归调用了q_sort本身.

但是, Simon的这个代码是无法得出正确的结果的! 也就是说是错的! 以下是示例运行结果:
>>> q_sort= lambda l: l if len(l)<=1 else q_sort([x for x in l[1:] if x<l[0]])+[l[0]]+q_sort([x for x in l[1:] if x<=l[0]])
>>> print q_sort([2,3,5,6,3,1,8,5])
[1, 2, 1]

接下来我会留言分析下为什么Simon给出的python解决方案是错的.

Simon的代码之所不行,是因为它打错了一个字符. 最后的"="
一开始我以为是什么隐蔽的错误呢, 没想到是这么明显的.

引用阮一峰的发言:

@wordgold:想了一下,你说得对,没必要splice,只要在遍历数组的时候,只要跳过“基准”元素就行了,这样代码也更易读。谢谢。

调用javascript的splice方法很好啊。

此处var pivot = arr.splice(pivotIndex, 1)[0]有两个作用:

(1)将“基准”从arr数组删除

(2)将arr数组的“基准”赋值给pivot

如果按照@wordgold直接取,则后面还需要写一段将“基准”元素从arr数组删除的代码,这样一来代码反而更多。阮兄的代码很精简,拜读。

用C#代码实现:
Func<IEnumerable<IComparable>, IEnumerable<IComparable>> quick_sort = null;
quick_sort = new Func<IEnumerable<IComparable>, IEnumerable<IComparable>>(l => l.Count() <= 1 ? l : quick_sort(l.Skip(1).Where(t => t.CompareTo(l.ElementAt(0)) < 0)).Concat(new IComparable[] { l.ElementAt(0) }).Concat(quick_sort(l.Skip(1).Where(t => t.CompareTo(l.ElementAt(0)) >= 0))));

博主在编程方面的日志稍微少了点。可否写一些关于日常项目中的设计思想的日志,如果你愿意分享的话。

引用魏蕤的发言:

调用javascript的splice方法很好啊。

此处var pivot = arr.splice(pivotIndex, 1)[0]有两个作用:

(1)将“基准”从arr数组删除

(2)将arr数组的“基准”赋值给pivot

如果按照@wordgold直接取,则后面还需要写一段将“基准”元素从arr数组删除的代码,这样一来代码反而更多。阮兄的代码很精简,拜读。

不需要删除啊,仔细想想,比较的时候只比较大于小于没有等于就相当于删除了的

这个对理解quicksort的思想有好处,但实际应用中,quicksort一般会采取"in place"的做法,不应该引入额外的数组,若是这样,quicksort与mergesort都差不多了

这篇贴子的点击率还挺高的,希望博主更改成就地排序,不然可能会误导初学者啊

haskell的可以更简单:
qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]

这里有所有语言的qsort实现大全:http://rosettacode.org/wiki/Sorting_algorithms/Quicksort
几个函数语言haskell、erlang、ocaml、clojure的实现是最简洁的。

嘿嘿 谢谢分享 这是我下一步要学习的

添个js原地排序的版本:

function quick (start ,end){
var mid = start , temp = arr[start];
for(var i = start+1 ; i if(arr[i] arr[mid]=arr[i];// >> mid+1 i-1
var j = i ;
mid++;
while(j!=mid){arr[j]=arr[j-1];j--}
}
}
arr[mid]= temp ;
return mid;
}

function sort (start , end ){
if(end>start){
var mid = quick(start ,end);console.log(mid)
sort(start,mid-1);sort(mid+1,end);
}
}

sort(0,arr.length)
console.log(arr);

引用Tyler Long的发言:

Simon的代码之所不行,是因为它打错了一个字符. 最后的"="
一开始我以为是什么隐蔽的错误呢, 没想到是这么明显的.


你也够粗心的,不是最后的“=”,是if x<=l[0]]) 这里面的 < 要改成 > 就对了

引用wordgold的发言:

取数组中间值的时候为什么不直接取而要Splice,如果是为了后续循环好像没必要

splice会对原数组做操作,这里获取pivot的同时,还从原数组中删除了pivot。

引用findfunaax的发言:

是啊,快速排序算法的优点之一就是可以原地排序,博主这样浪费掉了这个特性。

那个排序演示很有趣~

快速排序的递归部分并不是原地排序的,所以原地排序并不是快速排序的优点。

why i love ruby?

def quick_sort(a)
  (x=a.pop) ? quick_sort(a.select{|i| i x}) : []
end

挺好的,就是如果在对比的时候不加上那个不用splice在循环的时候判断是否和pivoet相等会少递归循环。。而且会比较好读。。

[2,4,3,4,6,3,2,5,6,2,3,6,5,4]如果数组有重复的这样就不行了

引用Max的发言:

[2,4,3,4,6,3,2,5,6,2,3,6,5,4]如果数组有重复的这样就不行了

遇到同样的问题

引用wordgold的发言:

取数组中间值的时候为什么不直接取而要Splice,如果是为了后续循环好像没必要

有必要的,如果你你splice掉你的中间元素 可能会造成死循环。

跟你们说一下,
1:
快速排序从数组中间抽数字可以任意指定一个位置,比如说 0 第一位,
2:
也不一定判断数组的长度,也可以判断 数组【0】!== undefined || 操作数 是否为 null 为递归停止条件

引用阮一峰的发言:
@wordgold:想了一下,你说得对,没必要splice,只要在遍历数组的时候,只要跳过“基准”元素就行了,这样代码也更易读。谢谢。

实际测试 var pivot=arr.splice(pivotIndex,1)[0]; 改成
var pivot=arr[pivotIndex];
报错,太多的递归。

感谢分享,讲的很仔细。
使用 splice 有个不好的地方是会破坏原数组,可以直接: var pivot = arr[0];
然后 for 循环时: for(var i = 1; i

引用wordgold的发言:

取数组中间值的时候为什么不直接取而要Splice,如果是为了后续循环好像没必要

有必要,splice会改变数组,就会把当前的value删除,

楼主你好,有个排序的问题请教一下,我在js中markerArr 记录了地图中点的坐标信息,我想依次判断从第一个点之后与第一个点的距离,getdistance计算坐标间的距离。按照与第一个点的距离从小到大排序,我这样写实现的不对,你能帮忙看一下么,你有什么好的解决方法么
if (markerArr.length > 3) {
for (var i = markerArr.length; i > 0; i--) {
for (var j = 0; j if (j == markerArr.length - 2) { break; }
var px0 = markerArr[0].split(',');
var px1 = markerArr[j + 1].split(',');
var px2 = markerArr[j + 2].split(',');
//alert(getDisance(px0[1], px0[0], px1[1], px1[0]));
//alert(getDisance(px0[1], px0[0], px2[1], px2[0]));
if (getDisance(px0[1], px0[0], px1[1], px1[0]) > getDisance(px0[1], px0[0], px2[1], px2[0])) {
var middle = markerArr[1];
markerArr[1] = markerArr[2];
markerArr[2] = middle;
}
}
}
}

引用飞啊的发言:

实际测试 var pivot=arr.splice(pivotIndex,1)[0]; 改成
var pivot=arr[pivotIndex];
报错,太多的递归。

If you wanna make this works, you have to skip the arr[pivotIndex].

//提高一下代码的效率:
var quickSort = function(arr) {
var arrLength = arr.length;

if (arrLength return arr;
}

var pivotIndex = Math.floor(arrLength / 2);

var pivot = arr[pivotIndex];

var left = [];
var right = [];
var equal = [];
for (var i = 0; i if (arr[i] left.push(arr[i]);
} else if (arr[i] > pivot) {
right.push(arr[i]);
} else {
equal.push(arr[i]);
}
}

return quickSort(left).concat(equal, quickSort(right));
};

引用wordgold的发言:

取数组中间值的时候为什么不直接取而要Splice,如果是为了后续循环好像没必要

他要删除那个元素的,来使数组越来越小,满足递归,这个程序有一个问题,就是原数组会改变

引用fms的发言:

遇到同样的问题

遍历的时候跳过基准即可

谢谢您,以前一直没搞明白快排,这篇文章真是写得简洁明了!

引用飞啊的发言:

实际测试 var pivot=arr.splice(pivotIndex,1)[0]; 改成
var pivot=arr[pivotIndex];
报错,太多的递归。

太多的递归是因为数组长度没有减小,如果不用splice,那么排序重复的元素会出现问题:
var quickSort = function(arr){
var len = arr.length;
if(len<2){
return arr;
}
var pivotIndex = Math.floor(len/2);
var pivot = arr[pivotIndex];
var left = [];
var right = [];
for(var i=0,item;item=arr[i++];){
if(item<pivot){
left.push(item);
}
if(item>pivot){
right.push(item);
}
}
return quickSort(left).concat([pivot],quickSort(right));
}
//有重复元素,排序结果错误
//var arr = [1,3,6,3,23,76,1,34,222,6,456,221,556,75,30];
//无重复元素可以正常排序
var arr = [1,4,6,45,324,6678,333,2234,9];
quickSort(arr);

峰哥,右上角的搜索框,获得焦点时有篮框啊,很不美观,建议设置


input{outline:none};

@小浩少校:谢谢指出,已经修改了。

另外还是用了一个left和一个right数组,这样空间复杂度就提升到了O(3n)

引用wells.tang的发言:

有道理。

引用wordgold的发言:

取数组中间值的时候为什么不直接取而要Splice,如果是为了后续循环好像没必要

splice的目的是将取“中心”元素的值之后将原数组中该值删除,这样下面的for循环的时候是不会循环中心元素了。[22, 21, 23, 12, 1, 242]比如,这样splice之后原来的数组就是[22, 21, 23, 1, 242]。

楼主,数组里加个100就失效了

楼主的代码没错是我试错了

var pivot = arr.splice(pivotIndex, 1)[0];

这里的[0]是什么意思,有些不明白!

引用wordgold的发言:

不需要删除啊,仔细想想,比较的时候只比较大于小于没有等于就相当于删除了的

如果不比较等于,如果基准的数有重复就会覆盖掉

var quickSort = function(arr) {
  if (arr.length   var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++){
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
};

var ay=[85, 24, 63, 45, 17, 31, 96, 50,1,2,7]
var quickSort = 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 < arr.length; i++){
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  console.log(quickSort(left).concat([pivot], quickSort(right))) ;
};

quickSort(ay)

楼主你看,为何这排序错误

您的方法改变了原数组 其实没有必要,改进后的方法
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}

var left = [],
right = [],
pivot = arr[0];

for (var i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}

return quickSort(left).concat(pivot, quickSort(right));
}

按照您的算法:var pivot = arr.splice(pivotIndex, 1)[0];第一次取到的基准应该是17,不是45。依次下面的数组长度为偶数时都与之不符合。

阮老师,请问js里的sort是用快速排序实现的吗?

引用Mervyn的发言:

您的方法改变了原数组 其实没有必要,改进后的方法

function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}

var left = [],
right = [],
pivot = arr[0];

for (var i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}

return quickSort(left).concat(pivot, quickSort(right));
}


其实你这个方法也不是原数组了,并且没有判断相等的情况

引用0x4d的发言:

阮老师,请问js里的sort是用快速排序实现的吗?

sort是根据字符编码的顺序进行排序的,不是快排

function quicksorter(arr,start,end)
{
var i =start;
var j =end;
var m;
if(i {
var x = arr[i];
while(i {
while(i x) j--;
if(i while(i if(i }
arr[i]=x;
m=i;
console.log(m);
quicksorter(arr,start,m-1);
quicksorter(arr,m+1,end);
}
}

不需要用其他数组的快速排序在此。

function quickSort(list,start,stop) {
start = start||0;
stop = stop||(list.length-1);
var tmp = null;
for(var indL = start,indR = stop-1; indL if(list[indL] indL++;
continue;
}
if(list[indR]>=list[stop]){
indR--;
continue;
}
tmp = list[indL];
list[indL] = list[indR];
list[indR] = tmp;
}
if(list[indL]>list[stop]){
tmp = list[indL];
list[indL] = list[stop];
list[stop] = tmp;
}
if(indL-start > 1){
quickSort(list,start,indL);
}
if(stop-indL > 1){
quickSort(list,indL,stop);
}
}
quickSort([23,4,45,7,5,4,7,67,8]);

引用nebula的发言:

splice会对原数组做操作,这里获取pivot的同时,还从原数组中删除了pivot。


按照博客里有必要。因为如果不把pivot从原来数组中去除,会发生quickSort之后的数组和原来的数组一样的情况,从而造成死循环。
例如quickSort([1,1,5]) 返回一个quickSort([1,1,5])。


  var pivotIndex = Math.floor(arr.length / 2) ;
  var pivot = arr.splice(pivotIndex, 1)[0];
这两句代码在数据集{85, 24, 63, 45, 17, 31, 96, 50}应该先取的17吧;
老师你的图好像画错啦!!!

引用aaa的发言:


  var pivotIndex = Math.floor(arr.length / 2) ;
  var pivot = arr.splice(pivotIndex, 1)[0];
这两句代码在数据集{85, 24, 63, 45, 17, 31, 96, 50}应该先取的17吧;
老师你的图好像画错啦!!!

楼上+1

不是原地排序,大数组比较耗内存

发现了一个Bug:代码运行的时候会修改原来的数组,运行之后源数组(input Array)会丢失一项,结果数组(Output Array)倒是正常的。
一开始我用的数组是博主提供的:[85, 24, 63, 45, 17, 31, 96, 50],发现少了17,
后来继续添加了一几个数字,变成[85, 24, 63, 45, 17, 31, 96, 50,33,65,99,120,15],发现少了96

代码:
var Arr = [85, 24, 63, 45, 17, 31, 96, 50];

console.log(Arr);

var quickSort = function(arr) {
console.log(Arr.length);

  if (arr.length <= 1) { return arr; }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];

console.log(Arr.length);

  for (var i = 0; i

    if (arr[i]       left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }

  }
console.log(Arr.length);

  return quickSort(left).concat([pivot], quickSort(right));
};


var NewArr = quickSort(Arr);

console.log(Arr);
console.log(NewArr);


浏览器控制台输出:
(8) [85, 24, 63, 45, 17, 31, 96, 50]
8 (手动加注:开始的时候长度还是8,然后运行的时候就变成7了,以下同)
7
...
7
(7) [85, 24, 63, 45, 31, 96, 50]
(8) [17, 24, 31, 45, 50, 63, 85, 96]

`function qSort(arr, low, high) {
let pivot;
if (low < high) {
pivot = partition(arr, low, high);
qSort(arr, low, pivot - 1);
qSort(arr, pivot + 1, high);
}
};

function partition(arr, low, high) {
let pivotKey = arr[low];
while(low < high) {
while(low < high && arr[high] >= pivotKey)
high--;
[arr[low], arr[high]] = [arr[high], arr[low]];
while(low < high && arr[low] <= pivotKey)
low++;
[arr[low], arr[high]] = [arr[high], arr[low]];
}
return low;
};

let a = [8,3,4,1,9,7,6,10,2]

qSort(a, 0, 8);
console.log(a);`

阮老师希望您看下这段代码跟您博客代码的对比,我觉得空间和时间复杂度都有比较大的区别。

我也分享一个自己写的原地排序版本:
function SQ(arr, start, end){
if(arr.lnegth return arr;
}
const mid = arr[end];
let midindex = end;
let cha = 0;
for(let i=start;i if(arr[i-cha] > mid){
const tmp = arr.splice(i-cha,1)[0];
arr.splice(end,0,tmp)
cha++
midindex--
}
}
if(midindex - start > 2){
SQ(arr,start,midindex-1);
}
if(end - midindex > 2){
SQ(arr,midindex,end);
}
return arr;
}
const ary = [0,333333,1,33,222,44,2,17,4,784,31,6,7];
console.log("hh",SQ(ary,0,ary.length-1))

我要发表看法

«-必填

«-必填,不公开

«-我信任你,不会填写广告链接