数据结构第六次上机实习

C++ 上机 数据结构
数据结构上机实习
发布日期:   2021-02-02
文章字数:   2.8k
阅读时长:   13 分
阅读次数:  

实习题目：排序算法应用及对比

一、 上机实习题目与要求

问题描述

分别写出快速排序（改进版），归并排序和堆排序的递归和非递归版本以及冒泡/插入排序这些算法来实现排序算法应用及对比。

基本要求

（1）生成三组1000万个数，分别为随机数、基本正序(所有元素在正序的基础上整体左移 2位)、逆序（用什么数据结构？如果数据量达到1亿，10亿怎么办？）；

（2）实现快速排序（改进版），归并排序和堆排序的递归和非递归版本；

（3）要求从三组1000万数据中查找前d个最大的数（d是输入参数，请用快排，堆排序， 归并排序以及插入/冒泡 排序算法对所有数据排序后再查找最大的d个数，比较不同 排序算法以及递归和非递归算法的区别(运行时间)；

（4）不需要对1000万数据整体排序，从三组1000万数据中查找前d个最大和最小的数， 用什么数据结构？

二、数据结构设计

在这个题中要求使用1000万个数来试验排序算法，数量还是比较庞大的，全部存放在内存中会占用电脑较大的内存，本应该将这些数据存储在一个文本文件中，通过读取文件将这几组数进行排序处理。但是本程序为了方便，而且1000万个整型数据占用的内存也没有那么大，内存还是放的下的，因此选用了一个长度为1000万的数组来存放这1000万个数，将这组数进行相关的操作即可获得其他两组数。

三、源代码

stdfax.h

#ifndef STDFAX_H_INCLUDE
#define STDFAX_H_INCLUDE
#include <iostream>
#include <ctime>
#include <time.h>
#include <algorithm>
using namespace std;
#endif // !SYDFAX_H_INCLUDE

sort.h

#ifndef SORT_H_INCLUDE
#define SORT_H_INCLUDE
#include "stdfax.h"

const int M = 20;

template<class T>
//交换x与y
void Swap(T& x, T& y)
{
    T temp = x;
    x = y;
    y = temp;
}

template<class T>
//获取一个有n个随机数的序列
T* creat(int n)
{
    T* array = new T[n];
    srand(0);
    //依次将n个随机数放到数组中存储
    for (int i = 0; i < n;i++)
    {
        array[i] = rand();
    }
    return array;
}

template<class T>
//将正序数组转化为基本正序数组
void backward(T* arr,int n)
{
    int i;
    //保存最左边的元素
    int temp1 = arr[0];
    int temp2 = arr[1];
    // 全部元素往左移动两个位置
    for (i = 0; i < n - 1; i++)
    {
        arr[i] = arr[i + 2];
    }
    // 把最左边的元算放到最右边
    arr[i-1] = temp1;
    arr[i] = temp2;
}

template<class T>
//将正序数组转化为逆序数组
void reverse(T* arr, int n)
{
    for (int i = 0;i < n/2;i++)
    {
        //依次交换两边的数
        Swap(arr[i], arr[n - i - 1]);
    }
}

template<class T>
//复制数组
T* copy(T* arr, int n)
{
    T* result = new T[n];
    for (int i = 0;i < n;i++)
    {
        //将元素组的所有元素依次复制到新数组中
        result[i] = arr[i];
    }
    return result;
}

//改进的快速排序
template <class T>
//三数取中，选择中间的数作为基准
T NumberOfThree(T* arr, int low, int high)
{
    int mid = low + ((high - low) >> 1);
    //对起始元素，末尾元素，中间元素进行一个简单排序，返回中间的数作为基准
    if (arr[mid] > arr[high])
    {
        Swap(arr[mid], arr[high]);
    }
    if (arr[low] > arr[high])
    {
        Swap(arr[low], arr[high]);
    }
    if (arr[mid] > arr[low])
    {
        Swap(arr[mid], arr[low]);
    }
    //返回大小为中间的数作为基准
    return arr[low];
}

template <class T>
//对序列进行划分
int Partition(T* arr, int low, int high)
{
    int i = low, j = high + 1;
    //x为用三数取中的方法获取的基准数
    T x = NumberOfThree(arr, low, high);
    while (true)
    {
        while (arr[++i] < x && i < high);//使i指针指向比基准大的数
        while (arr[--j] > x);            //或者high指向比基准小的数
        if (i >= j)
            break;                        //i>=j时退出循环
        Swap(arr[i], arr[j]);
    }
    arr[low] = arr[j];
    //将基准元素放到j的位置
    arr[j] = x;
    return j;
}

template <class T>
//插入排序的算法
void InsertSort(T* arr, int low, int high)
{
    int i, j;
    T temp; // 用来存放临时的变量
    for (i = low + 1; i <= high; i++)
    {
        temp = arr[i];
        //找到对应的位置，并将元素插入
        for (j = i - 1; (j >= low) && (arr[j] > temp); j--)
        {
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = temp;
    }
}

template <class T>
//改进的快速排序
void QuickSort(T* arr, int low, int high)
{
    int pivotpos;
    if (high - low + 1 < 10)
    {
        //一组中元素个数少于10个就使用插入排序
        InsertSort(arr, low, high);
        return;
    }
    if (low < high)
    {
        //否则使用快排的方法
        pivotpos = Partition(arr, low, high);        //进行划分
        QuickSort(arr, low, pivotpos - 1);
        QuickSort(arr, pivotpos + 1, high);
    }
}


template <typename T>
//合并两个有序的序列
void Merge(T* arr, int start, int mid, int end)
{
    int i, j, k, n1, n2;
    k = 0;
    n1 = mid - start + 1;
    n2 = end - mid;
    T* L = new T[n1], * R = new T[n2];

    for (i = 0; i < n1; i++) // 将arr的左部分赋给L
        L[i] = arr[start + i];
    for (j = 0; j < n2; j++) // 将arr的右部分赋给R
        R[j] = arr[mid + j + 1];
    i = 0;
    j = 0;
    k = start;
    while (i < n1 && j < n2) 
    { //合并
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else 
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) 
    { // 左部分没处理完继续处理
        arr[k] = L[i];
        k++;
        i++;
    }
    while (j < n2) 
    { // 右部分没处理完继续处理
        arr[k] = R[j];
        k++;
        j++;
    }
    delete[] L;
    delete[] R;
}
template <typename T>
//归并排序
void MergeSort(T* arr, int start, int end)
{
    int mid;
    //start>=end时为递归出口
    if (start >= end)
        return;
    mid = (start + end) / 2;
    MergeSort(arr, start, mid);
    MergeSort(arr, mid + 1, end);
    Merge(arr, start, mid, end);
}

template <class T>
//下滑操作 
void ShiftDown(T* arr, int start, int end) 
{
    int i, j, temp;
    i = start;
    j = 2 * i + 1; //让j为i的子女
    temp = arr[i];
    while (j <= end) 
    {
        if (j < end && arr[j] < arr[j + 1]) //获取两个子女中较大者
        {
            j++;
        }
        if (temp < arr[j])
        { //如果双亲比子女小，那么上移较大的子女结点
            arr[i] = arr[j];
            i = j;            //i为父
            j = 2 * i + 1; //j为子女
        }
        else //否则，则结束循环
        {
            break;
        }
    }
    arr[i] = temp; // 把temp暂存的值放到正确的位置
}

template <class T>
//堆排序非递归算法
void HeapSortOFF(T* arr, int n) 
{
    int Current, i, temp; //Current需要下滑的结点

    //先用下滑的方法建成最大堆
    for (Current = (n / 2 - 1); Current >= 0; Current--)
    {
        ShiftDown(arr, Current, n - 1);
    }
    //将堆顶点元素与数组中n-1位置的数交换位置
    Swap(arr[0], arr[n - 1]);
    for (i = n - 2; i > 0; i--) 
    { //然后重复上面的操作，直到处理完毕
        ShiftDown(arr, 0, i);
        Swap(arr[0], arr[i]);
    }
}

template <class T>
//堆排序的递归算法
//调整堆
void adjust(T* arr, int x, int n)
{
    int left = 2 * x + 1;
    int right = 2 * x + 2;
    int max = x;

    if (x <= n / 2)
    {
        if (left < n && arr[left] > arr[max])
        {
            max = left;
        }
        if (right < n && arr[right] > arr[max])
        {
            max = right;
        }
        //否则交换位置后继续调整
        if (max != x)
        {
            Swap(arr[x], arr[max]);
            adjust(arr, max, n);
        }
    }
}

template <class T>
//建立大根堆
void buildHeap(T* arr, int n)
{
    int Current;            //Current需要下滑的结点
    //用下滑的方法建成最大堆
    for (Current = (n / 2 - 1); Current >= 0; Current--)
    {
        ShiftDown(arr, Current, n - 1);
    }
}

template <class T>
//堆排序的递归算法
void heapSortON(T* arr, int n) 
{
    buildHeap(arr, n);

    for (int i = n - 1; i > -1; --i)
    {
        Swap(arr[0], arr[i]);
        adjust(arr, 0, i);
    }
}

template <class T>
//冒泡排序
void BubbleSort(T* arr, int n)
{
    bool flag;            //falg为交换标志
    for (int i = 1;i < n;i++)
    {
        flag = false;
        for (int j = n - 1;j >= i;i--)
        {
            if (arr[j - 1] > arr[j])
            {
                Swap(arr[j - 1], arr[j]);
                flag = true;
            }
        }
        if (flag == false) break;
    }
}

#endif // !SORT_H_INCLUDE

main.cpp

#include "stdfax.h"
#include "sort.h"

int main()
{
    int n, d;
    clock_t start, end;
    double runTime;
    cout << "请输入元素的个数n：";
    cin >> n;
    int* array=creat<int>(n);
    /*reverse(array, n);
    cout << "逆序序列:" << endl;
    for (int i = 0; i < n;i++)
    {
        cout << array[i] << " ";
    }
    cout << endl;
    backward(array, n);
    cout << "基本正序序列:" << endl;
    for (int i = 0; i < n;i++)
    {
        cout << array[i] << " ";
    }
    cout << endl;*/

    //测试随机序列中改进的快速排序算法的用时
    int* ori = copy(array, n);
    start = clock();
    QuickSort(ori, 0, n - 1);
    end = clock();
    runTime = double(end - start) / CLOCKS_PER_SEC;
    cout << "随机序列：改进的快速排序的用时为：" << runTime << "s" << endl;

    reverse(ori, n);        //将数组转置
    start = clock();
    QuickSort(ori, 0, n - 1);
    end = clock();
    runTime = double(end - start) / CLOCKS_PER_SEC;
    cout << "逆序序列：改进的快速排序的用时为：" << runTime << "s" << endl;

    backward(ori, n);        //将数组转置
    start = clock();
    QuickSort(array, 0, n - 1);
    end = clock();
    runTime = double(end - start) / CLOCKS_PER_SEC;
    cout << "部分正序序列：改进的快速排序的用时为：" << runTime << "s" << endl;
    cout << "请输入需要获得的最大数的个数d：";
    cin >> d;
    cout << "最大的d个数为：";
    for (int i = 0;i < d;i++)
    {
        cout << array[n - i - 1] << "\t";
    }
    delete[] ori;
    cout << endl;
    cout << endl;


    ori = copy(array, n);
    start = clock();
    MergeSort(array, 0, n - 1);
    end = clock();
    runTime = double(end - start) / CLOCKS_PER_SEC;
    cout << "随机序列：二路归并排序的用时为：" << runTime << "s" << endl;

    reverse(ori, n);        //将数组转置
    start = clock();
    MergeSort(array, 0, n - 1);
    end = clock();
    runTime = double(end - start) / CLOCKS_PER_SEC;
    cout << "逆序序列：二路归并排序的用时为：" << runTime << "s" << endl;

    backward(ori, n);        //将数组转置
    start = clock();
    MergeSort(array, 0, n - 1);
    end = clock();
    runTime = double(end - start) / CLOCKS_PER_SEC;
    cout << "部分正序序列：二路归并排序的用时为：：" << runTime << "s" << endl;
    cout << "最大的d个数为：";
    for (int i = 0;i < d;i++)
    {
        cout << array[n - i - 1] << "\t";
    }
    delete[] ori;
    cout << endl;
    cout << endl;


    ori = copy(array, n);
    start = clock();
    HeapSortOFF(array, n);
    end = clock();
    runTime = double(end - start) / CLOCKS_PER_SEC;
    cout << "随机序列：非递归堆排序的用时为：" << runTime << "s" << endl;

    reverse(ori, n);        //将数组转置
    start = clock();
    HeapSortOFF(ori,n);
    end = clock();
    runTime = double(end - start) / CLOCKS_PER_SEC;
    cout << "逆序序列：非递归堆排序的用时为：" << runTime << "s" << endl;

    backward(ori, n);        //将数组转置
    start = clock();
    HeapSortOFF(ori, n);
    end = clock();
    runTime = double(end - start) / CLOCKS_PER_SEC;
    cout << "部分正序序列：非递归堆排序的用时为：" << runTime << "s" << endl;
    cout << "最大的d个数为：";
    for (int i = 0;i < d;i++)
    {
        cout << array[n - i - 1] << "\t";
    }
    delete[] ori;
    cout << endl;
    cout << endl;


    ori = copy(array, n);
    start = clock();
    heapSortON(array, n);
    end = clock();
    runTime = double(end - start) / CLOCKS_PER_SEC;
    cout << "随机序列：递归堆排序的用时为：" << runTime << "s" << endl;

    reverse(ori, n);        //将数组转置
    ori = copy(array, n);
    start = clock();
    heapSortON(array, n);
    end = clock();
    runTime = double(end - start) / CLOCKS_PER_SEC;
    cout << "逆置序列：递归堆排序的用时为：" << runTime << "s" << endl;

    backward(ori, n);        //将数组转置
    ori = copy(array, n);
    start = clock();
    heapSortON(array, n);
    end = clock();
    runTime = double(end - start) / CLOCKS_PER_SEC;
    cout << "部分正序序列：递归堆排序的用时为：" << runTime << "s" << endl;
    cout << "最大的d个数为：";
    for (int i = 0;i < d;i++)
    {
        cout << array[n - i - 1] << "\t";
    }
    cout << endl;
    cout << endl;

    start = clock();
    BubbleSort(array, n);
    end = clock();
    runTime = double(end - start) / CLOCKS_PER_SEC;
    cout << "改进的冒泡排序的用时为：" << runTime << "s" << endl;
    cout << "最大的d个数为：";
    for (int i = 0;i < d;i++)
    {
        cout << array[n - i - 1] << "\t";
    }
    cout << endl;

    delete[] array;
    system("pause");
    return 0;
}
文章作者: 陈细利
文章链接: https://firewolf321.github.io/2021/02/02/shu-ju-jie-gou-di-liu-ci-shang-ji/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 陈细利 !
C++ 上机 数据结构
赏
评论
 上一篇
计算机网络实验 计算机网络实验
问题及回答记录 问题及回答记录 (self-test Q&A related to your experience reports, and no less than 5 questions or contents of Q&
2021-02-11 计算机网络
上机 计算机网络
下一篇 
数据结构第五次上机实习 数据结构第五次上机实习
实习题目：图的三种算法的同步演示一、 上机实习题目与要求问题描述分别写出深度优先遍历、Prim算法与Dijkstra算法这三个算法，同时动态显示出相应的构造过程。 基本要求（1）基于第3页ppt的图例构造图（权值可以自行设计添加）； （2）
2021-01-29 数据结构上机实习
C++ 上机 数据结构
  目录