《数据结构与算法》实验：排序算法实验比较——选择排序 & 堆排序

《数据结构与算法》实验和课程Github资源 

《数据结构与算法》实验：线性结构及其应用——算术表达式求值

《数据结构与算法》实验：树型结构的建立与遍历

《数据结构与算法》实验：图结构的建立与搜索

《数据结构与算法》实验：查找结构的实验比较——二叉查找树BST & 二分（折半）查找

《数据结构与算法》实验：排序算法实验比较——选择排序 & 堆排序

注意：正文文字为宋体小4号，图中文字为宋体5号。行距为多倍行距1.25。

      源程序与此报告打包提交，压缩包采用学号命名。

// lab5.cpp

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <windows.h>
using namespace std;
#define Swap(x, y) (a[x] = a[x] ^ a[y], a[y] = a[x] ^ a[y], a[x] = a[x] ^ a[y])
#define N 1000000
int a[N + 5];

void HeapAdjust(int x, int n) //调整堆
{
    if (x * 2 > n) return;
    int maxi = x * 2 + 1 > n ? x * 2 : (a[x * 2] < a[x * 2 + 1] ? x * 2 : x * 2 + 1);
    if (a[maxi] < a[x]) Swap(x, maxi), HeapAdjust(maxi, n);
}

void HeapSort(int n)
{
    for (int i = n; i >= 1; i--) HeapAdjust(i, n); //建立最小堆
    for (int i = n; i > 1; i--)
    {
        Swap(1, i); //取出堆根节点
        HeapAdjust(1, i - 1); //调整堆，此时大小减1
    }
}

void Print(int n)
{
    for (int i = 1; i < n; i++) printf("%d ", a[i]);
    printf("%d\n\n", a[n]);
}

void SelectSort(int n)
{
    int mini;
    for (int i = 1; i < n; i++)
    {
        mini = i;
        for (int j = i + 1; j <= n; j++)
            if (a[j] < a[mini]) mini = j;
        if (i != mini) Swap(i, mini);
    }
}

#define M 10
int main()
{
    freopen("init.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    DWORD sta, end;
    scanf("%d", &n);
    for (int j = 1; j <= 5; j++)
    {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        sta = GetTickCount();
        for (int i = 1; i <= M; i++) HeapSort(n);
        end = GetTickCount();
        printf("Heap%d %.6lfs\n", j, (double)(end - sta) / 1000 / M);
    }
    for (int j = 1; j <= 5; j++)
    {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        sta = GetTickCount();
        SelectSort(n);
        end = GetTickCount();
        printf("Select%d %.6lfs\n", j, (double)(end - sta) / 1000 / M);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

// create_data.cpp

#include <cstdio>
#include <cstdlib>
#define N 100000
#define M (1 << 30)
int main()
{
    freopen("init.txt", "w", stdout);
    printf("%d\n", N);
    for (int j = 1; j <= 5; j++, printf("\n"))
        for (int i = 1; i <= N; i++)
        {
            int x = rand() % M + 1, y = rand() % 15;
            x = x << y;
            printf("%d ", x);
        }
    fclose(stdout);
    return 0;
}

# d.py 画图

import matplotlib.pyplot as plt
import numpy as np
import seaborn as sns

heap_n = [10000, 50000, 100000, 200000, 300000]
heap_t = [0.001575, 0.008575, 0.016, 0.03555, 0.051975]
slct_n = [10000, 50000, 100000, 200000, 300000]
slct_t = [0.01095, 0.257425, 1.054325, 4.168375, 9.321475]

plt.rcParams["figure.figsize"] = (10.0, 6.0)
fig = plt.figure()
style = ["darkgrid", "dark", "white", "whitegrid", "ticks"]
sns.set_style(style[2])

ax1 = fig.add_subplot(111)
ax1.set_ylim([0, 1])
ax1.plot(heap_n, heap_t, "c", ms=10, lw=1, marker="o")  # 设置线粗细，节点样式
ax1.set_ylabel("Heap_time", fontsize="20")
ax1.tick_params(labelsize=10)
for x, y in zip(heap_n, heap_t):  # # 添加数据标签
    plt.text(
        x, y + 0.01, str(y) + "s", ha="center", va="bottom", fontsize=8, rotation=0
    )
# plt.plot(heap_t, label="heap")
# plt.legend(bbox_to_anchor=(0.15, 1.0))

ax2 = ax1.twinx()
ax2.set_ylim([0, 10])
ax2.plot(slct_n, slct_t, "darkviolet", ms=7, lw=1, marker="o")  # 设置线粗细，节点样式
ax2.set_ylabel("Select_time", fontsize="20")
ax2.tick_params(labelsize=10)
for x, y in zip(slct_n, slct_t):  # # 添加数据标签
    plt.text(x, y + 0.1, str(y) + "s", ha="center", va="bottom", fontsize=8, rotation=0)
# plt.plot(slct_t, label="slct")
"""
plt.legend(
    bbox_to_anchor=(0.0, 1.02, 1.0, 0.102),
    loc=0,
    ncol=3,
    mode="expand",
    borderaxespad=0.0,
)
"""
plt.savefig(r"D:\GZN\HIT\个人文件\2019秋数据结构与算法\Lab5\1.png", dpi=1000, bbox_inches="tight")
plt.grid()
plt.show()