排序算法---快速排序

快速排序头脑

• 从数组中选择一个元素作为基准点
  
• 排序数组，全部比基准值小的元素摆放在左边，而大于基准值的摆放在右边。每次分割结束以后基准值会插入到中间去。
  
• 末了使用递归，将摆放在左边的数组和右边的数组在进行一次上述的1和2操作。
  

快速排序代码实现

   测试数组【6,5,4, 7,1】
  第一轮：                                第二轮：                          第三轮：
  对比值：6                              对比值 5                          对比值 4
  左边 5，4，1                         左边 4，1                        左边 1
  右边 7                                     右边 []                              右边 []
  5,4,1,6,7                                  4,1,5,6,7                           1,4,5,6,7

1. function quickSort(arr) {
2.     if (arr.length <= 1) {
3.       return arr;
4.     }
5.     const left = []
6.     const right = []
7.     let temp = arr[0]
8.       for (let i = 1; i < arr.length; i++) {
9.         if (arr[i] > temp) {
10.           right.push(arr[i])
11.         } else {
12.           left.push(arr[i])
13.         }
14.       }
15.       return this.quickSort([...left]).concat(temp, this.quickSort(right))
16. }

复制代码

快速排序复杂度

时间复杂度
   快速排序的时间复杂度在均匀环境下是O(nlogn)，但在最坏环境下大概达到O(n^2)
  空间复杂度
   快速排序的空间复杂度依赖于递归调用的深度，理想环境下为O(logn)，但在最坏环境下大概达到O(n)
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。