100個亂數排序

完結

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define Maxsize 100

typedef struct
{
    int R[Maxsize + 1];
    int length;
} SqList;

void InsertSort(SqList &L)
{
    int i, j;
    int count = 0;
    for (i = 2; i <= L.length; i++)
        if (L.R[i] < L.R[i - 1])
        {
            count++;
            L.R[0] = L.R[i];
            L.R[i] = L.R[i - 1];
            for (j = i - 2; L.R[0] < L.R[j]; j--, count++)
                L.R[j + 1] = L.R[j];
            L.R[j + 1] = L.R[0];
        }
    printf("\n直插法比較次數是：%d", count);
}

int ShellInsert(SqList &L, int dk)
{
    int i, j;
    int count = 0;
    for (i = dk + 1; i <= L.length; i++)
        if (L.R[i] < L.R[i - dk])
        {
            count++;
            L.R[0] = L.R[i];
            for (j = i - dk; j > 0 && L.R[0] < L.R[j]; j -= dk, count++)
                L.R[j + dk] = L.R[j];
            L.R[j + dk] = L.R[0];
        }
    return count;
}

void ShellSort(SqList &L, int dita[], int t)
{
    int k, count = 0, sum = 0;
    for (k = 0; k < t; k++)
    {
        count = ShellInsert(L, dita[k]);
        sum += count;
    }
    printf("\n希爾排序比較次數是：%d", sum);
}

int Partition(SqList &L, int low, int high, int &count)
{
    count = 0;
    int pivotkey;
    L.R[0] = L.R[low];
    pivotkey = L.R[low];
    while (low < high)
    {
        count++;
        while (low < high && L.R[high] >= pivotkey)
        {
            high--;
            count++;
        }
        if (low < high)
        {
            L.R[low++] = L.R[high];
            count++;
        }
        while (low < high && L.R[low] <= pivotkey)
        {
            low++;
            count += 2;
        }
        if (low < high)
        {
            L.R[high--] = L.R[low];
            count++;
        }
    }
    L.R[low] = L.R[0];
    return low;
}

void QSort(SqList &L, int low, int high, int &count)
{
    int pivotloc, sum;
    if (low < high)
    {
        count++;
        pivotloc = Partition(L, low, high, sum);
        count += sum;
        QSort(L, low, pivotloc - 1, count);
        QSort(L, pivotloc + 1, high, count);
    }
}

void Merge(int *R, int low, int m, int high, int &count)
{
    int i = low, j = m + 1, p = 0;
    int *R1;
    R1 = (int *)malloc((high - low + 1) * sizeof(int));
    if (!R1)
        return;
    while (i <= m && j <= high)
    {
        R1[p++] = (R[i] <= R[j]) ? R[i++] : R[j++];
        count += 2;
    }
    while (i <= m)
    {
        R1[p++] = R[i++];
        count++;
    }
    while (j <= high)
    {
        R1[p++] = R[j++], count++;
    }
    for (p = 0, i = low; i <= high; p++, i++)
        R[i] = R1[p];
}

void MergeSort(SqList &L, int low, int high, int &count)
{
    int mid;
    int sum = 0;
    if (low < high)
    {
        mid = (low + high) / 2;
        MergeSort(L, low, mid, count);
        MergeSort(L, mid + 1, high, count);
        Merge(L.R, low, mid, high, sum);
        count += sum;
    }
}

int main()
{
    int i;
    SqList L, L0;
    int dita[3];
    int count = 0, count1 = 0;
    srand((unsigned)time(NULL) + (unsigned)rand());
    for (i = 1; i <= 100; i++)
    {
        L.R[i] = rand() % 100;
        L0.R[i] = L.R[i];
    }
    printf("100個亂數是：\n");
    for (i = 1; i <= 100; i++)
    {
        if (i % 10)
            printf("%5d", L0.R[i]);
        else
        {
            printf("%5d", L0.R[i]);
            printf("\n");
        }
    }
    L.length = L0.length = 100;
    /*直插排序*/
    InsertSort(L);
    printf("\n直插排序結果：\n");
    for (i = 1; i <= 100; i++)
    {
        if (i % 10)
            printf("%5d", L.R[i]);
        else
        {
            printf("%5d", L.R[i]);
            printf("\n");
        }
    }
    for (i = 1; i <= 100; i++)
    {
        L.R[i] = L0.R[i];
    } /*更新L*/
    /*希爾排序*/
    dita[0] = 5;
    dita[1] = 3;
    dita[2] = 1;
    ShellSort(L, dita, 3);
    printf("\n希爾排序結果：\n");
    for (i = 1; i <= 100; i++)
    {
        if (i % 10)
            printf("%5d", L.R[i]);
        else
        {
            printf("%5d", L.R[i]);
            printf("\n");
        }
    }
    for (i = 1; i <= 100; i++)
    {
        L.R[i] = L0.R[i];
    } /*更新L*/
    /*快速排序*/
    QSort(L, 1, L.length, count);
    printf("\n快速排序比較次數是：%d\n", count);
    printf("快速排序結果：\n");
    for (i = 1; i <= 100; i++)
    {
        if (i % 10)
            printf("%5d", L.R[i]);
        else
        {
            printf("%5d", L.R[i]);
            printf("\n");
        }
    }
    /*歸并排序*/
    for (i = 1; i <= 100; i++)
    {
        L.R[i] = L0.R[i];
    } /*更新L*/
    MergeSort(L, 1, 100, count1);
    printf("\n歸并排序比較次數是：%d\n", count1);
    printf("歸并排序結果：\n");
    for (i = 1; i <= 100; i++)
    {
        if (i % 10)
            printf("%5d", L.R[i]);
        else
        {
            printf("%5d", L.R[i]);
            printf("\n");
        }
    }
    system("pause");
}