C++中的23种算法

为堆积树，如下所示：

如此重覆步骤之后，由于使用一维阵列来储存堆积树，每一次将树叶与树根交换的动作就是将

最小值放至后端的阵列，所以最后阵列就是变为已排序的状态。

其实堆积在调整的过程中，就是一个选择的行为，每次将最小值选至树根，而选择的路径并不

是所有的元素，而是由树根至树叶的路径，因而可以加快选择的过程， 所以Heap排序法才会被

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

#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 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]);

}

}

17.快速排序法（一）

说明快速排序法（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