Loading...
墨滴

公子宇

2021/12/12  阅读:36  主题:自定义主题1

内部排序算法的实现与比较

内部排序算法的实现与比较

一、问题描述

(1) 实验题目

在教科书中,各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。

(2) 基本要求

  1. 对常用的内部排序算法进行比较:直接插入排序、简单选择排序、冒泡排序、快速排序、希尔排序、归并排序。
  2. 利用随机函数产生N(N=30000)个随机整数,作为输入数据作比较;比较的指标为关键字参加的比较次数和关键字的移动次数(关键字交换计为3次移动)。
  3. 对结果作出简要分析。

(3) 测试数据

随机函数产生。

二、需求分析

(1) 程序所能达到的基本可能

  1. 本程序用来求出六种算法运行时关键字参加的比较次数和关键字的移动次数
  2. 程序运行后自动输出这六种算法的关键字比较次数和移动次数

(2) 输入和输出的形式

  1. 输入数据:参加排序的整数个数NN=30000,注:不得减少N);
  2. 输出数据:各种排序方法的关键字比较次数和移动次数(从小到大排列)。

三、概要设计

(1) 定义头文件sorting.h

  1. 创建Record类型和data类型

  2. 创建六种排序算法的模块

    void InsertSort(Record R[], int n, data* num);
    void SelectSort(Record R[], int n, data* num);
    void BubbleSort(Record R[], int n, data* num);
    int QuickOnePass(Record R[],int i, int j, data* num);
    void QuickSort(Record R[], int low, int high, data* num);
    void ShellInsert(Record R[], int m, int n, data* num);
    void ShellSort(Record R[], int n, data* num);
    int min(int x, int y);
    void MergeSort(Record* R, int n, data* num);

(2) 头文件引用与预定义

#include "sorting.h"
#include <time.h>

#define MAXSIZE 30000

(3) 模块定义

void GenRanNums(Record *a, int n)// 产生随机数数组函数
void Zeroing(data* n)// 令比较、移动次数归零

(4) 主程序调用关系

  1. 定义变量并初始化

    Record a[MAXSIZE+1];

    // 初始化一个data类型用来记录比较和移动次数

    data* num = (data*)malloc(sizeof(data));

  2. 调用void Zeroing(data* n);令比较、移动次数归零,调用void GenRanNums(Record *a, int n);产生随机数数组(以下简称:归零、产生随机数)

  3. 计算插入排序的关键词比较、移动次数

  4. 归零、产生随机数,计算选择排序的关键词比较、移动次数

  5. 归零、产生随机数,计算冒泡排序的关键词比较、移动次数

  6. 归零、产生随机数,计算快速排序的关键词比较、移动次数

  7. 归零、产生随机数,计算希尔排序的关键词比较、移动次数

  8. 归零、产生随机数,计算归并排序的关键词比较、移动次数

四、详细设计

(1) 创建必要的数据类型

#define KeyType int
#define InfoType char
// 定义Record类型
typedef struct record
{

    KeyType key;
    InfoType info;
}Record;
// 定义用来记录比较、移动次数的data类型
typedef struct data
{

    int comNum;
    int movNum;
}data;

(2) 编写六种算法模块

void InsertSort(Record R[], int n, data* num)// 插入排序
void SelectSort(Record R[], int n, data* num)// 简单选择排序
void BubbleSort(Record R[], int n, data* num)// 冒泡排序
int QuickOnePass(Record R[],int i, int j, data* num);
void QuickSort(Record R[], int low, int high, data* num)// 快速排序
void ShellInsert(Record R[], int m, int n, data* num);
void ShellSort(Record R[], int n, data* num)// 希尔排序
int min(int x, int y);
void MergeSort(Record* R, int n, data* num)// 归并算法

(3) 头文件引用与预定义

#include "sorting.h"
#include <time.h>

#define MAXSIZE 30000

(4) 归零函数

void Zeroing(data* n) // 令比较、移动次数归零
{
    n->comNum = 0;
    n->movNum = 0;
}

(5) 随机数产生函数

void GenRanNums(Record *a, int n) // 产生随机数数组函数
{
    int i;
    a[0].info = 0;
    a[0].key = 0;
    srand((unsigned)time(NULL)); // 产生随机数种子
    for (i = 1; i < n; i++)
    {
        a[i].info = 0;
        a[i].key = rand(); // 将关键字定义为随机数
    }
}

五、调试分析

(1) 算法编写思路

在编写这个程序时,我首先先编写正常的六大算法,之后按照比较次数和移动次数的特点,在算法所在函数的对应位置添加num->comNum++;num->movNum++;num->movNum += 3;(对应关键词交换情况)。

(2) 算法的时空分析

  • 归零函数void Zeroing(data* n);运算次数为1,时间复杂度为O(1)。
  • 随机数函数void GenRanNums(Record *a, int n);含有一个循环结构,运算次数为n,时间复杂度为O(n)。

六、使用说明

程序运行后自动输出这六种算法的关键字比较次数和移动次数

七、调试结果

第一组测试样例

  Sorting : 比较次数    移动次数
InsertSort: 226871937   226931937
SelectSort: 450015000   89973
BubbleSort: 450015000   673191681
 QuickSort: 344452      235856
 ShellSort: 564492      1344534
 MergeSort: 410409      450000

第二组测试样例

  Sorting : 比较次数    移动次数
InsertSort: 223909632   223969632
SelectSort: 450015000   89964
BubbleSort: 450015000   678127635
 QuickSort: 378758      234440   
 ShellSort: 559314      1339356
 MergeSort: 410275      450000 

八、遇到的问题和解决方法

(1) 快速排序无法运算30000个随机数

  • 描述

    快速排序总是在运算到两万八千多的时候报错,如果将MAXSIZE换为10000或者20000,就可以运行。

  • 解决办法

    我编写的六个算法全都是直接对随机数数组修改的,所以在插入排序之后,数组就是有序的了。后续的所有算法都是对一个有序的算法进行修改。所以我在每一个算法调用之前全都调用了一次void GenRanNums(Record *a, int n);,将有序的数组替换为随机的数组。在这之后,该问题就奇怪的解决了。原因我还没有找到。

(2) 出现有的算法移动次数或者比较次数为0

  • 描述

    有些算法在调用之后出现比较次数或者移动次数为0的情况

  • 解决办法

    同上一个问题,是因为在插入排序之后,数组就变为有序,因此,有些算法的关键字比较次数或者移动次数变为0。所以在每一个算法调用之前全都调用了一次void GenRanNums(Record *a, int n);,将有序的数组替换为随机的数组

九、实验收获与感想

  1. 这个实验是要测算六个算法的关键字比较次数和移动次数,在编写程序的时候,因为要编写六个算法的函数,我又回顾了一遍这六个算法的实现思路与结构;
  2. 当终端打印出算法的关键字比较次数和移动次数时,看着这六个算法各不相同的比较次数和移动次数,我对于不同算法的差异性有了更深的了解。
  3. 这六种算法的输入都是随机数组,通过编写程序,我又回顾了一遍C语言随机数相关的函数。

十、附录

源程序文件清单:

  • SortingAlgorithm.c
  • sorting.h

公子宇

2021/12/12  阅读:36  主题:自定义主题1

作者介绍

公子宇