手写js-实现快速排序(sort)

我心飞翔 分类:javascript

前言:快速排序是一种很高效的排序方法,在很多大厂面试题中都是“熟人”,它其中用了一种高效的方法-----分治法。

核心思想

  • 取数组中的一个元素作为参照数
  • 依据这个参照数,比它大的放右边,比它小或者等于的放到左边
  • 这样就大致分了两边,然后调用自身函数递归分成两边的数组

具体步骤

依据本次实操数据

  • 首先我们写入了三个参数 s , l, r 它们分别代表 s数组 l函数执行排序最左边元素的下标,r最右边的下标。这次是直接定义了 a 代表为哨兵(参照数) let a = s[i],让数组的第一个元素的值作为参照数的值
  • 接下来就是进行比较了,定义l=i ,r=j, 方便循环,例如数组 s=[4,2,7,9,1] 那么 l=0, r=4 , a=s[l]=4 , 当s[j]=1 时 1<4,所以s[l]=s[j] 此时 s=[1,2,7,9,1] , 依旧继续 j-- ,继续比较 9>4,那么应该不移动,继续执行循环。同时左边也是 当s[i]>a 应该移到右边,如果s[i]<=a 则不移动,直到当 i=j 时停止,此时为止就完成了第一次排序 也就是把 a 作为中间值 左边都小于a 右边都大于a。
  • 但这a 的左右两边并还没有排完序,所以我们要将 a 的左右两边 分别再进行如上的排序方法排序, 这时就是运用到了 递归的思想 一层一层地去排序 ,最后再返回整个排好序的数组。

简单表示一下

image.png

一个数组从7个元素划分为两个数组都为3个元素,一直这样细分下去,直至i=j;

代码

//三个参数
const quicksort = (s,l,r) => {
    if( l<r ){
        var i = l;var j= r;
        //哨兵  参照数 a
        var a = s[l];
        
        while( i<j ){
            while( i<j && s[j] >= a) // 从右至左找小于a的值
                j--;
            if( i<j ) 
                s[i++] = s[j];
            while( i<j && s[i]<a )// 从左至右找大于a的值
                i++;
            if( i<j )
                s[j--] = s[i]; 
        }
        s[i] = a;
        // 递归a 左右两边的子数组
        quicksort(s,l,i-1);
        quicksort(s,i+1,r);
        return s   
    } 
}
var b = quicksort([7,5,1,9,13,11,3],0,6);
console.log(b);
 

优化

不知大家想到没有,我们再进行第二次排序的时候,我们继续递归的传过去的参数 l , r ,是依据a为定的,但并不是每次拿过来的数组的第一个数都是中间值的。那么很显然,选择第一个元素为参照值(专业术语叫基准元素)进行快速排序对于已经有序,或大部分有序的数组就相当吃亏了。

  • 这时候我们会考虑随机取基准元,进行快速排序,我们的做法是随机取一个元素,与第一个元素互换,并以第一个元素作为基准元,进行快速排序。
  • 当然了我们还有一种可用的三数取中作为基准元的快速排序,一般都是取第一,末尾,和中间的三个数,对这三个数进行排序,取中值作为基准元

这里实际的操作就是集中在对 s[i]= ? 来做优化的,这里就不具体提供代码

总结

在数组长度不大的情况下,可以选择插入排序,其他的排序方式

最后,很多不足之处,请各位多多指点

回复

我来回复
  • 暂无回复内容