各种内排序算法的实现及性能的比较(借鉴材料)

实验报告

（2015/2016学年第2学期）

课程名称数据结构A

实验名称各种内排序算法的实现及性能的比较

实验时间2016 年 6 月20 日

指导单位计算机科学与技术系

指导教师骆健

学生姓名班级学号

学院(系) 管理学院专业信息管理与信息系统

一、问题陈述

（1）验证教材的各种内排序算法

（2）分析各种内排序算法的时间复杂度

（3）改进教材中的快速排序法，使得当子集和小于10个元素时改用直接插入排序

（4）使用随机数发生器产生大数据集合，运行上述各排序算法，使系统时钟测量个算法所需的实际时间，并进行比较。系统

时钟包含在头文件“time.h”中。

二、概要设计

Main.cpp调用Menu.h ，为主程序。Menu.h主菜单

Selectsort.h简单选择排序

Insertsort.h直接插入排序

Bubblesort.h冒泡排序

Quicksort.h快速排序

Mergesort.h合并排序

三、详细设计

①简单选择排序：将初始序列（A[0]~A[n-1]）作为待排序序列，第一趟在待排序序列（A[0]~A[n-1]）中找最小元素，与该序列中第一个元素A[0]交换，这样子序列（A[0]）有序，下一趟排序在带牌子序列（A[1]~A[n-1]）中进行。第i趟排序子序列（A[i-1]~A[n-1]）中进行。

经过n-1趟排序后使得初始序列有序。

程序流程图：

②直接插入排序：一个元素插入到有序表中，首先将其存入临时变量temp ，然后从后往前查找插入位置。当temp 小于表中元素时，就将开始

i=0

i

Small=i

j=i+1

j

A[j]

Small=

Swap(A[i],A[small]

j++

结束

N

N

N

Y

Y i++

该元素后移一个位置，继续比较、移动，直到temp大于等于表中元素或者到了有序表的第一个元素结束，这时就可将temp存入刚后移的元素的位置了。

程序流程图：

开始

N

i

Y

int j=i

T temp=A[i]

N

j>0&&temp

Y

A[j]=A[j-1];j-

A[j]=temp

i++

结束

③冒泡排序：第一趟在序列（A[0]~A[n-1]）中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次；第一趟排序结束，最大元素被交换到A[n-1]中（即沉底）下一趟排序只需在子序列

（A[0]~A[n-2]）中进行；如果在某一趟排序中未进行交换元素，说明子序列已经有序，则不再进行下一趟排序。

程序流程图：

④快速排序：取第一个元素作为分割元素，初始化i=left,j=right+1,i 开始

i=n-1

i>0

last=0;j=0

j

A[j+1]

Last=j

i=last

结束

N

N

Y

Y