插入排序、希尔排序、堆排序、归并排序 --c语言实现

逐渐添加中....

#include <stdio.h>
#include <stdlib.h>
#define LeftChild(i) (2 * (i) + 1)
#define FatalError(str) fprintf(stderr, "%s\n", str), exit(1);

void IntertionSort(int data[], int n);
void ShellSort(int data[], int n);
void HeapSort(int data[], int n);
void PercDown(int data[], int i, int n);
void Swap(int *a, int *b);
void MergeSort(int DataArray[], int n);
void MSort(int DataArray[], int TmpArray[], int Left, int Right);
void Merge(int DataArray[], int TmpArray[], int Left, int Center, int Right);

int main()
{
    int n;
    int data[] = {1, 5, 6, 2, 44, 7, 34, 67, 66};
    // IntertionSort(data, sizeof(data) / sizeof(int));
    // ShellSort(data, sizeof(data) / sizeof(int));
    // HeapSort(data, sizeof(data) / sizeof(int));
    MergeSort(data, sizeof(data) / sizeof(int));

    for (n = 0; n < sizeof(data) / sizeof(int); n++)
    {
        printf("%d\n", data[n]);
    }
}

// 插入排序 O(N²)
void IntertionSort(int data[], int n)
{
    int k, j;
    for (k = 1; k < n; k++)
    {
        int tmp = data[k];
        for (j = k; j > 0 && data[j - 1] > tmp; j--)
        {
            data[j] = data[j - 1];
        }
        data[j] = tmp;
    }
}

// 希尔排序 O(N²)
void ShellSort(int data[], int n)
{
    int i, j, increment, tmp;
    for (increment = n / 2; increment > 0; increment /= 2)
    {
        for (i = increment; i < n; i++)
        {
            tmp = data[i];
            for (j = i; j >= increment; j -= increment)
            {
                if (tmp < data[j - increment])
                {
                    data[j] = data[j - increment];
                }
                else
                {
                    break;
                }
            }
            data[j] = tmp;
        }
    }
}

// 堆排序 复杂度:NlogN - O(N)
void HeapSort(int data[], int n)
{
    int i;
    for (i = n / 2; i >= 0; i--)
    {
        PercDown(data, i, n);
    }
    for (i = n - 1; i >= 0; i--)
    {
        Swap(&data[0], &data[i]);
        PercDown(data, 0, i);
    }
}
// 节点上虑
void PercDown(int data[], int i, int n)
{
    int Tmp;
    int Child;
    for (Tmp = data[i]; LeftChild(i) < n; i = Child)
    {
        Child = LeftChild(i);
        if (Child != n - 1 && data[Child + 1] > data[Child])
        {
            Child++;
        }
        if (Tmp < data[Child])
        {
            data[i] = data[Child];
        }
        else
        {
            break;
        }
    }
    data[i] = Tmp;
}
void Swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

// 归并排序 复杂度 O(NlogN)
void MSort(int DataArray[], int TmpArray[], int Left, int Right)
{
    int Center;

    if (Left < Right)
    {
        Center = (Left + Right) / 2;
        MSort(DataArray, TmpArray, Left, Center);
        MSort(DataArray, TmpArray, Center + 1, Right);
        Merge(DataArray, TmpArray, Left, Center + 1, Right);
    }
}

void MergeSort(int DataArray[], int n)
{
    int *TmpArray;
    TmpArray = malloc(n * sizeof(int));
    if (TmpArray != NULL)
    {
        MSort(DataArray, TmpArray, 0, n - 1);
        free(TmpArray);
    }
    else
    {
        FatalError("not space TmpArray!!!");
    }
}
void Merge(int DataArray[], int TmpArray[], int Left, int Center, int RightEnd)
{
    int i, LeftEnd, TmpPos, NumElements;
    LeftEnd = Center - 1;
    TmpPos = Left;
    NumElements = RightEnd - Left + 1;

    while (Left <= LeftEnd && Center <= RightEnd)
    {
        if (DataArray[Left] < DataArray[Center])
        {
            TmpArray[TmpPos++] = DataArray[Left++];
        }
        else
        {
            TmpArray[TmpPos++] = DataArray[Center++];
        }
    }

    while (Left <= LeftEnd)
    {
        TmpArray[TmpPos++] = DataArray[Left++];
    }

    while (Center <= RightEnd)
    {
        TmpArray[TmpPos++] = DataArray[Center++];
    }

    for (i = 0; i < NumElements; i++, RightEnd--)
    {
        DataArray[RightEnd] = TmpArray[RightEnd];
    }
}