数据结构实验课设

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define N 100
void merge(int l, int r);//归并排序
void quick_sort(int q[], int l, int r);//快速排序
void down(int u);//堆排序
void swap(int* a, int* b);//交换函数
void ShellSort(int* arr, int n);//希尔排序
int q[N],temp[N];//归并排序temp辅助数组
int a[N];//快速排序辅助数组
int h[N], cnt;//堆排序辅助数组
int m[N];
int main(void) {

	int b = 3,n;
	while (b--) {
        printf("请输入整数个数\n");
	    scanf("%d", &n);//请输入n个整数
        printf("请输入%d个整数\n", n);
        for (int i = 0; i < n; i++) {
            scanf("%d", &q[i]);
            a[i] = q[i];
            h[i+1] = q[i];
            m[i] = q[i];
        }
        cnt=n;
        merge(0, n - 1);
        printf("归并排序的结果为:");
        for (int i = 0; i < n; i++) printf("%d ", q[i]);
        quick_sort(a, 0, n - 1);
        printf("\n快速排序的结果为:");
        for (int i = 0; i < n; i++) printf("%d ", a[i]);
        for (int i = n / 2; i; i--) down(i);//堆排序
        printf("\n堆排序的结果为:");
        for (int i = 1; i <=n; i++) {
            printf("%d ", h[1]);
            h[1] = h[cnt--];
            down(1);
        }
        ShellSort(m, n);
        printf("\n希尔排序的结果为:");
        for (int i = 0; i < n; i++) printf("%d ", m[i]);
        printf("\n");
	}

	return 0;
}
void merge(int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    int k = 0, i = l, j = mid + 1;

    merge(l, mid);
    merge(mid + 1, r);
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) temp[k++] = q[i++];
        else temp[k++] = q[j++];
    }
    while (i <= mid) temp[k++] = q[i++];
    while (j <= r)  temp[k++] = q[j++];
    for (i = l, j = 0; i <= r; i++, j++) {
        q[i] = temp[j];
    }
}
void quick_sort(int a[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = a[l + r >> 1];
    while (i < j)
    {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(&a[i], &a[j]);
    }

    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}
void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        swap(&h[u], &h[t]);
        down(t);
    }
}
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
//希尔排序
void ShellSort(int* arr, int n)
{
    int gap = n;
    while (gap > 1)
    {
        //每次对gap折半操作
        gap = gap / 2;
        //单趟排序
        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tem = arr[end + gap];
            while (end >= 0)
            {
                if (tem < arr[end])
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            arr[end + gap] = tem;
        }
    }
}