资讯专栏INFORMATION COLUMN

面试官:快排会写吗?

UCloud / 1422人阅读

摘要:快排可以说是一道必知的常见面试题,同时也有多种实现方式。之所以使用随机快速排序而不是普通的快排。其中交换数组元素位置,打印元素的方法我就没贴了,代码太长你们也不方便看。

快排可以说是一道必知的常见面试题,同时也有多种实现方式。在这篇文章中,我使用的是随机三路快排。

之所以使用随机快速排序而不是普通的快排。是因为前者可以使得数列有序的概率降低,从而使随机快速排序平均速度是比快速排序要快的。具体的两者的性能差别可以看下这篇文章:

https://blog.csdn.net/haelang...

talk id cheap,show the code。一共 20+ 行代码,每行代码都有注释。其中交换数组元素位置,打印元素的方法我就没贴了,代码太长你们也不方便看。

PS:代码下面有执行流程图,结合代码来看比较容易理解。

public static void main(String[] args) {                                             
     // 测试数据                              
     int[] arr = new int[]{5, 3, 6, 4}; 
     // 执行快排
     quickSort(arr, 0, arr.length - 1);         
     // 打印数组元素              
     printArray(arr);                           
 }  
 
private static void quickSort(int[] arr, int l, int r) {               
     if (l < r) {                                                       
         // 随机取需要排序的数组中的一个元素和数组的最后一个元素交换,作为划分值                          
         swap(arr, l + (int) (Math.random() * (r - l + 1)), r);       
         // 得到数组元素中等于划分值的区域                                             
         int[] part = partition(arr, l, r);                             
         // 小于等于划分值的区域                                                  
         quickSort(arr, l, part[0] - 1);                                
         // 大于划分值的区域                                                    
         quickSort(arr, part[1] + 1, r);                                
     }                                                                  
 }   

private static int[] partition(int[] arr, int l, int r) {                                                                   
    // 初始化小于等于划分值区域的当前下标,默认是数组第一个元素的前一个位置                                                                                   
    int less = l - 1;                                                                                                       
    // 初始化大于划分值区域的当前下标,默认是数组最后一个元素的位置,同时也是划分值的位置,但该值并不属于大于划分值的区域,所以要在最后进行移动                                                 
    int more = r;                                                                                                           
    // 当前下标小于大于划分值区域的下标时                                                                                                    
    while (l < more) {                                                                                                      
        // 当前值比划分值小,当前值和小于等于划分值区域的右边第一个值进行交换,小于等于划分值区域右移1个下标,当前下标+1                                                         
        if (arr[l] < arr[r]) {                                                                                              
            swap(arr, l++, ++less);                                                                                         
            // 当前值比划分值大,当前值和大于划分值区域的左边第一个值进行交换,大于划分值的区域左移1个下标                                                               
        } else if (arr[l] > arr[r]) {                                                                                       
            swap(arr, l, --more);                                                                                           
            // 当前值等于划分值,当前下标+1                                                                                              
        } else {      
            // 当前下标+1                                                                                          
            l++;                                                                                                            
        }                                                                                                                   
    }                                                                                                                       
    // 将划分值和大于划分值区域中,最接近划分值区域的元素交换。至此完成所有值的区域划分                                                                             
    swap(arr, more, r);                                                                                                     
    // 返回等于划分值的区域                                                                                                           
    return new int[]{less + 1, more};                                                                                       
} 

下面我会画个流程图帮大家理解一下,测试数据和代码一样。

假设代码执行完 13 行后,测试数据的顺序依旧不变,即为 {5,3,6,4}。

接下来在执行 partition() 方法的过程中,数组元素的情况如下图所示(灵魂写手求轻喷)

好了,以上就是本文的全部内容,我们下篇文章再见,捂脸逃~

PS:本文原创发布于微信公众号「不只Java」,后台回复「Java」,送你 13 本 Java 经典电子书。公众号专注分享 Java 干货、读书笔记、成长思考

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/72160.html

相关文章

  • 前端排序算法总结;前端面试题2.0;JavaScript异步编程

    摘要:与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在,至少在被标准化的那一刻起,就支持异步编程了。然而异步编程真正发展壮大,的流行功不可没。在握手过程中,端点交换认证和密钥以建立或恢复安全会话。 1、前端 排序算法总结 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较...

    aaron 评论0 收藏0
  • 前端排序算法总结;前端面试题2.0;JavaScript异步编程

    摘要:与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在,至少在被标准化的那一刻起,就支持异步编程了。然而异步编程真正发展壮大,的流行功不可没。在握手过程中,端点交换认证和密钥以建立或恢复安全会话。 1、前端 排序算法总结 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较...

    ARGUS 评论0 收藏0
  • 前端排序算法总结;前端面试题2.0;JavaScript异步编程

    摘要:与异步编程按照维基百科上的解释独立于主控制流之外发生的事件就叫做异步。因为的存在,至少在被标准化的那一刻起,就支持异步编程了。然而异步编程真正发展壮大,的流行功不可没。在握手过程中,端点交换认证和密钥以建立或恢复安全会话。 1、前端 排序算法总结 排序算法可能是你学编程第一个学习的算法,还记得冒泡吗? 当然,排序和查找两类算法是面试的热门选项。如果你是一个会写快排的程序猿,面试官在比较...

    April 评论0 收藏0
  • 记一次腾讯霸面---前端

    摘要:客户端的浏览器根据双方同意的安全等级,建立会话密钥,然后利用网站的公钥将会话密钥加密,并传送给网站。地址必须和一个网络掩码对应使用缺一不可。网络掩码的主要作用是告诉计算机如何从地址中析取网络标识和主机标识。 霸面的是前端实习生岗位,当时听同学说前端缺人,还特意设了一个霸面区,就去溜了个弯儿,毕竟不试试,怎么知道自己有多菜呢o( ̄︶ ̄)o一面技术面,面试官关注的点一直在数据结构、算法、计...

    ralap 评论0 收藏0

发表评论

0条评论

UCloud

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<