堆排序（logn(n-1) ）

1、首先将无需数组构造成一个大根堆（新插入的数据与其父结点比较）
2、固定一个最大值，将剩余的数重新构造成一个大根堆，重复这样的过程

include

void display(int array[], int size) {
for (int i = 0; i < size; i++) {
printf(“%d “, array[i]);
}
printf(“\n”);
}

void swap(int array[], int x, int y) {
int key = array[x];
array[x] = array[y];
array[y] = key;
}

// 从大到小排序
// void Down(int array[], int i, int n) {
// int child = 2 i + 1;
// int key = array[i];
// while (child < n) {
// if (child + 1 < n && array[child] > array[child + 1]) {
// child++;
// }
// if (key > array[child]) {
// swap(array, i, child);
// i = child;
// } else {
// break;
// }
// child = child 2 + 1;
// }
// }

// 从小到大排序
void Down(int array[], int i, int n) { // 最后结果就是大顶堆
int parent = i; // 父节点下标
int child = 2 i + 1; // 子节点下标
while (child < n) {
if (child + 1 < n && array[child] < array[child + 1]) { // 判断子节点那个大，大的与父节点比较
child++;
}
if (array[parent] < array[child]) { // 判断父节点是否小于子节点
swap(array, parent, child); // 交换父节点和子节点
parent = child; // 子节点下标 赋给 父节点下标
}
child = child 2 + 1; // 换行，比较下面的父节点和子节点
}
}

void BuildHeap(int array[], int size) {
for (int i = size / 2 - 1; i >= 0; i—) { // 倒数第二排开始, 创建大顶堆，必须从下往上比较
Down(array, i, size); // 否则有的不符合大顶堆定义
}
}

void HeapSort(int array[], int size) {
printf(“初始化数组：”);
BuildHeap(array, size); // 初始化堆
display(array, size); // 查看初始化结果
for (int i = size - 1; i > 0; i—) {
swap(array, 0, i); // 交换顶点和第 i 个数据
// 因为只有array[0]改变，其它都符合大顶堆的定义，所以可以从上往下重新建立
Down(array, 0, i); // 重新建立大顶堆

    printf("排序的数组：");<br />        display(array, size);<br />    }<br />}

int main() {
int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 10};
int size = sizeof(array) / sizeof(int);

// 打印数据<br />    printf("%d \n", size);<br />    printf("排序前数组：");<br />    display(array, size);<br />    HeapSort(array, size);

return 0;<br />}

最小生成树

一个有N个点的图，边一定是大于等于N-1条的。图的最小生成树，就是在这些边中选择N-1条出来，连接所有的N个点。这N-1条边的边权之和是所有方案中最小的。

1、Prim算法

每次循环都将一个蓝点u变为白点，并且此蓝点u与白点相连的最小边权min[u]还是当前所有蓝点中最小的。这样相当于向生成树中添加了n-1次最小的边，最后得到的一定是最小生成树。

Kruskal算法

将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个点都是孤立的，分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了n-1条边为止。