快速排序(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()就行了。

(完)

留言(105条)

好东西!谢谢!

通俗易懂

取数组中间值的时候为什么不直接取而要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))

过程清晰命了,很容易理解,谢谢!

@Mervyn:

splice的一个作用是最终数组元素小于等于1递归开始返回,你这样的话不动原数组那如果数组全部是相同的元素就会导致递归无法返回

你这种做法,略微简单简单了一点吧;你申明了left 和right 两个空的数组,增加的空间复杂度;
较为完善的做法,是利用交换;而不是添加额外的空间

here is good example:

https://www.hackerearth.com/zh/practice/algorithms/sorting/quick-sort/tutorial/

我觉得 阮老师的这篇文章 主要是想告诉我们 Quicksort 这个思想 又用一个案例来更好的理解 Quicksort 的原理,至于这个案例代码的性能、复杂度并不用太在意 只有真正理解了 Quicksort 那上面的问题都....

引用向往蓝天的林的发言:

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

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


这里splice返回的是删除元素的数组,用[0]去得到具体的值

阮老师,我补充了下,因为数组是引用传递,
因为函数中使用了splice函数,会造成原数组少一个元素,
然后concat函数中,貌似函数参数不必刻意是数组,


function quickSort(arr) {
// 数组是引用传递 避免修改原数组
arr = JSON.parse(JSON.stringify(arr));

// 数组只有一个元素
if(arr.length < 2) {
return arr;
}

let middleIndex = Math.floor(arr.length / 2);
let middle = arr.splice(middleIndex, 1)[0];
let left = [];
let right = [];

// 和中间元素比较,小的放左边, 大的放右边
for(let i = 0; i < arr.length; i++) {
arr[i] }

// 递归
return quickSort(left).concat(middle, quickSort(right));
}

let arr = [85, 24, 63, 45, 17, 31, 96, 50];

quickSort(arr);
console.log(quickSort(arr));
console.log(arr);

引用Ted的发言:

In Erlang:

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

Hail Erlang!

In Typescript:

const qsort = ([pivot, ...arr]) =>
pivot == undefined ? [] :
[...qsort(arr.filter(x => x pivot,
...qsort(arr.filter(x => x > pivot))]

引用vision57的发言:

In Typescript:

const qsort = ([pivot, ...arr]) =>
pivot == undefined ? [] :
[...qsort(arr.filter(x => x
pivot,
...qsort(arr.filter(x => x > pivot))]


const qsort = ([pivot, ...arr]) =>
pivot == undefined ? [] :
[...qsort(arr.filter(x => x pivot,
...qsort(arr.filter(x => x > pivot))]

引用vision57的发言:


const qsort = ([pivot, ...arr]) =>
pivot == undefined ? [] :
[...qsort(arr.filter(x => x
pivot,
...qsort(arr.filter(x => x > pivot))]


const qsort = ([pivot, ...arr]) =>
pivot == undefined ? [] :
[...qsort(arr.filter(x => x pivot,
...qsort(arr.filter(x => x > pivot))]

引用wordgold的发言:

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

可以删除原数组中间的值

何時退化到插入排序?

很简洁。什么时候能再说说quickSelect算法,就完美了。

splice是很有必要的,无论基准值是取中间值还是任意位置的值(如第一位)。
var arr = [99,22];
function quickSort1(arr) {
if (arr.length return arr;
}
var pivot = arr.splice(0, 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 quickSort1(left).concat([pivot],quickSort1(right));
}
console.log(quickSort1(arr));
如果把var pivot = arr.splice(0, 1)[0];改成var pivot = arr[0];就会造成死循环

通俗易懂

没理解为什么要多此一举的试用splice去从所谓的中间拿有什么意义。还不是直接arr[0].
function quick(arr){
if(!arr || arr.length === 0 ) return [];
let minArr=[];
let maxArr=[];
let limit = arr[0];
for(let i=1;i<arr.length;i++){
if(arr[i]>limit){
maxArr.push(arr[i]);
}else{
minArr.push(arr[i]);
}
}
return quick(minArr).concat(limit).concat(quick(maxArr));
};

js 也挺清晰的

function qs(arr: number[]): number[] {
if (arr.length const left = [];
const right = [];
const [a, ...rest] = arr;
rest.forEach(x => (x return [...qs(left), a, ...qs(right)];
}

请问一下,如果调用这种方法后再调用原数组,是不是会少一个元素?

突然有这种感觉

谢天谢地 世上有一个阮一峰

我也想做他这样的人

看到大家都在讨论有没有必要删除基准元素的问题:亲测需要删。

有人说不删,只需要比较的时候只push大于或小于基准元素的元素即可,但是有个问题别忘了:还有些重复的元素,这样最后得到的数组元素只包含那些不重复的元素。

但是如果另一个子集允许小于等于的时候,又会出现栈溢出!最后发现还是删了比较好

前几日有个面试官还问我快排的最差情况,我查阅了是所有元素都有序或者是所有元素都相等的情况。我在我的博客里改进了阮老师的 JS 实现算法来解决哪两个情况,参见下面链接

https://www.cnblogs.com/everlose/p/12815606.html

引用findfunaax的发言:

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

那个排序演示很有趣~

快速排序并不是原地排序吧

前面看的好好的,看到最后一行当场去世。。。。。

取中间的值作为基准可能会导致不稳定。取第一个应该会更好吧。

10年后依然受用

阮哥怎么讲什么都懂啊?

这种解法现在在力扣上面, 提交过不去了啊..

引用wordgold的发言:

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

是为了取到基准值的同时遍历数组时跳过基准值,用splice就不用写判断语句了

引用小白的发言:

这种解法现在在力扣上面, 提交过不去了啊..

内存占用过大

我要发表看法

«-必填

«-必填,不公开

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