C++中的23种算法

并不是所有的元素同时进行时，而是取一段间隔。

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 <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;

}

}

15.排序法-

改良的气泡排序

说明

请看看之前介绍过的气泡排序法：

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浮出