📄 shellsort.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>Shell 排序法 - 改良的插入排序</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: Shell 排序法 - 改良的插入排序</a></h1>
<h2>说明</h2>
插入排序法由未排序的后半部前端取出一个值，插入已排序前半部的适当位置，概念简单但速度不快。<br>
<br>
排序要加快的基本原则之一，是让后一次的排序进行时，尽量利用前一次排序后的结果，以加快排序的速度，Shell排序法即是基于此一概念来改良插入排序法。<br>
<h2>解法</h2>
Shell排序法最初是D.L Shell于1959所提出，假设要排序的元素有n个，则每次进行插入排序时并不是所有的元素同时进行时，而是取一段间隔。<br>
<br>
Shell首先将间隔设定为n/2，然后跳跃进行插入排序，再来将间隔n/4，跳跃进行排序动作，再来间隔设定为n/8、n/16，直到间隔为1之后的最
后一次排序终止，由于上一次的排序动作都会将固定间隔内的元素排序好，所以当间隔越来越小时，某些元素位于正确位置的机率越高，因此最后几次的排序动作将
可以大幅减低。<br>
<br>
举个例子来说，假设有一未排序的数字如右：89 12 65 97 61 81 27 2 61 98<br>
<br>
数字的总数共有10个，所以第一次我们将间隔设定为10 / 2 = 5，此时我们对间隔为5的数字进行排序，如下所示：<br>
<div style="text-align: center;"><img style="width: 225px; height: 95px;" alt="Shell 排序" title="Shell 排序" src="images/shellSort-1.jpg"><br>
<div style="text-align: left;"></div>
<div style="text-align: left;">画线连结的部份表示 要一起进行排序的部份，再来将间隔设定为5 / 2的商，也就是2，则第二次的插入排序对象如下所示：<br>
<div style="text-align: center;"><img style="width: 229px; height: 74px;" alt="Shell 排序" title="Shell 排序" src="images/shellSort-2.jpg"><br>
</div>
<br>
再来间隔设定为2 / 2 = 1，此时就是单纯的插入排序了，由于大部份的元素都已大致排序过了，所以最后一次的插入排序几乎没作什么排序动作了： <br>
<div style="text-align: center;"><img style="width: 225px; height: 66px;" alt="Shell 排序" title="Shell 排序" src="images/shellSort-3.jpg"><br>
<br>
</div>
将间隔设定为n / 2是D.L
Shell最初所提出，在教科书中使用这个间隔比较好说明，然而Shell排序法的关键在于间隔的选定，例如Sedgewick证明选用以下的间隔可以加
快Shell排序法的速度： <br>
<div style="text-align: center;"><img style="width: 184px; height: 94px;" alt="Shell 排序" title="Shell 排序" src="images/shellSort-4.jpg"><br>
</div>
其中4*(2<sup>j</sup>)<sup>2</sup> + 3*(2<sup>j</sup>) + 1不可超过元素总数n值，使用上式找出j后代入4*(2<sup>j</sup>)<sup>2</sup> + 3*(2<sup>j</sup>) + 1求得第一个间隔，然后将2<sup>j</sup>除以2代入求得第二个间隔，再来依此类推。 <br>
<br>
后来还有人证明有其它的间隔选定法可以将Shell排序法的速度再加快；另外Shell排序法的概念也可以用来改良气泡排序法。<br>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br>#include <time.h> <br>#define MAX 10 <br>#define SWAP(x,y) {int t; t = x; x = y; y = t;} <br><br>void shellsort(int[]); <br><br>int main(void) { <br> int number[MAX] = {0}; <br> int i; <br><br> srand(time(NULL)); <br><br> printf("排序前："); <br> for(i = 0; i < MAX; i++) { <br> number[i] = rand() % 100; <br> printf("%d ", number[i]); <br> } <br><br> shellsort(number); <br><br> return 0; <br>} <br><br>void shellsort(int number[]) { <br> int i, j, k, gap, t; <br><br> gap = MAX / 2; <br><br> while(gap > 0) { <br> for(k = 0; k < gap; k++) { <br> for(i = k+gap; i < MAX; i+=gap) { <br> for(j = i - gap; j >= k; j-=gap) { <br> if(number[j] > number[j+gap]) { <br> SWAP(number[j], number[j+gap]); <br> } <br> else <br> break; <br> } <br> } <br> } <br><br> printf("\ngap = %d：", gap); <br> for(i = 0; i < MAX; i++) <br> printf("%d ", number[i]); <br> printf("\n"); <br><br> gap /= 2; <br> } <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>public class ShellSort {<br> public static void sort(int[] number) {<br> int gap = number.length / 2; <br><br> while(gap > 0) { <br> for(int k = 0; k < gap; k++) { <br> for(int i = k+gap; i < number.length; i+=gap) { <br> for(int j = i - gap; j >= k; j-=gap) { <br> if(number[j] > number[j+gap]) { <br> swap(number, j, j+gap); <br> } <br> else <br> break; <br> } <br> } <br> } <br><br> gap /= 2; <br> } <br> }<br> <br> private static void swap(int[] number, int i, int j) {<br> int t; <br> t = number[i]; <br> number[i] = number[j]; <br> number[j] = t;<br> }<br>}</pre>
<br>
</div>
</div>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -