做网站做注册登录的难点深圳市龙岗区

做网站做注册登录的难点,深圳市龙岗区,搜狗竞价推广,防水自己如何建设网站快速排序#xff08;Quick Sort#xff09;的“死穴”#xff0c;也就是它的最坏情况。简单来说#xff0c;它的意思是#xff1a;如果你运气不好#xff0c;选的基准值#xff08;Pivot#xff09;太极端#xff0c;快速排序就会变得非常慢#xff0c;慢得像冒泡排序…快速排序Quick Sort的“死穴”也就是它的最坏情况。简单来说它的意思是如果你运气不好选的基准值Pivot太极端快速排序就会变得非常慢慢得像冒泡排序一样。我来把这张图里的“行话”翻译成大白话配合具体的例子演示。1. 快速排序的理想状态 vs. 糟糕状态快速排序的核心思想是“分治”分而治之。理想情况选一个基准值比如中间大小的数它能把数组一分为二左边一半右边一半。每轮都减半速度极快。糟糕情况PPT里的情况选的基准值是最大或最小的数。它没能把数组切开只是把最边上的一个切下来了剩下的一大坨还在那一侧。2. 结合 PPT 中的例子演示PPT 里举了两个例子一个是倒序的一个是正序的。通常教科书里的快速排序默认取第一个元素作为基准值Pivot。例子 A倒序数组(90, 85, 79, 74, ...)假设我们总是取第一个数做基准Pivot 90。第一轮基准90比较剩下的所有数 (85, 79, 74...) 都比 90 小。划分结果左边子序列(85, 79, 74, 68, 50, 46)也就是除了90以外的所有人右边子序列()空空如也因为没人比90大代价我们忙活了一整轮只把90这一个数排好了位置。第二轮处理左边那一堆基准85现在的第一个比较剩下的 (79, 74...) 都比 85 小。划分结果又是一边倒。85 右边是空的左边还是那一堆。结论这就像切西瓜原本想一刀两半结果你每一刀都只切下来薄薄的一层皮。你要切 N 次才能切完。例子 B正序数组(46, 50, 68, ...)道理是一样的。基准46。比较剩下的所有数 (50, 68...) 都比 46 大。划分结果左边子序列()空的右边子序列(50, 68, 74, ...)所有人都在右边3. 为什么 PPT 说“退化为冒泡排序”你看上面的过程快速排序最坏情况第一轮搞定 1 个数90第二轮搞定 1 个数85第三轮搞定 1 个数79...冒泡排序第一轮冒出一个最大值搞定1个第二轮冒出第二大值搞定1个...它们的工作效率变成一模一样的了正常快排复杂度O(nlogn) 类似树形结构层数少退化后的复杂度O(n2) 类似链表结构层数变成了 N 层非常慢4. 树形图解对比为了让你直观感受区别我画个图理想的快速排序平衡树每次都运气好选到中间值两边均匀。代码段graph TD A[50] -- B[25] A -- C[75] B -- D[10] B -- E[40] C -- F[60] C -- G[90]PPT 里的最坏情况歪脖子树每次都选到最大或最小有序数组选第一个数就会这样。代码段graph TD A[90] -- B[85] B -- C[79] C -- D[74] D -- E[68] E -- F[...]看下面这棵“歪脖子树”明显比上面的“平衡树”要深得多走的路更长所以效率极低。总结 PPT 的红框结论“快速排序不适于对原本有序或基本有序的记录序列进行排序。”这句话的意思是 如果你拿到一个数组发现它已经是排好序的或者倒序的这时候如果你还傻乎乎地用“取第一个元素当基准”的快速排序去排它那就是自寻死路效率最低。那怎么办实际工程中为了避免这种尴尬我们通常随机选基准或者三数取中取头、中、尾三个数的中间值当基准这样就能避开这种“死穴”了。