JavaScript的排序算法——快速排序

快速排序（Quicksort）

快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序（Quicksort）

复杂度

算法	最好情况	平均情况	最坏情况	空间复杂度	稳定性
快速排序	O(n log n)	O(n log n)	O(n2)	O(log n)	不稳定

ES6 实现

function QuickSort(array) {
 const sort = (arr, left = 0, right = arr.length - 1) => {
  if (left >= right) {
   return array;
  }
 let i = left;
 let j = right;
 const baseVal = arr[j] ;
 while (i < j) {
  while (i < j && arr[i] <= baseVal) {
   i++;
  }
  arr[j] = arr[i] ;
  while (j > i && arr[j] >= baseVal) { 
   j--;
 }
  arr[i] = arr[j] ;
 }
 arr[j] = baseVal ;
 sort(arr, left, j-1) ;
 sort(arr, j+1, right) ;
 }
 const newArr = array.concat() ;
 sort(newArr);
 return newArr;
}

参考

• 维基百科
• 百度百科

相关阅读

JavaScript的排序算法——冒泡排序
JavaScript的排序算法——选择排序
JavaScript的排序算法——插入排序
JavaScript的排序算法——归并排序
JavaScript的排序算法——快速排序