快排在我心中一直有一个特别的位置，无论是各种笔试面试常考的排序算法，还是在现实实践中最快的排序算法，快排始终在一个特别的位置上。
算法的平均时间复杂度： n *logn
最坏的时间复杂度：n^2，发生的情景：完全逆序的序列
关于快排需要知道一个概念： pivot，一般把这个译作准元(还是主元来着)。pivot，排序时根据pivot的值，将大于他的值移动到他的右边，小于他的值移动到他的左边。和归并排序一样快排也是分而治之思想的一种典型应用。
在这个算法中首先会用到一个交换元素的方法：function swap( i , j ,arr){
if ( i == j ) return;
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
然后选准元，选准元的方式可有很多方法，我们使用一般的方式，就是比较一个序列最左边，中间元素，以及最右边元素的大小，选取三个元素的中位数作为准元，最后将中位数和倒数第二个元素交换，返回准元：function selectPivot(left,right,arr){
let mid = Math.floor (( left + right )/ 2);
if( arr[left] > arr[right] ){
swap(left,right,arr)
};
if( arr[left] > arr[mid] ){
swap( left, mid,arr )
}
if( arr[ mid ] > arr[right] ){
swap( mid,right,arr )
}
swap( mid,right-1,arr );
return arr[ right - 1 ]
}
有了 pivot之后，就可以开始主体部分了，将小于等于主元的元素放到他左边，大于等于主元的元素放到他右边，分治的时候我们会使用到两个指针，分别从数组的(起始位置+1)和 (pivot-1)的位置扫描元素，扫描完毕之后，递归排序pivot前面的部分和后面的部分：function quickSort(arr,left = 0,right){
left = left ,right = right !== undefined ? right : arr.length - 1;
if( left
let pivot = selectPivot( left , right ,arr );
let i = left, j = right - 1;
for( ;; ){
while( arr[++i]
while( arr[ --j ] > pivot ){};
if( i
swap( i,j,arr )
}else{
break;
}
}
if( i
swap( i,right-1,arr );
quickSort( arr,left, i - 1 );
quickSort( arr,i+1,right )
}else{
return 'quickSorttings';
}
}
以上，是看完浙大陈姥姥的数据结构之后自己用js重写的，与c语言版本的相比多了几处改动，之前完全仿照c语言版的写过一版快排，但是在一定数量级之后这个东西就开始出现bug了。这次重写之后bug解决了，出现bug的原因在16行，在交换两个元素的时候，假如 i = right -1= pivot的位置，此时是不需要交换的，假如再交换，实际上是把主元给交换到比他之后的位置了，因此完全扰乱了算法的序列。
后记：记得去年还在中国大学mooc完完整整的看完了陈姥姥的数据结构，没想到前几天面试的时候算法竟然生疏到这个程度了，哎，以后每天都得看一遍这个。
转播
