📄 ds10.3.htm
字号:
</span>65<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>96<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span><u>49</u><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>55<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>74<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span><o:p>
</o:p>
</font></span></b></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><font color="#FFFFFF" size="5"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></span></b></font><img border="0" src="ds10.318.gif" width="18" height="46"><font color="#FFFFFF" size="5"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></span></b></font><img border="0" src="ds10.318.gif" width="18" height="46"><font color="#FFFFFF" size="5"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><o:p>
</o:p>
</span></b></font></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><b><font color="#FFFFFF"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font></span></font><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF">low<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>high<o:p>
</o:p>
</font></span></b></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font color="#FFFFFF" size="5"><b>第三次搜索交换<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF">从high向前搜索小于r[0].key的记录，得到结果<o:p>
</o:p>
</font></span></b></p>
<p class="MsoNormal"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF">27<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>14<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>38<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>8<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>□<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>65<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>96<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span><u>49</u><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>55<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>74<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span><o:p>
</o:p>
</font></span></b></p>
<p class="MsoNormal"><font color="#FFFFFF" size="5"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></span></b></font><img border="0" src="ds10.318.gif" width="18" height="46"><font color="#FFFFFF" size="5"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><o:p>
</o:p>
</span></b></font></p>
<p class="MsoNormal"><b><font color="#FFFFFF"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font></span></font><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF">low<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>high<o:p>
</o:p>
</font></span></b></p>
<p class="MsoNormal"><b><font color="#FFFFFF"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman"> </span></font></span></font></b><font color="#FFFFFF" size="5"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman"">low=high，划分结束，填入支点记录<o:p>
</o:p>
</span></b></font></p>
<b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font size="5" color="#FFFFFF">27<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>14<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>38<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>8<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="5" color="#FFFF00">49</font><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>65<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>96<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span><u>49</u><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>55<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>74</font></span></b>
<p class="MsoNormal"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFF00"><b>【</b></font></span><font size="5"><b><font color="#FFFF00"><span style="font-family:黑体;
mso-ascii-font-family:"Times New Roman"">效率分析</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">】</span></font><font color="#FFFFFF"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><o:p>
</o:p>
</span></font></b></font></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5"><b><font color="#FFFF00">空间效率：</font><font color="#FFFFFF">快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log<sub>2</sub>n)，即树的高度；在最坏情况下，即二叉树是一个单链，为O(n)。<o:p>
</o:p>
</font></b></font></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5"><b><font color="#FFFF00">时间效率：</font><font color="#FFFFFF">在n个记录的待排序列中，一次划分需要约n次关键码比较，时效为O(n)，若设T(n)为对n个记录的待排序列进行快速排序所需时间。<o:p>
</o:p>
</font></b></font></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5"><b><font color="#FFFFFF">理想情况下：每次划分，正好将分成两个等长的子序列，则<o:p>
</o:p>
</font></b></font></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font color="#FFFFFF" size="5"><b> <span style="mso-spacerun: yes">
</span>T(n)≤cn+2T(n/2)<span style="mso-spacerun: yes">
</span>c是一个常数<o:p>
</o:p>
</b></font></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><span style="mso-spacerun: yes"><font size="5"><b><font color="#FFFFFF">
</font></b></font></span><font size="5"><b><font color="#FFFFFF">≤cn+2(cn/2+2T(n/4))=2cn+4T(n/4)<o:p>
</o:p>
</font></b></font></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><span style="mso-spacerun: yes"><font size="5"><b><font color="#FFFFFF">
</font></b></font></span><font size="5"><b><font color="#FFFFFF">≤2cn+4(cn/4+T(n/8))=3cn+8T(n/8)<o:p>
</o:p>
</font></b></font></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><span style="mso-spacerun: yes"><font size="5"><b><font color="#FFFFFF">
</font></b></font></span><font size="5"><b><font color="#FFFFFF">······<o:p>
</o:p>
</font></b></font></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font color="#FFFFFF" size="5"><b><span style="mso-spacerun: yes">
</span>≤cnlog<sub>2</sub>n+nT(1)=O(nlog<sub>2</sub>n)</b></font><font color="#FFFFFF" size="5"><b> <o:p>
</o:p>
</b></font></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font color="#FFFFFF" size="5"><b>最坏情况下:即每次划分,只得到一个子序列,时效为O(n<sup>2</sup>)。<o:p>
</o:p>
</b></font></span></p>
<font color="#FFFFFF" size="5"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
快速排序是通常被认为在同数量级（<span lang="EN-US">O</span></span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">(nlog<sub>2</sub>n)</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。</span></b></font>
<p class="MsoNormal" align="center"> </p>
<p class="MsoNormal" align="center"><b><font size="5"><a href="ds10.htm"><font color="#FFFF00">返回</font></a></font></b></p>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -