HeapSort

Algorithm Gossip: Heap 排序法 - 改良的选择排序

说明

选择排序法的概念简单，每次从未排序部份选一最小值，插入已排序部份的后端，其时间主要花费于在整个未排序部份寻找最小值，如果能让搜寻最小值的方式加 快，选择排序法的速率也就可以加快，Heap排序法让搜寻的路径由树根至最后一个树叶，而不是整个未排序部份，因而称之为改良的选择排序法。

解法

Heap排序法使用Heap Tree（堆积树），树是一种资料结构，而堆积树是一个二元树，也就是每一个父节点最多只有两个子节点（关于树的详细定义还请见资料结构书籍），堆积树的 父节点若小于子节点，则称之为最小堆积（Min Heap），父节点若大于子节点，则称之为最大堆积（Max Heap），而同一层的子节点则无需理会其大小关系，例如下面就是一个堆积树： 可以使用一维阵列来储存堆积树的所有元素与其顺序，为了计算方便，使用的起始索引是1而不是0，索引1是树根位置，如果左子节点储存在阵列中的索引为s，则其父节点的索引为s/2，而右子节点为s+1，就如上图所示，将上图的堆积树转换为一维阵列之后如下所示： 首先必须知道如何建立堆积树，加至堆积树的元素会先放置在最后一个树叶节点位置，然后检查父节点是否小于子节点（最小堆积），将小的元素不断与父节点交换，直到满足堆积树的条件为止，例如在上图的堆积加入一个元素12，则堆积树的调整方式如下所示： 建立好堆积树之后，树根一定是所有元素的最小值，您的目的就是：

1. 将最小值取出
2. 然后调整树为堆积树 不断重复以上的步骤，就可以达到排序的效果，最小值的取出方式是将树根与最后一个树叶节点交换，然后切下树叶节点，重新调整树为堆积树，如下所示： 调整完毕后，树根节点又是最小值了，于是我们可以重覆这个步骤，再取出最小值，并调整树为堆积树，如下所示： 如此重覆步骤之后，由于使用一维阵列来储存堆积树，每一次将树叶与树根交换的动作就是将最小值放至后端的阵列，所以最后阵列就是变为已排序的状态。 其实堆积在调整的过程中，就是一个选择的行为，每次将最小值选至树根，而选择的路径并不是所有的元素，而是由树根至树叶的路径，因而可以加快选择的过程， 所以Heap排序法才会被称之为改良的选择排序法。

实作

• C /#include /#include /#include /#define MAX 10 /#define SWAP(x,y) {int t; t = x; x = y; y = t;} void createheap(int[]); void heapsort(int[]); int main(void) { int number[MAX+1] = {-1}; int i, num; srand(time(NULL)); printf("排序前："); for(i = 1; i <= MAX; i++) { number[i] = rand() % 100; printf("%d ", number[i]); } printf("\n建立堆积树："); createheap(number); for(i = 1; i <= MAX; i++) printf("%d ", number[i]); printf("\n"); heapsort(number); printf("\n"); return 0; } void createheap(int number[]) { int i, s, p; int heap[MAX+1] = {-1}; for(i = 1; i <= MAX; i++) { heap[i] = number[i]; s = i; p = i / 2; while(s >= 2 && heap[p] > heap[s]) { SWAP(heap[p], heap[s]); s = p; p = s / 2; } } for(i = 1; i <= MAX; i++) number[i] = heap[i]; } void heapsort(int number[]) { int i, m, p, s; m = MAX; while(m > 1) { SWAP(number[1], number[m]); m--; p = 1; s = 2 / p; while(s <= m) { if(s < m && number[s+1] < number[s]) s++; if(number[p] <= number[s]) break; SWAP(number[p], number[s]); p = s; s = 2 / p; } printf("\n排序中："); for(i = MAX; i > 0; i--) printf("%d ", number[i]); } }

• Java public class HeapSort { public static void sort(int[] number) { int[] tmp = new int[number.length + 1]; // 配合说明，使用一个有遍移的暂存阵列 for(int i = 1; i < tmp.length; i++) { tmp[i] = number[i-1]; } createHeap(tmp); int m = number.length; while(m > 1) { swap(tmp, 1, m); m--; int p = 1; int s = 2 / p; while(s <= m) { if(s < m && tmp[s+1] < tmp[s]) s++; if(tmp[p] <= tmp[s]) break; swap(tmp, p, s); p = s; s = 2 / p; } } // 这边将排序好的暂存阵列设定回原阵列 for(int i = 0; i < number.length; i++) { number[i] = tmp[i+1]; } } private static void createHeap(int[] tmp) { int[] heap = new int[tmp.length]; for(int i = 0; i < heap.length; i++) heap[i] = -1; for(int i = 1; i < heap.length; i++) { heap[i] = tmp[i]; int s = i; int p = i / 2; while(s >= 2 && heap[p] > heap[s]) { swap(heap, p, s); s = p; p = s / 2; } } for(int i = 1; i < tmp.length; i++) tmp[i] = heap[i]; } private static void swap(int[] number, int i, int j) { int t; t = number[i]; number[i] = number[j]; number[j] = t; } }

KnightTour

Algorithm Gossip: 骑士走棋盘

说明

骑士旅游（Knight tour）在十八世纪初倍受数学家与拼图迷的注意，它什么时候被提出已不可考，骑士的走法为西洋棋的走法，骑士可以由任一个位置出发，它要如何走完[所有的位置？

解法

骑士的走法，基本上可以使用递回来解决，但是纯綷的递回在维度大时相当没有效率，一个聪明的解法由J.C. Warnsdorff在1823年提出，简单的说，先将最难的位置走完，接下来的路就宽广了，骑士所要走的下一步，“为下一步再选择时，所能走的步数最少 的一步。”，使用这个方法，在不使用递回的情况下，可以有较高的机率找出走法（找不到走法的机会也是有的）。

演算法

FOR(m = 2; m <= 总步数; m++) [ 测试下一步可以走的八个方向，记录可停留的格数count。 IF(count == 0) [ 游历失败 ] ELSE IF(count == 1) [ 下一步只有一个可能 ] ELSE [ 找出下一步的出路最少的格子 如果出路值相同，则选第一个遇到的出路。 ] 走最少出路的格子，记录骑士的新位置。 ]

实作

• C /#include int board[8][8] = {0}; int main(void) { int startx, starty; int i, j; printf("输入起始点："); scanf("%d %d", &startx, &starty); if(travel(startx, starty)) { printf("游历完成！\n"); } else { printf("游历失败！\n"); } for(i = 0; i < 8; i++) { for(j = 0; j < 8; j++) { printf("%2d ", board[i][j]); } putchar('\n'); } return 0; } int travel(int x, int y) { // 对应骑士可走的八个方向 int ktmove1[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; int ktmove2[8] = {1, 2, 2, 1, -1, -2, -2, -1}; // 测试下一步的出路 int nexti[8] = {0}; int nextj[8] = {0}; // 记录出路的个数 int exists[8] = {0}; int i, j, k, m, l; int tmpi, tmpj; int count, min, tmp; i = x; j = y; board[i][j] = 1; for(m = 2; m <= 64; m++) { for(l = 0; l < 8; l++) { exists[l] = 0; } l = 0; // 试探八个方向 for(k = 0; k < 8; k++) { tmpi = i + ktmove1[k]; tmpj = j + ktmove2[k]; // 如果是边界了，不可走 if(tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7) continue; // 如果这个方向可走，记录下来 if(board[tmpi][tmpj] == 0) { nexti[l] = tmpi; nextj[l] = tmpj; // 可走的方向加一个 l++; } } count = l; // 如果可走的方向为0个，返回 if(count == 0) { return 0; } else if(count == 1) { // 只有一个可走的方向 // 所以直接是最少出路的方向 min = 0; } else { // 找出下一个位置的出路数 for(l = 0; l < count; l++) { for(k = 0; k < 8; k++) { tmpi = nexti[l] + ktmove1[k]; tmpj = nextj[l] + ktmove2[k]; if(tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7) { continue; } if(board[tmpi][tmpj] == 0) exists[l]++; } } tmp = exists[0]; min = 0; // 从可走的方向中寻找最少出路的方向 for(l = 1; l < count; l++) { if(exists[l] < tmp) { tmp = exists[l]; min = l; } } } // 走最少出路的方向 i = nexti[min]; j = nextj[min]; board[i][j] = m; } return 1; }

• Java public class Knight { public boolean travel(int startX, int startY, int[][] board) { // 对应骑士可走的八个方向 int[] ktmove1 = {-2, -1, 1, 2, 2, 1, -1, -2}; int[] ktmove2 = {1, 2, 2, 1, -1, -2, -2, -1}; // 下一步出路的位置 int[] nexti = new int[board.length]; int[] nextj = new int[board.length]; // 记录出路的个数 int[] exists = new int[board.length]; int x = startX; int y = startY; board[x][y] = 1; for(int m = 2; m <= Math.pow(board.length, 2); m++) { for(int k = 0; k < board.length; k++) { exists[k] = 0; } int count = 0; // 试探八个方向 for(int k = 0; k < board.length; k++) { int tmpi = x + ktmove1[k]; int tmpj = y + ktmove2[k]; // 如果是边界了，不可走 if(tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7) { continue; } // 如果这个方向可走，记录下来 if(board[tmpi][tmpj] == 0) { nexti[count] = tmpi; nextj[count] = tmpj; // 可走的方向加一个 count++; } } int min = -1; if(count == 0) { return false; } else if(count == 1) { min = 0; } else { // 找出下一个位置的出路数 for(int l = 0; l < count; l++) { for(int k = 0; k < board.length; k++) { int tmpi = nexti[l] + ktmove1[k]; int tmpj = nextj[l] + ktmove2[k]; if(tmpi < 0 || tmpj < 0 || tmpi > 7 || tmpj > 7) { continue; } if(board[tmpi][tmpj] == 0) exists[l]++; } } int tmp = exists[0]; min = 0; // 从可走的方向中寻找最少出路的方向 for(int l = 1; l < count; l++) { if(exists[l] < tmp) { tmp = exists[l]; min = l; } } } // 走最少出路的方向 x = nexti[min]; y = nextj[min]; board[x][y] = m; } return true; } public static void main(String[] args) { int[][] board = new int[8][8]; Knight knight = new Knight(); if(knight.travel( Integer.parseInt(args[0]), Integer.parseInt(args[1]), board)) { System.out.println("游历完成！"); } else { System.out.println("游历失败！"); } for(int i = 0; i < board.length; i++) { for(int j = 0; j < board[0].length; j++) { if(board[i][j] < 10) { System.out.print(" " + board[i][j]); } else { System.out.print(board[i][j]); } System.out.print(" "); } System.out.println(); } } }

JosephusProblem

Algorithm Gossip: 约瑟夫问题（Josephus Problem）

说明

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人 开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

解法

约瑟夫问题可用代数分析来求解，将这个问题扩大好了，假设现在您与m个朋友不幸参与了这个游戏，您要如何保护您与您的朋友？只要画两个圆圈就可以让自己与朋友免于死亡游戏，这两个圆圈内圈是排列顺序，而外圈是自杀顺序，如下图所示： 使用程式来求解的话，只要将阵列当作环状来处理就可以了，在阵列中由计数1开始，每找到三个无资料区就填入一个计数，直而计数达41为止，然后将阵列由索引1开始列出，就可以得知每个位置的自杀顺序，这就是约瑟夫排列，41个人而报数3的约琴夫排列如下所示： 14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23 由上可知，最后一个自杀的是在第31个位置，而倒数第二个自杀的要排在第16个位置，之前的人都死光了，所以他们也就不知道约琴夫与他的朋友并没有遵守游戏规则了。

实作

• C /#include /#include /#define N 41 /#define M 3 int main(void) { int man[N] = {0}; int count = 1; int i = 0, pos = -1; int alive = 0; while(count <= N) { do { pos = (pos+1) % N; // 环状处理 if(man[pos] == 0) i++; if(i == M) { // 报数为3了 i = 0; break; } } while(1); man[pos] = count; count++; } printf("\n约琴夫排列："); for(i = 0; i < N; i++) printf("%d ", man[i]); printf("\n\n您想要救多少人？"); scanf("%d", &alive); printf("\nL表示这%d人要放的位置：\n", alive); for(i = 0; i < N; i++) { if(man[i] > alive) printf("D"); else printf("L"); if((i+1) % 5 == 0) printf(" "); } printf("\n"); return 0; }

• Java public class Josephus { public static int[] arrayOfJosephus( int number, int per) { int[] man = new int[number]; for(int count = 1, i = 0, pos = -1; count <= number; count++) { do { pos = (pos+1) % number; // 环状处理 if(man[pos] == 0) i++; if(i == per) { // 报数为3了 i = 0; break; } } while(true); man[pos] = count; } return man; } public static void main(String[] args) { int[] man = Josephus.arrayOfJosephus(41, 3); int alive = 3; System.out.println("约琴夫排列："); for(int i = 0; i < 41; i++) System.out.print(man[i] + " "); System.out.println("\nL表示3个存活的人要放的位置："); for(int i = 0; i < 41; i++) { if(man[i] > alive) System.out.print("D"); else System.out.print("L"); if((i+1) % 5 == 0) System.out.print(" "); } System.out.println(); } }

QuickSort2

Algorithm Gossip: 快速排序法（二）

说明

在 快速排序法（一） 中，每次将最左边的元素设为轴，而之前曾经说过，快速排序法的加速在于轴的选择，在这个例子中，只将轴设定为中间的元素，依这个元素作基准进行比较，这可以增加快速排序法的效率。

解法

在这个例子中，取中间的元素s作比较，同样的先得右找比s大的索引 i，然后找比s小的索引 j，只要两边的索引还没有交会，就交换 i 与 j 的元素值，这次不用再进行轴的交换了，因为在寻找交换的过程中，轴位置的元素也会参与交换的动作，例如： 41　24　76　11　45　64　21　69　19　36 首先left为0，right为9，(left+right)/2 = 4（取整数的商），所以轴为索引4的位置，比较的元素是45，您往右找比45大的，往左找比45小的进行交换：

• 41　24　76/　11　[45]　64　21　69　19　/36
• 41　24　36　11　45/　64　21　69　19/　76
• 41　24　36　11　19　64/　21/　69　45　76
• [41　24　36　11　19　21]　[64　69　45　76] 完成以上之后，再初别对左边括号与右边括号的部份进行递回，如此就可以完成排序的目的。

实作

• C /#include /#include /#include /#define MAX 10 /#define SWAP(x,y) {int t; t = x; x = y; y = t;} void quicksort(int[], int, int); int main(void) { int number[MAX] = {0}; int i, num; srand(time(NULL)); printf("排序前："); for(i = 0; i < MAX; i++) { number[i] = rand() % 100; printf("%d ", number[i]); } quicksort(number, 0, MAX-1); printf("\n排序后："); for(i = 0; i < MAX; i++) printf("%d ", number[i]); printf("\n"); return 0; } void quicksort(int number[], int left, int right) { int i, j, s; if(left < right) { s = number[(left+right)/2]; i = left - 1; j = right + 1; while(1) { while(number[++i] < s) ; // 向右找 while(number[--j] > s) ; // 向左找 if(i >= j) break; SWAP(number[i], number[j]); } quicksort(number, left, i-1); // 对左边进行递回 quicksort(number, j+1, right); // 对右边进行递回 } }

• Java public class QuickSort { public static void sort(int[] number) { sort(number, 0, number.length-1); } private static void sort(int[] number, int left, int right) { if(left < right) { int s = number[(left+right)/2]; int i = left - 1; int j = right + 1; while(true) { // 向右找 while(number[++i] < s) ; // 向左找 while(number[--j] > s) ; if(i >= j) break; swap(number, i, j); } sort(number, left, i-1); // 对左边进行递回 sort(number, j+1, right); // 对右边进行递回 } } private static void swap(int[] number, int i, int j) { int t; t = number[i]; number[i] = number[j]; number[j] = t; } }

QuickSort1

Algorithm Gossip: 快速排序法（一）

说明

快速排序法（quick sort）是目前所公认最快的排序方法之一（视解题的对象而定），虽然快速排序法在最差状况下可以达O(n2)，但是在多数的情况下，快速排序法的效率表现是相当不错的。 快速排序法的基本精神是在数列中找出适当的轴心，然后将数列一分为二，分别对左边与右边数列进行排序，而影响快速排序法效率的正是轴心的选择。 这边所介绍的第一个快速排序法版本，是在多数的教科书上所提及的版本，因为它最容易理解，也最符合轴心分割与左右进行排序的概念，适合对初学者进行讲解。

解法

这边所介绍的快速演算如下：

1. 将最左边的数设定为轴，并记录其值为 s 回圈处理：

2. 令索引 i 从数列左方往右方找，直到找到大于 s 的数

3. 令索引 j 从数列右方往左方找，直到找到小于 s 的数
4. 如果 i >= j，则离开回圈
5. 如果 i < j，则交换索引i与j两处的值
6. 将左侧的轴与 j 进行交换
7. 对轴左边进行递回
8. 对轴右边进行递回 透过以下演算法，则轴左边的值都会小于s，轴右边的值都会大于s，如此再对轴左右两边进行递回，就可以对完成排序的目的，例如下面的实例，/*表示要交换的数，[]表示轴：

• [41]　24　76/　11　45　64　21　69　19　36/
• [41]　24　36　11　45/　64　21　69　19/　76
• [41]　24　36　11　19　64/　21/　69　45　76
• [41]　24　36　11　19　21　64　69　45　76
• 21　24　36　11　19　[41]　64　69　45　76 在上面的例子中，41左边的值都比它小，而右边的值都比它大，如此左右再进行递回至排序完成。

实作

• C /#include /#include /#include /#define MAX 10 /#define SWAP(x,y) {int t; t = x; x = y; y = t;} void quicksort(int[], int, int); int main(void) { int number[MAX] = {0}; int i, num; srand(time(NULL)); printf("排序前："); for(i = 0; i < MAX; i++) { number[i] = rand() % 100; printf("%d ", number[i]); } quicksort(number, 0, MAX-1); printf("\n排序后："); for(i = 0; i < MAX; i++) printf("%d ", number[i]); printf("\n"); return 0; } void quicksort(int number[], int left, int right) { int i, j, s; if(left < right) { s = number[left]; i = left; j = right + 1; while(1) { // 向右找 while(i + 1 < MAX && number[++i] < s) ; // 向左找 while(j -1 > -1 && number[--j] > s) ; if(i >= j) break; SWAP(number[i], number[j]); } number[left] = number[j]; number[j] = s; quicksort(number, left, j-1); // 对左边进行递回 quicksort(number, j+1, right); // 对右边进行递回 } }

• Java public class QuickSort { public static void sort(int[] number) { sort(number, 0, number.length-1); } private static void sort(int[] number, int left, int right) { if(left < right) { int s = number[left]; int i = left; int j = right + 1; while(true) { // 向右找 while(i + 1 < number.length && number[++i] < s) ; // 向左找 while(j -1 > -1 && number[--j] > s) ; if(i >= j) break; swap(number, i, j); } number[left] = number[j]; number[j] = s; sort(number, left, j-1); // 对左边进行递回 sort(number, j+1, right); // 对右边进行递回 } } private static void swap(int[] number, int i, int j) { int t; t = number[i]; number[i] = number[j]; number[j] = t; } }