34.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排序法的概念也可以用来改良气泡排序法。
#include <stdio.h> #include <stdlib.h> #include <time.h> #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; } }
35.Algorithm Gossip: Shaker 排序法 - 改良的气泡排序
说明
请看看之前介绍过的气泡排序法：
for(i = 0; i < MAX-1 && flag == 1; i++) { flag = 0; for(j = 0; j < MAX-i-1; j++) { if(number[j+1] < number[j]) { SWAP(number[j+1], number[j]); flag = 1; } } }
事实上这个气泡排序法已经不是单纯的气泡排序了，它使用了旗标与右端左移两个方法来改进排序的效能，而Shaker排序法使用到后面这个观念进一步改良气泡排序法。
解法
在上面的气泡排序法中，交换的动作并不会一直进行至阵列的最后一个，而是会进行至MAX-i-1，所以排序的过程中，阵列右方排序好的元素会一直增加，使得左边排序的次数逐渐减少，如我们的例子所示：
排序前：95 27 90 49 80 58 6 9 18 50
27 90 49 80 58 6 9 18 50 [95] 95浮出
27 49 80 58 6 9 18 50 [90 95] 90浮出
27 49 58 6 9 18 50 [80 90 95] 80浮出
27 49 6 9 18 50 [58 80 90 95] ......
27 6 9 18 49 [50 58 80 90 95] ......
6 9 18 27 [49 50 58 80 90 95] ......
6 9 18 [27 49 50 58 80 90 95]
方括号括住的部份表示已排序完毕，Shaker排序使用了这个概念，如果让左边的元素也具有这样的性质，让左右两边的元素都能先排序完成，如此未排序的元素会集中在中间，由于左右两边同时排序，中间未排序的部份将会很快的减少。
方法就在于气泡排序的双向进行，先让气泡排序由左向右进行，再来让气泡排序由右往左进行，如此完成一次排序的动作，而您必须使用left与right两个旗标来记录左右两端已排序的元素位置。
一个排序的例子如下所示：
排序前：45 19 77 81 13 28 18 19 77 11
往右排序：19 45 77 13 28 18 19 77 11 [81]
向左排序：[11] 19 45 77 13 28 18 19 77 [81]
往右排序：[11] 19 45 13 28 18 19 [77 77 81]
向左排序：[11 13] 19 45 18 28 19 [77 77 81]
往右排序：[11 13] 19 18 28 19 [45 77 77 81]
向左排序：[11 13 18] 19 19 28 [45 77 77 81]
往右排序：[11 13 18] 19 19 [28 45 77 77 81]
向左排序：[11 13 18 19 19] [28 45 77 77 81]
如上所示，括号中表示左右两边已排序完成的部份，当left > right时，则排序完成。
#include <stdio.h> #include <stdlib.h> #include <time.h> #define MAX 10 #define SWAP(x,y) {int t; t = x; x = y; y = t;} void shakerSort(int[]); int main(void) { srand(time(NULL)); int number[MAX] = {0}; printf("排序前："); int i; for(i = 0; i < MAX; i++) { number[i] = rand() % 100; printf("%d ", number[i]); } shakerSort(number); printf("\n排序後："); for(i = 0; i < MAX; i++) { printf("%d ", number[i]); } return 0; } void shakerSort(int number[]) { int left = 0, right = MAX - 1, shift = 0; while(left < right) { // 向右進行氣泡排序 int i; for(i = left; i < right; i++) { if(number[i] > number[i+1]) { SWAP(number[i], number[i+1]); shift = i; } } right = shift; // 向左進行氣泡排序 int k; for(k = right; k > left; k--) { if(number[k] < number[k-1]) { SWAP(number[k], number[k-1]); shift = k; } } left = shift; } }
37.Algorithm Gossip: 快速排序法（一）
说明
快速排序法（quick sort）是目前所公认最快的排序方法之一（视解题的对象而定），虽然快速排序法在最差状况下可以达O(n2)，但是在多数的情况下，快速排序法的效率表现是相当不错的。
快速排序法的基本精神是在数列中找出适当的轴心，然后将数列一分为二，分别对左边与右边数列进行排序，而影响快速排序法效率的正是轴心的选择。
这边所介绍的第一个快速排序法版本，是在多数的教科书上所提及的版本，因为它最容易理解，也最符合轴心分割与左右进行排序的概念，适合对初学者进行讲解。
解法
这边所介绍的快速演算如下：将最左边的数设定为轴，并记录其值为 s
回圈处理：
令索引 i 从数列左方往右方找，直到找到大于 s 的数
令索引 j 从数列左右方往左方找，直到找到小于 s 的数
如果 i >= j，则离开回圈
如果 i < j，则交换索引i与j两处的值
将左侧的轴与 j 进行交换
对轴左边进行递回
对轴右边进行递回
透过以下算法，则轴左边的值都会小于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左边的值都比它小，而右边的值都比它大，如此左右再进行递回至排序完成。
#include <stdio.h> #include <stdlib.h> #include <time.h> #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 < number.length && 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); // 对右边进行递回 } }
38.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]
完成以上之后，再初别对左边括号与右边括号的部份进行递回，如此就可以完成排序的目的。
#include <stdio.h> #include <stdlib.h> #include <time.h> #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); // 对右边进行递回 } }
39.Algorithm Gossip: 快速排序法（三）
说明
之前说过轴的选择是快速排序法的效率关键之一，在这边的快速排序法的轴选择方式更加快了快速排序法的效率，它是来自算法名书 Introduction to Algorithms 之中。
解法
先说明这个快速排序法的概念，它以最右边（或最左边）的值s作比较的标准，将整个数列分为三个部份，一个是小于s的部份，一个是大于s的部份，一个是未处理的部份，如下所示 ：
在排序的过程中，i 与 j 都会不断的往右进行比较与交换，最后数列会变为以下的状态：
然后将s的值置于中间，接下来就以相同的步骤会左右两边的数列进行排序的动作，如下所示：
整个演算的过程，直接摘录书中的伪码来作说明：
QUICKSORT(A, p, r)
if p < r
then q <- PARTITION(A, p, r)
QUICKSORT(A, p, q-1)
QUICKSORT(A, q+1, r)
end QUICKSORT
PARTITION(A, p, r)
x <- A[r]
i <- p-1
for j <- p to r-1
do if A[j] <= x
then i <- i+1
exchange A[i]<->A[j]
exchange A[i+1]<->A[r]
return i+1
end PARTITION
一个实际例子的演算如下所示：
#include <stdio.h> #include <stdlib.h> #include <time.h> #define MAX 10 #define SWAP(x,y) {int t; t = x; x = y; y = t;} int partition(int[], int, int); 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; } int partition(int number[], int left, int right) { int i, j, s; s = number[right]; i = left - 1; for(j = left; j < right; j++) { if(number[j] <= s) { i++; SWAP(number[i], number[j]); } } SWAP(number[i+1], number[right]); return i+1; } void quicksort(int number[], int left, int right) { int q; if(left < right) { q = partition(number, left, right); quicksort(number, left, q-1); quicksort(number, q+1, right); } }
40.Algorithm Gossip: 合并排序法
说明
之前所介绍的排序法都是在同一个阵列中的排序，考虑今日有两笔或两笔以上的资料，它可能是不同阵列中的资料，或是不同档案中的资料，如何为它们进行排序？
解法
可以使用合并排序法，合并排序法基本是将两笔已排序的资料合并并进行排序，如果所读入的资料尚未排序，可以先利用其它的排序方式来处理这两笔资料，然后再将排序好的这两笔资料合并。
有人问道，如果两笔资料本身就无排序顺序，何不将所有的资料读入，再一次进行排序？排序的精神是尽量利用资料已排序的部份，来加快排序的效率，小笔资料的 排序较为快速，如果小笔资料排序完成之后，再合并处理时，因为两笔资料都有排序了，所有在合并排序时会比单纯读入所有的资料再一次排序来的有效率。
那么可不可以直接使用合并排序法本身来处理整个排序的动作？而不动用到其它的排序方式？答案是肯定的，只要将所有的数字不断的分为两个等分，直到最后剩一个数字为止，然后再反过来不断的合并，就如下图所示：
不过基本上分割又会花去额外的时间，不如使用其它较好的排序法来排序小笔资料，再使用合并排序来的有效率。
下面这个程序范例，我们使用快速排序法来处理小笔资料排序，然后再使用合并排序法处理合并的动作。
#include <stdio.h> #include <stdlib.h> #include <time.h> #define MAX1 10 #define MAX2 10 #define SWAP(x,y) {int t; t = x; x = y; y = t;} int partition(int[], int, int); void quicksort(int[], int, int); void mergesort(int[], int, int[], int, int[]); int main(void) { int number1[MAX1] = {0}; int number2[MAX1] = {0}; int number3[MAX1+MAX2] = {0}; int i, num; srand(time(NULL)); printf("排序前："); printf("\nnumber1[]："); for(i = 0; i < MAX1; i++) { number1[i] = rand() % 100; printf("%d ", number1[i]); } printf("\nnumber2[]："); for(i = 0; i < MAX2; i++) { number2[i] = rand() % 100; printf("%d ", number2[i]); } // 先排序两笔资料 quicksort(number1, 0, MAX1-1); quicksort(number2, 0, MAX2-1); printf("\n排序后："); printf("\nnumber1[]："); for(i = 0; i < MAX1; i++) printf("%d ", number1[i]); printf("\nnumber2[]："); for(i = 0; i < MAX2; i++) printf("%d ", number2[i]); // 合并排序 mergesort(number1, MAX1, number2, MAX2, number3); printf("\n合并后："); for(i = 0; i < MAX1+MAX2; i++) printf("%d ", number3[i]); printf("\n"); return 0; } int partition(int number[], int left, int right) { int i, j, s; s = number[right]; i = left - 1; for(j = left; j < right; j++) { if(number[j] <= s) { i++; SWAP(number[i], number[j]); } } SWAP(number[i+1], number[right]); return i+1; } void quicksort(int number[], int left, int right) { int q; if(left < right) { q = partition(number, left, right); quicksort(number, left, q-1); quicksort(number, q+1, right); } } void mergesort(int number1[], int M, int number2[], int N, int number3[]) { int i = 0, j = 0, k = 0; while(i < M && j < N) { if(number1[i] <= number2[j]) number3[k++] = number1[i++]; else number3[k++] = number2[j++]; } while(i < M) number3[k++] = number1[i++]; while(j < N) number3[k++] = number2[j++]; }
41.Algorithm Gossip: 基数排序法
说明
在之前所介绍过的排序方法，都是属于「比较性」的排序法，也就是每次排序时 ，都是比较整个键值的大小以进行排序。
这边所要介绍的「基数排序法」（radix sort）则是属于「分配式排序」（distribution sort），基数排序法会使用到「桶子」（bucket），顾名思义，它是透过键值的部份信息，将要排序的元素分配至某些「桶」中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。
解法
基数排序的方式可以采用LSD（Least sgnificant digital）或MSD（Most sgnificant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
以LSD为例，假设原来有一串数值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
81 |
65 |
39 |
|||||||
|
43 |
14 |
55 |
28 |
||||||
|
93 |
|||||||||
|
22 |
73 |
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配，这次是根据十位数来分配：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
28 |
39 |
||||||||
|
14 |
22 |
43 |
55 |
65 |
73 |
81 |
93 |
接下来将这些桶子中的数值重新串接起来，成为以下的数列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演 算方式则都相同.
#include <stdio.h> #include <stdlib.h> void radixSort(int[]); int main(void) { int data[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81}; printf("\n排序前: "); int i; for(i = 0; i < 10; i++) printf("%d ", data[i]); putchar('\n'); radixSort(data); printf("\n排序後: "); for(i = 0; i < 10; i++) printf("%d ", data[i]); return 0; } void radixSort(int data[]) { int temp[10][10] = {0}; int order[10] = {0}; int n = 1; while(n <= 10) { int i; for(i = 0; i < 10; i++) { int lsd = ((data[i] / n) % 10); temp[lsd][order[lsd]] = data[i]; order[lsd]++; } // 重新排列 int k = 0; for(i = 0; i < 10; i++) { if(order[i] != 0) { int j; for(j = 0; j < order[i]; j++, k++) { data[k] = temp[i][j]; } } order[i] = 0; } n *= 10; } }