js冒泡排序时间复杂度（js快排（JavaScript快速排序算法）- 前端面试）

快速排序算法通过多次比较和交换来实现排序 
  
  
  
  
  
  
，其排序流程如下：

(1) 首先设定一个分界值 
  
  
  
  
  
  
 ，通过该分界值将数组分成左右两部分              。

(2) 将大于或等于分界值的数据集中到数组右边

 


 


 


 


 


 


 ，小于分界值的数据集中到数组的左边
 
  
 
  
 
  
 
  
 
  
 
  
 
 。此时 
 
 
 
 
 
 
，左边部分中各元素都 小于分界值 
   
   
   
   
   
   
 ，而右边部分中各元素都大于或等于分界值













。

(3) 然后
 

 

 

 

 

 

 ，左边和右边的数据可以独立排序  
  
  
  
  
  
  。对于左侧的数组数据
 

 

 

 

 

 

 
，又可以取一个分界值             ，将该部分数据分成左右两部分 

 
 

 
 

 
 

 
 

 
 

 
 

 ，同样在左边放置较小值













，右边放置较大值 
  
  
  
  
  
  
 。右侧的数组数据也可以做类似处理


 


 


 


 


 


 


。

(4) 重复上述过程                    ，可以看出 
 
 
 
 
 
 
 
 
 
 
 
 
 ，这是一个递归定义 
 
 
 
 
 
 。通过递归将左侧部分排好序后




















，再递归排好右侧部分的顺序  
   
   
   
   
   
   
 。当左 
  
  
  
  
  
  
、右两个部分各数据排序完成后             ，整个数组的排序也就完成了

 

 

 

 

 

 

。

var arr = [9, 4, 3, 1, 6, 3, 8, 7] /** * 快速排序 * @param {array} - arr 需要排序的数组 * @returns {array} */ function quickSort (arr) { if (arr.length <= 1) return arr var arr1 = [], arr2 = [] for (var i = 1; i < arr.length; i++) { if (arr[i] < arr[0]) { arr1.push(arr[i]) } else { arr2.push(arr[i]) } } arr1 = quickSort(arr1) arr2 = quickSort(arr2) arr1.push(arr[0]) return arr1.concat(arr2) } console.log(quickSort(arr)) // [1, 3, 3, 4, 6, 7, 8, 9]

微信交流群

前端面试：剑指 Offer (3群)