|
快排在我心中始终有一个尤其的位置，无论是各样笔试面试常考的排序算法，还是在现实实践中最快的排序算法，快排始终在一个尤其的位置上。
算法的平均时间繁杂度： n *logn
最坏的时间繁杂度：n^2，出现的情景：完全逆序的序列
关于快排需要晓得一个概念： pivot，通常把这个译作准元（还是主元来着）。pivot，排序时按照pivot的值，将大于他的值移动到他的右边，少于他的值移动到他的左边。和归并排序同样快排亦是分而治之思想的一种典型应用。
在这个算法中首要会用到一个交换元素的办法： function swap( i , j ,arr){
if ( i == j ) return;
lettemp = 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 < right ){
let pivot = selectPivot( left , right ,arr );
let i = left, j = right - 1;
for( ;; ){
while( arr[++i] < pivot ){};while( arr[ --j ] > pivot ){};
if( i < j ){
swap( i,j,arr )
}else{
break;
}
}
if( i < right - 1 )
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完完整整的看完了陈姥姥的数据结构，没想到前几天面试的时候算法竟然生疏到这个程度了，哎，以后每日都得看一遍这个。
| 
发表于 2024-10-10 04:21:20