📄 ds10.2.3.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>数 据 结 构</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>
<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">
<p:colorscheme
colors="#0000FF,#FFFFFF,#000000,#FFCC66,#00FFFF,#3366FF,#FF0033,#FFFF00"/>
<p align="center"><b><font size="6" color="#FFFF00">10.2.4 希尔排序</font></b></p>
<p class="MsoNormal"><span style="mso-spacerun: yes"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""> </span></span><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span><span style="mso-spacerun: yes"> </span>希尔排序又称缩小增量排序，是1959年由D.L.Shell提出来的，较前述几种插入排序方法有较大的改进。<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 size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>直接插入排序算法简单，在n值较小时，效率比较高，在n值很大时，若序列按关键码基本有序，效率依然较高，其时间效率可提高到O(n)。希尔排序即是从这两点出发，给出插入排序的改进方法。<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""><b><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman"><font size="5" color="#FFFFFF"> </font><font size="5" color="#FFFF00">
</font></span><font size="5" color="#FFFF00">希尔排序方法：</font><font size="5" color="#FFFFFF"><o:p>
</o:p>
</font></b></span></p>
<p class="MsoNormal"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>1. 选择一个步长序列t<sub>1</sub>，t<sub>2</sub>，…，t<sub>k</sub>，其中t<sub>i</sub>>t<sub>i-1</sub>，t<sub>k</sub>=1；<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 size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>2. 按步长序列个数k，对序列进行k趟排序；<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 size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>3. 每趟排序，根据对应的步长t<sub>i</sub>，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅步长因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。</b></font></span><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:
"Times New Roman""><font size="5" color="#FFFFFF"><b> <o:p>
</o:p>
</b></font></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>【例<span lang="EN-US">10.4】待排序列为
:</span></b></font></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><b><span lang="EN-US"><font color="#FFFFFF" size="4">
39，80，76，41，13，29，50，78，30，11，100，7，<u>41</u>，86。<o:p>
</o:p>
</font></span></b></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font color="#FFFFFF"><b><font size="5">步长因子分别取</font></b></font><span lang="EN-US"><font color="#FFFFFF"><b><font size="5">5、3、1，则排序过程如下：</font></b></font><o:p>
</o:p>
</span></span></p>
<p class="MsoNormal" style="text-indent:21.25pt"><b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font color="#FFFFFF" size="4">p=5<span style="mso-tab-count: 2; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FFFF00">39</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#00FF00">80</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FF00FF">76</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FF9900">41</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FF0000">13</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FFFF00">29</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#00FF00">50</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FF00FF">78<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FF9900">30</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FF0000">11</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FFFF00">100</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#00FF00">7</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span><u></u></font><u><font size="4" color="#FF00FF">41</font></u><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FF9900">86</font></span></b><font color="#FFFFFF"><b><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></b><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><b><font size="5"><o:p>
</o:p>
</font></b></span></font></p>
<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"><font size="5" color="#FFFFFF">子序列分别为:</font></span></b>
<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 color="#FFFFFF" size="4">{39,29,100}，{80,50,7}，{76,78,41}，{41,30,86}，{13，11}。</font></span></b></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>第一趟排序结果：<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
<p class="MsoNormal" style="text-indent:21.25pt" align="left"><span lang="EN-US"><b><span style="font-family: 宋体; mso-hansi-font-family: Times New Roman"><font color="#FFFFFF" size="4"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman"">p=3<span style="mso-tab-count: 2; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></span></font><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="4" color="#FFFF00">29</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#00FF00">7</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span><u>41</u><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FFFF00">30</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#00FF00">11</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>39<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FFFF00">50</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#00FF00">76</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>41<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FFFF00">13</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#00FF00">100</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>80<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#FFFF00">78</font><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span></font><font size="4" color="#00FF00">86</font></span><font color="#FFFFFF" size="4"><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><o:p>
</o:p>
</span></font></span></b></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>子序列分别为</b></font></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><b><span lang="EN-US"><font color="#FFFFFF" size="4">{29,30,50,13,78}，{7,11,76,100,86}，{<u>41</u>,39,41,80}。<o:p>
</o:p>
</font></span></b></span></p>
<p class="MsoNormal"><span style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF"><b>第二趟排序结果：<span lang="EN-US"><o:p>
</o:p>
</span></b></font></span></p>
<p class="MsoNormal" style="text-indent:21.25pt"><span lang="EN-US" style="font-family:宋体;mso-hansi-font-family:"Times New Roman""><b><font color="#FFFFFF" size="4">p=1<span style="mso-tab-count: 2; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>13<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>7<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>39<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>29<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>11<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span><u>41</u><span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>30<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>76<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>41<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
</span>50<span style="mso-spacerun: yes; font-family: 宋体; mso-hansi-font-family: Times New Roman">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -