排序

归并排序

本质是将多个序列进行合并，和快排一样也用的是分而治之的思想，并且它也是基于比较里面较快的算法且能保持稳定性的算法。

那么怎么将两个序列合并呢?(假设左右两边已经有序)

1. 开辟一个和数组一样大的辅助数组，再设定两个指针，第一个指针指向第一个序列的开头，第二个指针指向第二个序列的开头。
2. 升序的话，就判断第一个指针所指的值如果小于等于第二个指针所指的值，就把第一个指针所指的值赋值到辅助数组。
3. 如果第一个指针的所指的值大于第二个指针所指的值，就把第二个指针所指的值赋值到辅助数组
4. 重复第二步和第三步直到左右两边有一边没有数了
5. 把剩下的数复制到辅助数组

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#define N 3//设置数组的大小

void mergeSort(int *a, int low, int high);//归并排序
void merge(int *a, int low, int mid, int high);//合并两个序列

int main(int argc, char *argv[])
{
int a[N];

for ( int i = 0; i < N; i++) {
scanf("%d", a + i);
}

mergeSort(a, 0, N - 1);

for ( int i = 0; i < N; i++) {
printf("%5d", a[i]);
}

putchar('\n');

return 0;
}
void mergeSort(int *a, int low, int high)
{
int mid = low + (high - low) >> 1;

if ( low == high) {
return ;
}

mergeSort(a, low, mid);
mergeSort(a, mid + 1, high);
merge(a, low, mid, high);
}
void merge(int *a, int low, int mid, int high)
{
int *p1 = (int*)malloc(sizeof(int) * (high - low + 1));
int p = low;
int q = mid + 1;
int i = 0;

while(p <= mid && q <= high) {
if ( a[p] <= a[q]) {
p1[i++] = a[p++];
}
else {
p1[i++] = a[q++];
}
}

while( p <= mid) {
p1[i++] = a[p++];
}

while( q <= high) {
p1[i++] = a[q++];
}

for (int j = 0; j < i; j++) {
a[low + j] = p1[j];
}
}

 堆排序

堆就是一颗完全二叉树结构，完全二叉树就是按从上到下，从左到右顺序的一颗树。堆分为大根堆和小根堆。大跟堆就是每一个子树它的父节点是最大的节点，小根堆就是每一个子树它的父节点是最小的节点.那么怎么建立二叉树到数组的映射呢。

对于任何一个下标i，它的父节点是( i - 1) / 2,左孩子是 (i * 2) + 1,右孩子是(i * 2) + 2.通过公式我们可以在数组中表示一颗完全二叉树。

这就是一颗完全二叉树也是满二叉树，观察它们的下标我们发现是符合刚刚的公式的。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#define N 10
void heapSort(int *a, int size);

int main(int argc,char *argv[])
{
    int a[N];
    
    srand(time(NULL));
    
    for (int i = 0; i < N; i++) {
        a[i] = rand() % 100;
    }
    
    printf("原数组\n");
    for (int i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    putchar('\n');
    
    heapSort(a, N);
    
    for (int i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    
    return 0; 
}
void heapSort(int *a, int size)
{
    if (size == 1) {
        return;
    }
    
    int heapSize = 0;
    
    a[heapSize++] = a[0];
    
    for (int i = 1; i < N; i++) {
        int j = i;
        a[heapSize++] = a[j];
        while( a[j] > a[(j - 1) / 2] && j) {
            int t = a[j];
            a[j] = a[(j - 1) / 2];
            a[(j - 1) / 2] = t;
            j = (j - 1) / 2;
        }
    }
    
    while( heapSize != 1) {
        int t = a[0];
        int j = 0;
        int bigger = 0;
        
        a[0] = a[heapSize - 1];
        a[heapSize - 1] = t;
        heapSize--;
        
        if (heapSize == 1) {
            break;
        }
        
        if ( 2 < heapSize ) {
            bigger = a[1] > a[2]? 1: 2;
        }
        else {
            bigger = 1;
        }
        
        while( j < heapSize && a[j] < a[bigger]) {
            t = a[j];
            a[j] = a[bigger];
            a[bigger] = t;
            j = bigger;
            
            if ( (j * 2 + 1) < heapSize)  {
                if ( j * 2 + 2 < heapSize) {
                    bigger = a[j * 2 + 1] > a[j * 2 + 2]? (j * 2 + 1): (j * 2 + 2);
                }
                else {
                    bigger = j * 2 + 1;
                }
            }
            else {
                break;
            }
        }
    }
}

这是自己写的代码没有进行优化有点丑

图

BFS

DFS