#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef int KeyType;
typedef struct
{   KeyType Key;
}LineList;

void InsertSort(LineList r[],int n)
{
    int i,j;
    for(i = 2;i <= n;i++)
    {
        r[0] = r[i];
        j = i-1;
        while(r[0].Key < r[j].Key)
        {
            r[j+1] = r[j];
            j = j-1;
        }
        r[j+1] = r[0];
    }
}

void ShellSort(LineList r[],int n)
{
    int i,j,d;
    d = n/2;
    while(d>0)
    {   for(i = d;i <= n;i++)
        {
            r[0] = r[i];
                j = j - d;
            while(j >= 0 && r[0].Key < r[j].Key)
            {
                r[j+d] = r[j];
                j = j - d;
            }
            r[j + d] = r[0];
            j = j - d;
        }
        d = d/2;
    }
}

void BubbleSort(LineList r[],int n)
{
    int i,j,exchange;
    LineList temp;
    for(i = 1;i < n;i++)
    {   exchange = 0;
        for(j = 1;j <= n-i;j++)
        if(r[j].Key > r[j+1].Key)
        {   temp = r[j];
            r[j] = r[j+1];
            r[j+1] = temp;
            exchange = 1;
        }
        if(exchange == 0) return;
    }
}

void QuickSort(LineList r[],int first,int end)
{
    int i,j;
    LineList temp;
    i = first;j = end;temp = r[i];
    while (i < j)
    {
        while(i < j && temp.Key <= r[j].Key) j--;
            r[i] = r[j];
        while(i < j && r[i].Key <= temp.Key) i++;
            r[j] = r[i];
    }
    r[i] = temp;
    if(first < i-1) QuickSort(r,first,i-1);
    if(i+1 < end) QuickSort(r,i+1,end);
}

void SelectSort(LineList r[],int n)
{
    int i,j,k;
    LineList x;
    for(i = 1;i <= n;i++)
    {   k = i;
        for(j = i+1;j <= n; ++j)
        if(r[j].Key < r[k].Key)
            k = j;
        if(k != j)
        {x = r[i];r[i] = r[k];r[k] = x;}
    }
}

void Sift(LineList r[],int low,int high)
{
    int i = low,j = 2*i;
    LineList tmp = r[i];
    while (j <= high)
    {
        if(j < high && r[j].Key < r[j+1].Key)
            j = j + 1;
        if(tmp.Key < r[j].Key)
        {
            r[i] = r[j];
            i = j;
            j = 2*i; 
        }
        else break;
    }
    r[i] = tmp;
}

void HeapSort(LineList r[],int n)
{
    int i;
    LineList tmp;
    for ( i = n/2; i >= 1; i--)
        Sift(r,i,n);
    for ( i = n; i >= 1; i--)
    {
        tmp = r[1];
        r[1] = r[i];
        r[i] = tmp;
        Sift(r,1,i-1);
    }
}

void Merge(LineList r[],int low,int mid,int high)
{
    LineList *r1;
    int i = low,j = mid+1,k = 1;
    r1 =(LineList *)malloc((high - low + 1)*sizeof(LineList));
    while(i <= mid && j <= high)
        if(r[i].Key <= r[j].Key)
            r1[k++] = r[i++];
        else
            r1[k++] = r[j++];
    while(i <= mid)
            r1[k++] = r[i++];
    while(j <= high)
            r1[k++] = r[j++];
    for(k = 1,i = low;i <= high;k++,i++)
            r[i] = r[k];
}

void MergePass(LineList r[],int length,int n)
{
    int i;
    for(i = 1;i+2*length-1<=n;i=i+2*length)
        Merge(r,i,i+length-1,n);
    if(i + length - 1 <= n)
        Merge(r,i,i+length-1,n);
}

void MergeSort(LineList r[],int n)
{
    int length;
    for(length = 1;length <= n;length = 2*length)
        MergePass(r,length,n);
}

void OutList(LineList r[],int n)
{
    int i;
    printf("排序后的记录为：");
    for (i = 1; i <= n; i++)
        printf("%5d",r[i]);
}

void MenuSort()
{
    printf("\n                   排序子系统");
    printf("\n =================================================");
    printf("\n|               1——更新排序数据                    |");
    printf("\n|               2——直接插入排序                    |");
    printf("\n|               3——希尔排序                        |");
    printf("\n|               4——冒泡排序                        |");
    printf("\n|               5——快速排序                        |");
    printf("\n|               6——直接选择排序                    |");
    printf("\n|               7——堆排序                          |");
    printf("\n|               8——归并排序                        |");
    printf("\n|               0——返回                            |");
    printf("\n =================================================");
    printf("\n请输入菜单号（0-8）:"); 
}

int main()
{
    int i,n;
    LineList r[MAXSIZE];
    char ch1,ch2,a;
    ch1 = 'y';
    while (ch1 == 'y' || ch1 == 'Y')
    {   MenuSort();
        scanf("%c",&ch2);
        getchar();
        switch(ch2)
        {
            case '1':
                printf("请输入待排序表的长度：");
                scanf("%d",&n);
                printf("请输入%d个整数：",n);
                for ( i = 1; i <= n; i++)
                    scanf("%d",&r[i]);
                OutList(r,n);
                break;
            case '2':
                InsertSort(r,n);
                printf("进行直接插入排序，");
                OutList(r,n);
                break;
            case '3':
                ShellSort(r,n);
                printf("进行希尔插入排序，");
                OutList(r,n);
                break;
            case '4':
                BubbleSort(r,n);
                printf("进行冒泡排序，");
                OutList(r,n);
                break;
            case '5':
                QuickSort(r,1,n);
                printf("进行快速排序，");
                OutList(r,n);
                break;
            case '6':
                SelectSort(r,n);
                printf("进行直接选择排序，");
                OutList(r,n);
                break;
            case '7':
                HeapSort(r,n);
                printf("进行堆排序，");
                OutList(r,n);
                break;
            case '8':
                MergeSort(r,n);
                printf("进行归并排序，");
                OutList(r,n);
                break;
            case '0':
                ch1 = 'n';
                break;
            default:
                printf("输入有误，请输入0-9进行选择!");
        }
        if(ch2 != '0')
        {   printf("\n按回车键继续，按任意键返回主菜单！\n");
            a = getchar();
            if(a != '\xA')
            {
                getchar();ch1 = 'n';
            }
        }       
    }
    
}

实验9排序子系统

1.实验目的

(1)掌握常用的排序方法的基本思想。

(2)通过实验加深对各种算法的理解。

(3)掌握各种算法的时间复杂度。

2.实验内容

(1)编写直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、归并排序、堆排序的算法

（2)程序执行时，能显示每一趟排序的结果。

（3)设计如下选择式菜单，以选择菜单方式进行操作。将上述各种算法实现。