数据结构优秀课程设计快速排序.docx

数据结构课程设计汇报

快速排序详析

专业
物联网工程
学生姓名
方振华
班级
152
学号

指导老师
刘 骞
完成日期
12月22日

目 录

一、介绍 1

二、算法说明 1

三、测试结果 7

四、分析和探讨 9

五、数据异常测试案例 15

六、小结 17

七、参考文件 18

八、源程序清单 18

快速排序详析
一、 介绍
排序是计算机程序设计中常见数据处理操作。经过一学期数据结构学习，我们学到很多个排序方法，如插入排序、交换排序、选择排序、归并排序、技术排序等。经过分析和对比，我们总结出一个快速排序优化版本，并对其设计思想和具体实现进行详解。

二、 算法说明
1、多种排序算法方法性能比较

图1：多种排序算法方法性能比较
（1）就时间性能而言，快速排序，堆排序和归并排序全部有很好时间性能。相对而言，快速排序速度最快，不过快速排序在最坏情况下，时间性能达成了O（n^2），不如堆排序和归并排序快。
（2）就空间性能而言，直接插入排序，冒泡排序，简单选择排序，堆排序要求辅助空间比较小。其中直接插入排序，冒泡排序，简单选择排序比较简单，轻易实现，但时间性能较差。
快速排序是一个有效排序算法。即使算法在最坏情况下运行时O(n^2)，但因为平均运行时间为O（nlogn），而且在内存使用、程序实现复杂性上表现优异，尤其是对快速排序算法进行随机化可能，使得快速排序在通常情况下是最实用排序方法之一。快速排序被认为是目前最优异内部排序方法，其基础思想是经过一趟排序将待排统计分割成独立两部分，其中一部分统计关键词比另一部分统计关键词小，则可分别对这两部分统计进行排序，以达成整个序列有序。
2、步骤
快速排序基础算法Quicksort(S)由以下4个步骤组成：
(1).假如S中元素数目为0或一，则返回。
(2).选择S中任意一个元素v,v叫做支点(Pivot)。
(3).将S-{v}(剩下元素在S中)分成两个分开部分。全部小于v元素和全部大于v元素。
(4).依次返回Quicksort(L)，v和Quicksort结果

基础快速排序算法能够应用递归实现，关键细节包含支点选择和怎样分组。该算法许可把任何元素作为支点。支点把数组分为两组，图2展示了算法基础过程。

图2：算法基础过程
3、分析
最好情况：
快速排序最好情况是支点把集合分成两个相同大小子集而且在递归每个阶段全部这么划分。然后就有了两个通常大小递归调用和线性分组开销。在这种情况下运行时间复杂度是O（nlog2n）。
最坏情况：
假设在每一步递归调用中支点全部恰好是最小元素。这么小元素集合L就是空而大元素集合R拥有除了支点以外全部元素。
设T（N）是对N各元素惊醒快速排序所需运行时间按并假设对0或1各元
素排序时间刚好是1个时间单位。那么对因为N》1当每次全部运气很差地最
小元素作为支点得到原型时间满足T（N）=T(N-1)+N.即对N各项进行排
序时间等于递归排序大元素子集中N-1各项所需要时间加上进行分组
N个单位开销。最终得出T（N）=T(1)+2+3+…+N=N(N+1)/2=O(N^2)
支点选择：
错误方法：比较常见不明智选择就是把第一个元素作为支点。但假如输入是已经预先排过序，或是倒序，该支点给出分组就很糟，因为它是一个末端元素；而且这种情况会在迭代中继续出现，会以O(N^2)时间复杂度而告终，所以选择第一个元素作为支点不是好策略。
中位选择：
把中间元素即待排序序列中间位置元素作为支点是合理选择。当输入已经排过序时这种选择在每次递归调用中全部会给出理想支点。
中值划分：
在上诉选择中使用中间值作为支点能够消除非随机输入时出现退化情况。但这是一个消极选择，就是说仅仅是试图避免一个坏支点而并没有去尝试选择一个愈加好支点。中值划分是一个选择比平均情况愈加好支点尝试。在中值划分中，一个比较简单而有效策略是选择待排序列第一个、中间一个和最好一个统计这3个值中值作为支点。一样道理，也能够从待排序列中等距离地选择5各值，并将这5各值中值作为支点。
4、 程序设计
本试验目标是设计并实现一个快速排序Quicksort优化版本，而且比较在下列组合情况下算法性能表现
(1) cutoff值从0~20。Cutoff值作用是只有当数组长度小于等于这个值时才使用另一个简单排序方法对其排序不然使用Quicksort算法排序。
(2) 选定支点方法分别是“第一个元素”“三个元素中值”“五个元素中值”。
程序关键由6部分组成，分别是：
（1） 程序入口main函数；
（2） Quicksort,快速排序算法实现部分；
（3） MedianOf3,选择三个值中值作为中点；
（4） MedianOf5,选择五个值中点作为支点；
（5） Swap,简单地交换两个元素值；
（6） Insertion,在数组长度小于cutoff值时使用插入排序来替换快速排序。
三、 测试结果
改完相关错误后运行代码，运行结果（图4所表示），在相关文件中新建文本文件，文件命名为”input.txt“。在文本文件中，打入输入数据，得出下列截图（图）。

图三：建立input并输入
回到程序，程序运行。

图四：程序运行
输入数据并确定。

图五：程序运行完成
查看output文件。

四、 分析和探讨
关键函数分析：
Main函数：
int main()
{

int i, group = 0, numbOFelements, elements, Amount;
int Array[10000];
int cutoff = 0;

FILE *InputPTR, *OutputPTR; /* input和output文件指针 */
InputPTR = fopen("input.txt", "r+");
OutputPTR = fopen("output.txt", "w+");
if (InputPTR == NULL) /* 检验input文件是否存在 */
{
W++;
InitGameBoard();
}
putin();
if ((median != 1) && (median != 3) && (median != 5))
{
N++;
putin();
}
start = GetTickCount();
Amount = fscanf(InputPTR, "%d", &numbOFelements); /* 读取每次迭代元素个数 */
while (Amount != EOF) /* 当读到不是文件末尾 */
{
start1 = GetTickCount();
group++;
fprintf(OutputPTR, "Case number: %d\nNumber of elements: %d\n",
group, numbOFelements); /*输出格式 */
for (i = 0;i<numbOFelements;i++)
{
fscanf(InputPTR, "%d", &Array[i]); /*将输入读入到数组中 */
fgetc(InputPTR);
}
fgetc(InputPTR);
QuickSort(Array, 0, numbOFelements - 1, cutoff, median); /*给数组排序 */
for (i = 0;i<numbOFelements;i++)
{
fprintf(OutputPTR, "%d ", Array[i]); /*打印排序后数组 */
}
stop1 = GetTickCount();
tim1 = stop1 - start1;
fprintf(OutputPTR, "\n 本组数据消耗时间为:%d ms ", tim1);
tim = tim1+tim;
Amount = fscanf(InputPTR, "%d", &numbOFelements);
fprintf(OutputPTR, "\n\n");
}
fclose(InputPTR);
fclose(OutputPTR);
stop = GetTickCount();
InitGameBoard();
return 0;
}
Main函数关键内容：
打开input.txt和output.txt文件；
读入数个数n；
从文件中次序读入n个数，并放到数组中；
应用Quicksort对该数组排序；
将排序后数输出到文件output.txt中；
读入下一组数个数，继续上述过程；
关闭文件。
QuickSort函数：
void QuickSort(int Array[], int min, int max, int cutoff, int median)
{
/*
median=1时使用第一个值作为支点
median=3时使用三个值中值作为支点
median=5时使用五个值中值作为支点
*/
int low, high, Pivot;
if ((max - min) == 0)
return; /* 假如数组中没有元素 */
if (min + cutoff <= max && (max - min + 1) >= median)
{ /* 检验cutoff值是否适宜 */
if (median == 1) {
Swap(&Array[min], &Array[max]);
Pivot = Array[max];
}
else if (median == 3) {
/* 调用函数MedianOf3 */
Pivot = MedianOf3(Array, min, max);
}
else if (median == 5) {
/*调用函数MedianOf5 */
Pivot = MedianOf5(Array, min, max);
}
low = min; high = max;
for (; ; )
{
while (Array[low] < Pivot)
{ /*跳过比支点小值 */
low++;
}
while (Array[--high] > Pivot)
{ /* 跳过比支点大值 */
}
if (low < high)
{ /* 交换两个值 */
Swap(&Array[low], &Array[high]);
}
else {
/* 假如指针重合了，则跳出循环 */
break;
}
}
Swap(&Array[low], &Array[max]);

QuickSort(Array, min, low - 1, cutoff, median); /* 分成两部分递归调用快速排序 */
QuickSort(Array, low + 1, max, cutoff, median);
}
else {
InsertionSort(Array, min, max); /* 对剩下数组进行插入排序 */
}
}

Quicksort函数
参数：待排数组，待排段起点位置，待排段终点位置，cutoff值，支点选择方法
If数组时空
Exit
If待排数段元素个数大于等于cutoff值，且元素个数大于等于支点选择方法所要求元素个数
依据支点选择方法选择一个元素作为支点
设置low为起点值、high为终点值
While low<=high{
While low位置值小于支点值
Low++ ；
While high位置值大于支点值
High——；
If low<high
交换low、high两个元素
}
将low位置元素和支点元素交换
Quicksort递归调用左半段
Quicksort递归调用右半段
Else
应用直接插入排序法对数组元素排序

MedianOf3：选择三个值中值作为中点；

MedianOf5：选择五个值中点作为支点；

Swap：简单地交换两个元素值；

Insertion：在数组长度小于cutoff值时使用插入排序来替换快速排序。

五、 数据异常测试案例
1. 没有配置input文件

处理方法：在特定文件夹创建input文件并输入数值保留。
2. 输入数值有误

处理方法；回到input文件输入正确数值。
六、 小结
经过这次课程设计，深入加深了我对多种排序算法认识，尤其是快速排序算法。每种排序算法全部有其不足，我们在编写程序时要用其优点。不足之处我们能够使用其它算法进行替换。从而在时间上取得愈加好效益。即使这次课程设计已经有现成代码不过我从代码中学到了部分东西，比如对文件读写操作。
以前我极少会将程序输出结果以文本格式存放起来。我认为我在数据结构这门课上还需要花很多时间，以前只学习理论知识，现在应用到实践真花费了很大力气，还需继续努力。
我同时体会到了团体合作关键性，从最初查阅资料到最终程序成功运行，和其说是学习，不如说它是合作精神和毅力考验。经过这次课程设计，我们不仅学到了很多知识和技能，更关键是团体合作。
最终，在这次实训过程中，我们深刻认识到了自己在学习方面不足之处，我知道我还有太多基础思想没有真正了解，当然我们不会气馁，我们会在以后日子里努力填补我们不足。
七、 参考文件
[1]何钦铭 陈根才 数据结构课程设计 浙江大学出版社 8月
[2] 谭浩强.C程序设计（第三版）.清华大学出版社,7月
[3] 严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社,1997年4月
八、 源程序清单
#define _CRT_SECURE_NO_DEPRECATE
#undef UNICODE
#undef _UNICODE
#include<graphics.h>
#include<stdio.h>
#include<stdlib.h>
#include<atlbase.h>
#include<statreg.h>
#include<time.h>
#include<conio.h>
#include<Windows.h>
#define SIZE 10000 /* 数组最大容量 */
#define NameMaxLength 12 //设定用户名最大字符数为：NameMaxLength-2
#define PsdMaxLength 10 //设定密码最大字符数
#define boxbkclr 0xfedcbd //绘制消息框和登录框专题填充颜色
#define drawFieldbkclr 0xFFFFFF //窗口区域背景填充颜色
/*----------------------------------------和算法相关函数和定义---------------------------------*/
int MedianOf3(int a[], int low, int high);
int MedianOf5(int a[], int low, int high);
void Swap(int *a, int *b);
void QuickSort(int a[], int left, int right, int cutoff, int median);
void InsertionSort(int a[], int low, int high);
int median;
int cutoff;

/*--------------------------------------和界面相关函数和定义------------------------------------*/
void DrawMsgBox();
void InitGameBoard();
void putin();
void InputName(); //输入账号
void InputPsd(); //输入密码
int xb00 = 0, xb01 = 0, xb02 = 0, xb03 = 0, xb04 = 0, xb05 = 0;//控件（按钮或输入框）位置坐标
int yb00 = 0, yb01 = 0, yb02 = 0, yb03 = 0, yb04 = 0, yb05 = 0;//控件（按钮或输入框）位置坐标
int T = 0;
int W = 0;
int N = 0;
int start, start1, stop, stop1;
int tim=0,tim1;
char IptName[NameMaxLength] = { ' ',' ',' ',' ',' ',' ',' ','\0' };
char IptPsd[PsdMaxLength] = { ' ',' ',' ',' ',' ',' ',' ','\0' };
int ResponseMouse(int xb0, int yb0, int xb1, int yb1, int xb2, int yb2, int xb3, int yb3, int xb4, int yb4, int xb5, int yb5)
{
int place = -1;
MOUSEMSG m;//定义鼠标消息
while (true)
{
m = GetMouseMsg();//获取一条鼠标消息
if (m.uMsg == WM_LBUTTONDOWN)
{
if (xb0 == -1)//在绘图区域任意点击
{
place = 0;
break;
}
//单击第一个对象
if ((m.x>xb0) && (m.x<xb1) && (m.y>yb0) && (m.y<yb1))
{
place = 1;
break;
}
//单击第二个对象
if ((m.x>xb2) && (m.x<xb3) && (m.y>yb2) && (m.y<yb3))
{
place = 2;
break;
}
//单击第三个对象

}
}
return place;//返回鼠标点击对象
}

/*------------------------------------主函数--------------------------------------------------------*/
int main()
{

int i, group = 0, numbOFelements, elements, Amount;
int Array[10000];
int cutoff = 0;

FILE *InputPTR, *OutputPTR; /* input和output文件指针 */
InputPTR = fopen("input.txt", "r+");
OutputPTR = fopen("output.txt", "w+");
if (InputPTR == NULL) /* 检验input文件是否存在 */
{
W++;
InitGameBoard();

}
putin();
if ((median != 1) && (median != 3) && (median != 5))
{
N++;

putin();

}
start = GetTickCount();
Amount = fscanf(InputPTR, "%d", &numbOFelements); /* 读取每次迭代元素个数 */
while (Amount != EOF) /* 当读到不是文件末尾 */
{
start1 = GetTickCount();
group++;
fprintf(OutputPTR, "Case number: %d\nNumber of elements: %d\n",
group, numbOFelements); /*输出格式 */
for (i = 0;i<numbOFelements;i++)
{
fscanf(InputPTR, "%d", &Array[i]); /*将输入读入到数组中 */
fgetc(InputPTR);
}
fgetc(InputPTR);
QuickSort(Array, 0, numbOFelements - 1, cutoff, median); /*给数组排序 */
for (i = 0;i<numbOFelements;i++)
{
fprintf(OutputPTR, "%d ", Array[i]); /*打印排序后数组 */
}
stop1 = GetTickCount();
tim1 = stop1 - start1;
fprintf(OutputPTR, "\n 本组数据消耗时间为:%d ms ", tim1);
tim = tim1+tim;
Amount = fscanf(InputPTR, "%d", &numbOFelements);
fprintf(OutputPTR, "\n\n");
}
fclose(InputPTR);
fclose(OutputPTR);
stop = GetTickCount();
InitGameBoard();
return 0;
}

/*---------------------------和算法相关函数-------------------------------------------------------*/
/******支点（pivot）选择三个值中值算法******/
int MedianOf3(int a[], int low, int high)
{
int mid = (low + high) / 2; /* 确定中间位置 */
if (a[low]>a[mid]) {
Swap(&a[low], &a[mid]);
}if (a[low]>a[high]) {
Swap(&a[low], &a[high]);
}if (a[mid]>a[high]) {
Swap(&a[mid], &a[high]);
}
Swap(&a[mid], &a[high]); /* 交换排序后中间元素和最终元素值 */
return a[high];
}
/******支点（pivot）选择五个值中值算法******/
int MedianOf5(int a[], int low, int high)
{
int i, temp, j, largest;
int Step;
Step = (high - low) / 4; /* 设定步长为四分之一，这么便能选出五个元素 */
for (j = 0; j<4; ++j)
{
largest = high - j*Step; /*每次迭代选择不一样值作为最大值 */
for (i = j + 1; i<5; ++i)
{ /* 比较每次选中值，用来找到最大值 */
if (a[high - i*Step]>a[largest])
{
largest = high - i*Step; /* 设定新最大值 */
}
}
Swap(&a[high - j*Step], &a[largest]); /* 将每次找到最大值放在每次对应位置 */
}
Swap(&a[high - Step - Step], &a[high]); /* 将选定支点放到最终面 */
Swap(&a[high - 3 * Step], &a[low]);
return a[high];
}
/******交换两个元素******/
void Swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
/******插入排序******/
void InsertionSort(int a[], int min, int max)
{
int j, i, temp;
for (i = min;i <= max;i++)
{
temp = a[i];
for (j = i;j>min && a[j - 1]>temp;j--)
a[j] = a[j - 1];
a[j] = temp;
}
}
/******快速排序******/
void QuickSort(int Array[], int min, int max, int cutoff, int median)
{
/*
median=1时使用第一个值作为支点
median=3时使用三个值中值作为支点
median=5时使用五个值中值作为支点
*/
int low, high, Pivot;
if ((max - min) == 0)
return; /* 假如数组中没有元素 */

if (min + cutoff <= max && (max - min + 1) >= median)
{ /* 检验cutoff值是否适宜 */
if (median == 1) {
Swap(&Array[min], &Array[max]);
Pivot = Array[max];
}
else if (median == 3) {
/* 调用函数MedianOf3 */
Pivot = MedianOf3(Array, min, max);
}
else if (median == 5) {
/*调用函数MedianOf5 */
Pivot = MedianOf5(Array, min, max);
}
low = min; high = max;
for (; ; )
{
while (Array[low] < Pivot)
{ /*跳过比支点小值 */
low++;
}
while (Array[--high] > Pivot)
{ /* 跳过比支点大值 */
}
if (low < high)
{ /* 交换两个值 */
Swap(&Array[low], &Array[high]);
}
else {
/* 假如指针重合了，则跳出循环 */
break;
}
}
Swap(&Array[low], &Array[max]);

QuickSort(Array, min, low - 1, cutoff, median); /* 分成两部分递归调用快速排序 */
QuickSort(Array, low + 1, max, cutoff, median);
}
else {
InsertionSort(Array, min, max); /* 对剩下数组进行插入排序 */
}

}
/*---------------------------和界面相关函数-------------------------------------------------------*/
/******按键设置******/
void InitGameBoard()
{
int choice;//点击了哪个按钮
char str_regist[] = "退出程序";
initgraph(500, 500);
setorigin(0, 0);//设置绘图窗口区域左上角为逻辑坐标原点
setbkcolor(0xFFFFFF);//设置背景颜色，0xFFFFFF为白色
DrawMsgBox();//绘制开启画面上两个按钮
choice = ResponseMouse(xb00, yb00, xb01, yb01, xb02, yb02, xb03, yb03, xb04, yb04, xb05, yb05);
if (choice == 1)
{
exit(0);
}

}
/******结束界面******/
void DrawMsgBox()
{
int xb0, xb1, yb0, yb1;
xb0 = xb1 = yb0 = yb1 = 0;
int w = 500;//消息框宽度为w
int h = 500;//消息框高度为h
int btnw = 80;//按钮宽度为btnw
int btnh = 30;//按钮高度为btnh

char timc[6];
setlinecolor(RGB(135, 206, 250));//设置线条颜色
setfillcolor(RGB(135, 206, 250));//设置填充颜色
fillroundrect((500 - w) / 2, (500 - h) / 2, (500 + w) / 2, (500 + h) / 2, 20, 20);//用颜色填充矩形
xb0 = 500 / 2 - btnw / 2;//按钮1位置坐标
yb0 = 500 / 2 - btnh / 2;//按钮1位置坐标
xb1 = 500 / 2 + btnw / 2;//按钮1位置坐标
yb1 = 500 / 2 + btnh / 2;//按钮1位置坐标
xb00 = xb0;
xb01 = xb1;
yb00 = yb0;
yb01 = yb1;
setlinecolor(WHITE);
setfillcolor(RGB(135, 206, 250));
fillroundrect(xb0, yb0, xb1, yb1, 10, 10);//用颜色填充按钮1
setcolor(RED);
setbkmode(TRANSPARENT);//设置文字输出时背景模式为透明色
settextstyle(28, 0, _T("楷体"));

if (W == 1)
{
outtextxy(150, 150, "没有找到input文件");
}
else
{
outtextxy(100, 100, "感谢使用");
outtextxy(200, 150, "优化排序已经完成");

_itoa_s(tim, timc, 10);//数字转化为字符
outtextxy(2, 300, "所消耗总时间为:");
outtextxy(300, 300, timc);
}
settextstyle(18, 0, _T("楷体"));
outtextxy(xb0 + 6, yb0 + 6, "退出程序");

}
/******cutoff输入******/
void putin()
{
IMAGE img;
initgraph(500, 462);
int xb0, xb1, xb2, xb3, xb4, xb5, yb0, yb1, yb2, yb3, yb4, yb5, x10, y10, x11, y11;
xb0 = xb1 = xb2 = xb3 = xb4 = xb5 = yb0 = yb1 = yb2 = yb3 = yb4 = yb5 = x10 = y10 = x11 = y11 = 0;
int choice;//点击了哪个按钮
int w = 360;//消息框宽度为w
int h = 180;//消息框高度为h
int btnw = 210;//输入框、按钮宽度为btnw
int btnh = 30;//输入框、按钮高度为btnh
x10 = (470 - w) / 2;
y10 = (462 - h) / 2;
x11 = (470 + w) / 2;
y11 = (462 + h) / 2;

cleardevice();
setlinecolor(boxbkclr);
setfillcolor(boxbkclr);
xb0 = x10 + btnw / 2;
yb0 = y10 + btnh;
xb1 = xb0 + btnw;
yb1 = yb0 + btnh;
xb2 = xb0;
yb2 = yb1 + btnh / 2;
xb3 = xb1;
yb3 = yb2 + btnh;
xb4 = xb0;
yb4 = yb3 + btnh / 2;
xb5 = xb1;
yb5 = yb4 + btnh;
xb00 = xb0;
xb01 = xb1;
xb02 = xb2;
xb03 = xb3;
yb00 = yb0;
yb01 = yb1;
yb02 = yb2;
yb03 = yb3;
xb04 = xb4;
xb