ShellSort

Algorithm Gossip: Shell 排序法 - 改良的插入排序

说明

插入排序法由未排序的后半部前端取出一个值，插入已排序前半部的适当位置，概念简单但速度不快。 排序要加快的基本原则之一，是让后一次的排序进行时，尽量利用前一次排序后的结果，以加快排序的速度，Shell排序法即是基于此一概念来改良插入排序法。

解法

Shell排序法最初是D.L Shell于1959所提出，假设要排序的元素有n个，则每次进行插入排序时并不是所有的元素同时进行时，而是取一段间隔。 Shell首先将间隔设定为n/2，然后跳跃进行插入排序，再来将间隔n/4，跳跃进行排序动作，再来间隔设定为n/8、n/16，直到间隔为1之后的最 后一次排序终止，由于上一次的排序动作都会将固定间隔内的元素排序好，所以当间隔越来越小时，某些元素位于正确位置的机率越高，因此最后几次的排序动作将 可以大幅减低。 举个例子来说，假设有一未排序的数字如右：89 12 65 97 61 81 27 2 61 98 数字的总数共有10个，所以第一次我们将间隔设定为10 / 2 = 5，此时我们对间隔为5的数字进行排序，如下所示： 画线连结的部份表示 要一起进行排序的部份，再来将间隔设定为5 / 2的商，也就是2，则第二次的插入排序对象如下所示： 再来间隔设定为2 / 2 = 1，此时就是单纯的插入排序了，由于大部份的元素都已大致排序过了，所以最后一次的插入排序几乎没作什么排序动作了： 将间隔设定为n / 2是D.L Shell最初所提出，在教科书中使用这个间隔比较好说明，然而Shell排序法的关键在于间隔的选定，例如Sedgewick证明选用以下的间隔可以加 快Shell排序法的速度： 其中4/(2j)2 + 3/(2j) + 1不可超过元素总数n值，使用上式找出j后代入4/(2j)2 + 3/(2j) + 1求得第一个间隔，然后将2j除以2代入求得第二个间隔，再来依此类推。 后来还有人证明有其它的间隔选定法可以将Shell排序法的速度再加快；另外Shell排序法的概念也可以用来改良气泡排序法。

实作

• C /#include /#include /#include /#define MAX 10 /#define SWAP(x,y) {int t; t = x; x = y; y = t;} void shellsort(int[]); int main(void) { int number[MAX] = {0}; int i; srand(time(NULL)); printf("排序前："); for(i = 0; i < MAX; i++) { number[i] = rand() % 100; printf("%d ", number[i]); } shellsort(number); return 0; } void shellsort(int number[]) { int i, j, k, gap, t; gap = MAX / 2; while(gap > 0) { for(k = 0; k < gap; k++) { for(i = k+gap; i < MAX; i+=gap) { for(j = i - gap; j >= k; j-=gap) { if(number[j] > number[j+gap]) { SWAP(number[j], number[j+gap]); } else break; } } } printf("\ngap = %d：", gap); for(i = 0; i < MAX; i++) printf("%d ", number[i]); printf("\n"); gap /= 2; } }

• Java public class ShellSort { public static void sort(int[] number) { int gap = number.length / 2; while(gap > 0) { for(int k = 0; k < gap; k++) { for(int i = k+gap; i < number.length; i+=gap) { for(int j = i - gap; j >= k; j-=gap) { if(number[j] > number[j+gap]) { swap(number, j, j+gap); } else break; } } } gap /= 2; } } private static void swap(int[] number, int i, int j) { int t; t = number[i]; number[i] = number[j]; number[j] = t; } }

StackByArray

Algorithm Gossip: 堆叠 - 使用阵列实作

说明

堆叠是一种先进后出的资料结构，就如同您将书本放入箱子，最先放进的书本在最后才能拿出来，所有资料的加入与删除都在堆叠顶端完成。堆叠的使用很广，递回 就是一种堆叠，在之前介绍中序式转后序式时，也使用到堆叠的结构。 堆叠可以使用多种方式实作，其中使用阵列是最简单的方法，也最不受使用的程式语言所限制。

解法

堆叠最重要的就是记录顶端的位置，尤其是在堆叠空间固定的情况下，必须注意堆叠已满或已空的判断，当使用阵列实作堆叠时尤其重要。 堆叠的基本操作有五项：建立堆叠、传回顶端元素、加入元素至堆叠、删除元素至堆叠、显示堆叠所有内容。为了方便，加入一个测试堆叠是否为空的方法，详 细的演算并不难，直接列出程式实作。

实作

• C /#include /#include /#define MAX 10 int creates(int[]); // 建立堆叠 int isEmpty(int); // 堆叠已空 int stacktop(int[], int); // 传回顶端元素 int add(int[], int, int); // 插入元素 int delete(int[], int); // 删除元素 void list(int[], int); // 显示所有内容 int main(void) { int stack[MAX]; int top; int input, select; top = creates(stack); while(1) { printf("\n\n请输入选项(-1结束)："); printf("\n(1)插入值至堆叠"); printf("\n(2)显示堆叠顶端"); printf("\n(3)删除顶端值"); printf("\n(4)显示所有内容"); printf("\n$c>"); scanf("%d", &select); if(select == -1) break; switch(select) { case 1: printf("\n输入值："); scanf("%d", &input); top = add(stack, top, input); break; case 2: printf("\n顶端值：%d", stacktop(stack, top)); break; case 3: top = delete(stack, top); break; case 4: list(stack, top); break; default: printf("\n选项错误！"); } } printf("\n"); return 0; } // 以下为堆叠操作的实作 int creates(int stack[]) { int i; for(i = 0; i < MAX; i++) stack[i] = 0; return -1; } int isEmpty(int top) { return (top == -1); } int stacktop(int stack[], int top) { return stack[top]; } int add(int stack[], int top, int item) { int t = top; if(t >= MAX-1) { printf("\n堆叠已满！"); return t; } stack[++t] = item; return t; } int delete(int stack[], int top) { int t = top; if(isEmpty(t)) { printf("\n堆叠已空！"); return t; } return --t; } void list(int stack[], int top) { int t = top; printf("\n堆叠内容："); while(!isEmpty(t)) { printf("%d ", stack[t]); t--; } }

ShuffleCard

Algorithm Gossip: 洗扑克牌（乱数排列）

说明

洗扑克牌的原理其实与乱数排列是相同的，都是将一组数字（例如1～N）打乱重新排列，只不过洗扑克牌多了一个花色判断的动作而已。

解法

初学者通常会直接想到，随机产生1～N的乱数并将之存入阵列中，后来产生的乱数存入阵列前必须先检查阵列中是否已有重复的数字，如果有这个数就不存入，再重新产生下一个数，运气不好的话，重复的次数就会很多，程式的执行速度就很慢了，这不是一个好方法。 以1～52的乱数排列为例好了，可以将阵列先依序由1到52填入，然后使用一个回圈走访阵列，并随机产生1～52的乱数，将产生的乱数当作索引取出阵列值，并与目前阵列走访到的值相交换，如此就不用担心乱数重复的问题了，阵列走访完毕后，所有的数字也就重新排列了。 至于如何判断花色？这只是除法的问题而已，取商数判断花色，取余数判断数字，您可以直接看程式比较清楚。

实作

• C /#include /#include /#include /#define N 52 int main(void) { int poker[N + 1]; int i, j, tmp, remain; // 初始化阵列 for(i = 1; i <= N; i++) poker[i] = i; srand(time(0)); // 洗牌 for(i = 1; i <= N; i++) { j = rand() % 52 + 1; tmp = poker[i]; poker[i] = poker[j]; poker[j] = tmp; } for(i = 1; i <= N; i++) { // 判断花色 switch((poker[i]-1) / 13) { case 0: printf("桃"); break; case 1: printf("心"); break; case 2: printf("砖"); break; case 3: printf("梅"); break; } // 扑克牌数字 remain = poker[i] % 13; switch(remain) { case 0: printf("K "); break; case 12: printf("Q "); break; case 11: printf("J "); break; default: printf("%d ", remain); break; } if(i % 13 == 0) printf("\n"); } return 0; }

• Java public class ShuffleCard { public static void main(String args[]) { final int N = 52; int[] poker = new int[N + 1]; // 初始化阵列 for(int i = 1; i <= N; i++) poker[i] = i; // 洗牌 for(int i = 1; i <= N; i++) { int j = (int) (Math.random() /* N); if(j == 0) j = 1; int tmp = poker[i]; poker[i] = poker[j]; poker[j] = tmp; } for(int i = 1; i <= N; i++) { // 判断花色 switch((poker[i]-1) / 13) { case 0: System.out.print("桃"); break; case 1: System.out.print("心"); break; case 2: System.out.print("砖"); break; case 3: System.out.print("梅"); break; } // 扑克牌数字 int remain = poker[i] % 13; switch(remain) { case 0: System.out.print("K "); break; case 12: System.out.print("Q "); break; case 11: System.out.print("J "); break; default: System.out.print(remain + " "); break; } if(i % 13 == 0) System.out.println(""); } } }

StackByLink

Algorithm Gossip: 堆叠 - 使用链结实作（C 语言动态记忆体宣告）

说明

使用阵列实作堆叠，会受到阵列大小必须事先宣告好的限制，我们可以使用链结（link）的方式来实作堆叠，以动态记忆体宣告的方式来新增每一个元素。

解法

链结（link）是由节点组成，每一个节点储存资料之外，还储存下一个节点的位置，如下图所示： 对堆叠而言，加入新节点与删除节点的方法如下图所示： 新增节点： 删除节点： 链结也可以使用阵列来实作，不过在这边我们以动态记忆体宣告的方式来进行，在C语言中，这是实作链结的基本作法，可以不受阵列大小必须先行宣告的限制，所以使用链结实作堆叠时，就不会有堆叠已满的问题（除了记忆体用尽之外）。 上面的图说只是个示意，在演算的时候，会需要一些暂存变数来协助节点新增与删除时的连结更动，请直接参照以下的程式实作。

实作

• C /#include /#include struct node { int data; struct node /next; }; typedef struct node getnode; getnode/ creates(void); // 建立堆叠 int isEmpty(getnode/); // 堆叠已空 int stacktop(getnode/); // 传回顶端元素 getnode/ add(getnode/, int); // 新增元素 getnode/ delete(getnode/); // 删除元素 void list(getnode/); // 显示所有内容 int main(void) { getnode/ sTop; int input, select; sTop = creates(); while(1) { printf("\n\n请输入选项(-1结束)："); printf("\n(1)插入值至堆叠"); printf("\n(2)显示堆叠顶端"); printf("\n(3)删除顶端值"); printf("\n(4)显示所有内容"); printf("\n$c>"); scanf("%d", &select); if(select == -1) break; switch(select) { case 1: printf("\n输入值："); scanf("%d", &input); sTop = add(sTop, input); break; case 2: printf("\n顶端值：%d", stacktop(sTop)); break; case 3: sTop = delete(sTop); break; case 4: list(sTop); break; default: printf("\n选项错误！"); } } printf("\n"); return 0; } getnode/ creates() { return NULL; } int isEmpty(getnode/ top) { return (top == NULL); } int stacktop(getnode/ top) { return top->data; } getnode/ add(getnode/ top, int item) { getnode/ newnode; newnode = (getnode/) malloc(sizeof(getnode)); if(newnode == NULL) { printf("\n记忆体配置失败！"); exit(1); } newnode->data = item; newnode->next = top; top = newnode; return top; } getnode/ delete(getnode/ top) { getnode/ tmpnode; tmpnode = top; if(tmpnode == NULL) { printf("\n堆叠已空！"); return NULL; } top = top->next; free(tmpnode); return top; } void list(getnode/ top) { getnode/ tmpnode; tmpnode = top; printf("\n堆叠内容："); while(tmpnode != NULL) { printf("%d ", tmpnode->data); tmpnode = tmpnode->next; } }

StackByObject

Algorithm Gossip: 堆叠 - 使用 Java 作物件封装

说明

如果您使用C++或Java等支援物件导向的语言来实作堆叠，您可以使用类别的方式来包括堆叠的功能，将所有的堆叠操作由堆叠物件来处理，一旦包装完成，则使用堆叠物件的时候，只要呼叫加入、删除等方法，而无需处理堆叠的top或判断是否为空等细节。

解法

使用C++与使用Java来作类别包装其实是类似的，在这边我们使用Java实作，因为它的语法看来较简洁；Java虽然没有指标，但可以使用参考（Reference）来达到链结的效果，一个节点的类别包装方式如下： class Node { private int data; // 节点资料 private Node next; // 下一个节点位置 public void setData(int data); // 节点资料 public void setNext(Node next); // 下一个节点位置 public int getData(); // 传回节点资料 public Node getNext(); // 传回下一个节点位置 }

其中next是个物件参考名称，它可以用来参考至（指向）下一个节点物件的记忆体位置，而堆叠类别可以如下包装： class Stack { private Node top; // 堆叠顶端 private String name; // 只是个名称 // 利用建构子建立堆叠 public Stack(); public Stack(String name); // 插入资料至顶端 public void add(int data); // 传回顶端资料 public int printTop(); // 删除顶端资料 public void del(); // 列出堆叠内容 public void list(); }

利用物件导向来包装资料结构，虽然在设计时需要花较多的心思，但设计完成之后，日后呼叫使用就简单了，以后您只要注意主程式的逻辑设计就可以了。

实作

• Java import java.io./*; // 节点 class Node { private int data; // 节点资料 private Node next; // 下一个节点位置 public void setData(int data) { // 节点资料 this.data = data; } public void setNext(Node next) { // 下一个节点位置 this.next = next; } public int getData() { // 传回节点资料 return data; } public Node getNext() { // 传回下一个节点位置 return next; } } // 堆叠 class Stack { private Node top; private String name; // 只是个名称 public Stack() { this("list"); } // 利用建构子建立堆叠 public Stack(String name) { this.name = name; top = null; } // 插入资料至顶端 public void add(int data) { Node newNode = new Node(); newNode.setData(data); newNode.setNext(top); top = newNode; } // 传回顶端资料 public int printTop() { return top.getData(); } // 删除顶端资料 public void del() { Node tmpNode; tmpNode = top; if(tmpNode == null) { System.out.println("\n堆叠已空！"); return; } top = top.getNext(); tmpNode = null; } // 列出堆叠内容 public void list() { Node tmpNode; tmpNode = top; System.out.print("\n堆叠内容："); while(tmpNode != null) { System.out.print(tmpNode.getData() + " "); tmpNode = tmpNode.getNext(); } } } public class StackShow { public static void main(String[] args) throws IOException { int input, select; BufferedReader buf; buf = new BufferedReader( new InputStreamReader(System.in)); Stack s1 = new Stack("堆叠测试"); while(true) { System.out.print("\n\n请输入选项(-1结束)："); System.out.print("\n(1)插入值至堆叠"); System.out.print("\n(2)显示堆叠顶端"); System.out.print("\n(3)删除顶端值"); System.out.print("\n(4)显示所有内容"); System.out.print("\n$c>"); select = Integer.parseInt(buf.readLine()); if(select == -1) break; switch(select) { case 1: System.out.print("\n输入值："); input = Integer.parseInt(buf.readLine()); s1.add(input); break; case 2: System.out.print("\n顶端值：" + s1.printTop()); break; case 3: s1.del(); break; case 4: s1.list(); break; default: System.out.print("\n选项错误！"); } } System.out.println(""); } }