C++中的23种算法

核心提示：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

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时，则排序完成。

实作

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 shakersort(int[]);

int main(void) {

int number[MAX] = {0};

int i;

srand(time(NULL));

16.排序法-

改良的选择排序

说明

选择排序法的概念简单，每次从未排序部份选一最小值，插入已排序部份的后端，其时间主要

花费于在整个未排序部份寻找最小值，如果能让搜寻最小值的方式加快，选择排序法的速率也

就可以加快，Heap排序法让搜寻的路径由树根至最后一个树叶，而不是整个未排序部份，因而

称之为改良的选择排序法。

解法

Heap排序法使用Heap Tree（堆积树），树是一种资料结构，而堆积树是一个二元树，也就是每

一个父节点最多只有两个子节点（关于树的详细定义还请见资料结构书籍），堆积树的父节点

若小于子节点，则称之为最小堆积（Min Heap），父节点若大于子节点，则称之为最大堆积（Max

Heap），而同一层的子节点则无需理会其大小关系，例如下面就是一个堆积树：

可以使用一维阵列来储存堆积树的所有元素与其顺序，为了计算方便，使用的起始索引是1而不

是0，索引1是树根位置，如果左子节点储存在阵列中的索引为s，则其父节点的索引为s/2，而右

子节点为s+1，就如上图所示，将上图的堆积树转换为一维阵列之后如下所示：

首先必须知道如何建立堆积树，加至堆积树的元素会先放置在最后一个树叶节点位置，然后检

查父节点是否小于子节点（最小堆积），将小的元素不断与父节点交换，直到满足堆积树的条件

为止，例如在上图的堆积加入一个元素12，则堆积树的调整方式如下所示：

建立好堆积树之后，树根一定是所有元素的最小值，您的目的就是：

将最小值取出

然后调整树为堆积树

不断重复以上的步骤，就可以达到排序的效果，最小值的取出方式是将树根与最后一个树叶节

点交换，然后切下树叶节点，重新调整树为堆积树，如下所示：

调整完毕后，树根节点又是最小值了，于是我们可以重覆这个步骤，再取出最小值，并调整树