有学有练才叫学习:学而不思则罔,思而不学则殆:学而不习,纸上谈兵,习而不进,画地为牢!

js快速排序(快速排序的JS实现)

javascript 炮渣日记 2周前 (11-18) 14次浏览 已收录 0个评论 扫描二维码

关于快排需要知道一个概念: 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 < 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完完整整的看完了陈姥姥的数据结构,没想到前几天面试的时候算法竟然生疏到这个程度了,哎,以后每天都得看一遍这个。

喜欢 (0)
炮渣日记
关于作者:
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址