专栏首页coding个人笔记阮一峰快速排序

阮一峰快速排序

本打算学一波快速排序,查了查资料,吓一大跳,说阮一峰大神的快排是不对的,以此开始了一大波大神针对这个问题的各种观点。感兴趣的可以看看知乎这篇帖子:

https://www.zhihu.com/question/276746146/answer/390729075

不管对还是错,阮一峰大神的快排思路是对的:

在数据集之中,选择一个元素作为"基准"(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 = []; 
   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));
};

思路很清晰找出基准之后,左边数组右边数组和基准的数组都很清晰。

那些说为什么用splice(splice本身也有时间复杂度)、为什么每次开辟新的left、right数组等,这确实是这段代码的问题。但是阮一峰大神只是提供思路,这些问题都是能优化的。当时ES6也没出来,以后还会有更多的数组扩展,那不是能更简单的实现快速排序,但是快速排序的思路是不变的。

我本来想把两个都优化了,奈何能力有限,无法解决一直开辟新数组的问题,也就是空间复杂度的问题:

var quickSort = function(arr) { 
 if (arr.length <= 1) { return arr; } 
  var pivot = arr[0]; 
  var left = []; 
  var right = []; 
  var mid = []; 
  for (var i = 0; i < arr.length; i++){ 
   if (arr[i] < pivot) { 
     left.push(arr[i]); 
   } else if (arr[i] > pivot){ 
     right.push(arr[i]); 
    }else{ 
      mid.push(arr[i]); 
   } 
} 
return quickSort(left).concat(mid, quickSort(right));
};

如果有大神知道,希望能告知优化方法。

本文分享自微信公众号 - coding个人笔记(gh_2ce38b49dae1),作者:wade

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ES6之数组的扩展

    copyWithin方法:改变原数组,接收三个参数,在当前数组内部,将指定位置的成员复制到其他位置(数组函数参数的下标都是包前不包后)

    wade
  • 深度优先DFS和广度优先BFS

    之前在HTML渲染过程这篇分享有人在评论问我,这个过程是DFS还是BFS,发现自己好水,确实不知道渲染过程是什么优先,到现在都不知道。

    wade
  • JavaScript之数组

    Array在JavaScript里面很常用,讲真的,平时开发除了循环数组和push数组之外,对于数组的其他方法和属性几乎都是用到的时候百度。今天自己整理一些数组...

    wade
  • PHP四种排序算法(快速排序)

    阿沐
  • 排序算法之快速排序

    快速排序是一种非常优秀的排序算法,应用的也非常广泛,面试时面试官也经常让你手写一个快排,所以说学习快速排序是非常有必要的。

    dejavu1zz
  • 快速排序填坑口诀

    快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此在很多笔试面试中出现的几率...

    KevinYan
  • Data Structure_Sort Algorithm

    生成随机的n个数量的数组,输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性,所以需要一个验证正确性和计算排序时间的:

    西红柿炒鸡蛋
  • [Go] Golang练习项目-快速排序的GO语言实现

    快速排序首先选一个基准(你也可以认为是要放到排序后数组正确位置的元素)pivot,然后将数组按照选取的基准 pivot 进行划分。而选取 pivot 的方式又有...

    陶士涵
  • Sort Algorithm

    生成随机的n个数量的数组,输出数组每一个元素的内容。测试排序算法使用的标准就是运行时间和排序的正确性,所以需要一个验证正确性和计算排序时间的:

    西红柿炒鸡蛋
  • 数据结构与算法 基础排序(O(n^2))

    不能直接找到一个比minIndex小的就swap,因为交换后比较的就是minIndex和后一个元素2个元素的比较 而不是minIndex和后面所有元素比较

    g小志

扫码关注云+社区

领取腾讯云代金券