算法设计技能训练报告.doc

算法设计技能训练报告

淮 阴 工 学 院
算法设计技能训练报告

姓 名:

学 号：

班 级:
NIIT
学 院:
计算机及软件工程学院
专 业:
计算机科学及技术
题 目:

排序算法的比较

指导教师：

目录
课题任务描述 3
系统设计 4
2.1功能模块设计 4
2.2数据结构设计 5
2.3算法设计 5
详细设计 6
测试 7
结 论 8
致 谢 9
参 考 文 献 10

课题任务描述
利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。
1.1 要求：
1.1.1  至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。
1.1.2 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。
1.1.3  如果采用4种或4种以上的方法者，可适当加分。

系统设计
2.1功能模块设计

2.2数据结构设计
int A[n];
srand(time(0));
for(int i=0;i<n;i++)
A[i]=rand()%n;
利用数组A进行生成随机数组然后进行排序
struct node
{
int index;
node* next;
};
class MyLis
private:
node* head;
int length;
利用链表进行排序

2.3算法设计
1.直接插入排序
原理：将数组分为无序区和有序区两个区，然后不断将无序区的第一个元素按大小顺序插入到有序区中去，最终将所有无序区元素都移动到有序区完成排序。
2.希尔排序
原理：又称增量缩小排序。先将序列按增量划分为元素个数相同的若干组，使用直接插入排序法进行排序，然后不断缩小增量直至为1，最后使用直接插入排序完成排序。
要点：增量的选择以及排序最终以1为增量进行排序结束。
1.冒泡排序
原理：将序列划分为无序和有序区，不断通过交换较大元素至无序区尾完成排序。
要点：设计交换判断条件，提前结束以排好序的序列循环
2.快速排序
原理：不断寻找一个序列的中点，然后对中点左右的序列递归的进行排序，直至全部序列排序完成，使用了分治的思想。
1.直接选择排序
原理：将序列划分为无序和有序区，寻找无序区中的最小值和无序区的首元素交换，有序区扩大一个，循环最终完成全部排序。
.堆排序
原理：利用大根堆或小根堆思想，首先建立堆，然后将堆首及堆尾交换，堆尾之后为有序区。
归并排序
原理：将原序列划分为有序的两个序列，然后利用归并算法进行合并，合并之后即为有序序列。

测试

图 4.1

图 4.2

图4.3

结 论
（1）平方阶(O(n2))排序
    　一般称为简单排序，例如直接插入、直接选择和冒泡排序；

（2）线性对数阶(O(nlgn))排序
    　如快速、堆和归并排序；

（3）O(n1+￡)阶排序
    　￡是介于0和1之间的常数，即0<￡<1，如希尔排序；

（4）线性阶(O(n))排序
    　如桶、箱和基数排序。

各种排序方法比较

     简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。

影响排序效果的因素

    　因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：
　　①待排序的记录数目n；
　　②记录的大小(规模)；
　　③关键字的结构及其初始状态；
　　④对稳定性的要求；
　　⑤语言工具的条件；
　　⑥存储结构；
　　⑦时间和辅助空间复杂度等。

不同条件下，排序方法的选择

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
    　当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
    　快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
    　堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
    　若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的  排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。

排序算法的稳定性
 1） 稳定的：如果存在多个具有相同排序码的记录，经过排序后，这些记录的相对次序仍然保持不变，则这种排序算法称为稳定的。
    插入排序、冒泡排序、归并排序、分配排序（桶式、基数）都是稳定的排序算法。
    2）不稳定的：否则称为不稳定的。
    直接选择排序、堆排序、shell排序、快速排序都是不稳定的排序算法

致 谢
谢我的老师，他们严谨细致、一丝不苟的作风一直是我工作、学习中的榜样；他们循循善诱的教导和不拘一格的思路给予我无尽的启迪。
这片论文的每个实验细节和每个数据，都离不开你的细心指导。而你开朗的个性和宽容的态度，帮助我能够很快的融入我们这个新的实验室
感谢我的同门，谢谢你们给予我的帮助！
感谢我的朋友，感谢你们在我失意时给我鼓励，在失落时给我支持，感谢你们和我一路走来，让我在此过程中倍感温暖！
感谢我的家人——我的父母、姐姐和弟弟。没有你们，就不会有今天的我！我一直感恩，感恩于我可以拥有一个如此温馨的家庭，让我所有的一切都可以在你们这里得到理解及支持，得到谅解和分担。我爱你们，爱我们的家！
一个人的成长绝不是一件孤立的事，没有别人的支持及帮助绝不可能办到。我感谢可以有这样一个空间，让我对所有给予我关心、帮助的人说声“谢谢”！今后，我会继续努力，好好工作！好好学习！好好生活！！

参 考 文 献

1 刘国钧，陈绍业，王凤翥.图书馆目录.第1版.北京：高等教育出版社，1957
2 傅承义，陈运泰，祁贵中.地球物理学基础.北京：科学出版社，1985，447
3 华罗庚，王元.论一致分布及近似分析.中国科学，1973（4）：339~357
4 张筑生.微分半动力系统的不变集研究：[学位论文]，北京：数学系统学研究所，1983
5 Borko H，Bernier C L．Indexing concepts and methods . New York: Academic Pr,1978
6《机程序设计艺术》英文名称：The Art of Computer Programming
作者：Donald.E.Knuth
7.《计算机导论》
名称：Introduction to Algorithms

作者：Thomas H. Cormen ，Charles E. Leiserson ，Ronald L. Rivest ，Clifford Stein 
《C语言程序设计实用教程》全面介绍了C语言的基础知识和程序设计方法，共分为三部分，由浅到深，再到综合应用。第一部分是基础知识的应用，包括第1章到第3章；第二部分为高级知识的应用，包括第4章到第7章；第三部分是综合应用，包括第8章。各章基本知识及典型例题及上机实训紧密结合，每章后面提供了大量的习题。为了满足国家计算机等级考试的要求，《C语言程序设计实用教程》介绍了Visual C++ 6.0的开发环境，教材内容涵盖了《全国计算机等级考试考试大纲》(C语言程序设计部分)。 《C语言程序设计实用教程》可以作为高职高专各专业学生的教材，也可以作为普通高等院校各专业学生的教材，还可以作为全国计算机等级考试(二级C语言程序设计)的辅导

wer by YOZOSOFT

代码
#include<iostream>
#include<fstream>
using namespace std;
#include<time.h>
#include<stdlib.h>
# define n 2000
#define lj 20
struct node
{

int index;
node* next;
};

class MyList
{
private:

node* head;
int length;
public:

MyList()
{
head = NULL;//头指针为空
length = 0;//长度为0
}

~MyList()
{

node* left = head;
node* right = NULL;
while (left != NULL)
{
right = left;
left = left->next;
delete right;
}
}

void addNode(int user_index)
{
if (isEmpty())
{

head = new node();
head->next = NULL;
head->index = user_index;
}
else
{
//创建一个新的节点
node* newnode = new node();
newnode->index = user_index;
newnode->next = NULL;
//将节点添加到链表的最末端
node* t = head;
while (t->next!=NULL)
{

t = t->next;
}

t->next = newnode;
length++;
}
}

int ljcode;
int getLength()
{
return length;
}

void display()
{

if (isEmpty())
{
cout << "The list is empty!";
return;
}
node* temp = head;
while (temp)
{

cout << temp->index;
if (!temp->next)
//已至链表尾，可以结束输出了。
{
break;
}
cout << "->";
temp = temp->next;
}

cout << endl;

}
char ljcode1;
void lhInput()
{

for (int i = 12; i>0; i--)
{

addNode(i);
}
}
bool isEmpty()
{
if (head==NULL)
{

return true;
}
else
{

int ljcode=0;
return false;
}
}
void bubbleSort()
{

if (isEmpty())
{

int ljcode=1;
return;
}
//temp指针用来进行指向要交换的两个节点的左边一个
node* temp = head;
while (temp && temp->next)
{
if (temp->index > temp->next->index)
{

exchangeNode(temp, temp->next);
}
}
//尾指针总是指向已经排好的元素的首地址，这里我们先移到链表尾部等待
node* tail = head;
while (tail->next)
{

tail = tail->next;
}
//外层还是数组的思想，内层就是链表的思想了，
//为什么外层要用数组的思想呢？因为这样比较简洁，不易搞错
for (int i = 0; i < length; i++)
{

temp = head;
while (temp->next != tail)
{
if (temp->index > temp->next->index)
{

exchangeNode(temp, temp->next);
}
}
tail = temp;
}
}
//交换相邻两个节点
void exchangeNode(node* left, node* right)
{
//如果left是头结点
if (left==head)
{

left->next = right->next;
right->next = left;
head = right;
return;
}
//找到左节点的前一个节点
node* before_left = head;
while (before_left->next!=left)
{

before_left = before_left->next;
}
before_left->next = right;
left->next = right->next;
right->next = left;
}
};
//堆的冒泡排序
int ljcode2=0;
void paixu(){
MyList hengbao;
hengbao.lhInput();
hengbao.display();
hengbao.bubbleSort();
hengbao.display();
int ljcode=0;

}
void InsertionSort(int *a, int len) //插入排序函数
{
for (int j=1; j<len; j++)
{
int key = a[j];
int i = j-1;
int ljcode=0;
while (i>=0 && a[i]>key)
{
a[i+1] = a[i];
i--;
}
a[i+1] = key;
}
}

void ShellSort(int *a, int len) //希尔排序代码
{
int h = 1;
while( h<len )
h = 3*h + 1;
while( h>0 )
{
for (int j=h; j<len; j++)
{
int key = a[j];
int i = j-h;
while( i>=0 && a[i]>key )
{
a[i+h] = a[i];
i = i-h;
}
int ljcode=0;
a[i+h] = key;
}
h = h/3;
}
}
//冒泡排序
void bubblesort(int *a,int len){

int i,j;
for( i=0;i<len-1;i++)
{
for( j=i+1;j<=len-1;j++)
if(a[i]<a[j])
{
int t=a[i];
a[j]=a[i];
a[i]=t;
}
}
}
//快速排序
void quickSort(int s[], int l, int r )
{
if (l<r)
{
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j]>= x) // 从右向左找第一个小于x的数
j--;
if(i < j)
s[i++] = s[j];
while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数
i++;
if(i < j)
s[j--] = s[i];
}
s[i] = x;
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
//选择排序
void SelectSort(int *a, int len)
{
for (int i=0; i<len-1; i++)
{
int k = i;
int key = a[i];
for (int j=i+1; j<len; j++)
{
if (a[j]<key)
{
k = j;
key = a[j];
}
}
if (k!=i)
swap(a[i], a[k]);
}
}

void MaxHeapify(int *a, int i, int heapSize)
{
int l = (i+1)*2-1;
int r = (i+1)*2;
int largest;

if (l<=heapSize && a[l]>a[i])
largest = l;
else
largest = i;

if (r<=heapSize && a[r]>a[largest])
largest = r;

if (largest!=i)
{
swap(a[i], a[largest]);
MaxHeapify(a, largest, heapSize);
}
}
// 创建最大堆
void BuildMaxHeap(int *a, int len)
{
for (int i=len/2-1; i>=0; i--)
{
MaxHeapify(a, i, len-1);
}
}
// 堆排序
void HeapSort(int *a, int len)
{
BuildMaxHeap(a, len);
for (int i=len-1; i>0; i--)
{
swap(a[0], a[i]);
MaxHeapify(a, 0, i-1);
}
}
//归并排序
void merge(int *data, int p, int q, int r)
{
int n1, n2, i, j, k;
int *left=NULL, *right=NULL;

n1 = q-p+1;
n2 = r-q;

left = (int *)malloc(sizeof(int)*(n1));
right = (int *)malloc(sizeof(int)*(n2));
for(i=0; i<n1; i++) //对左数组赋值
left[i] = data[p+i];
for(j=0; j<n2; j++) //对右数组赋值
right[j] = data[q+1+j];
i = j = 0;
k = p;
while(i<n1 && j<n2) //将数组元素值两两比较，并合并到data数组
{
if(left[i] <= right[j])
data[k++] = left[i++];
else
data[k++] = right[j++];
}

for(; i<n1; i++) //如果左数组有元素剩余，则将剩余元素合并到data数组
data[k++] = left[i];
for(; j<n2; j++) //如果右数组有元素剩余，则将剩余元素合并到data数组
data[k++] = right[j];
}

void mergeSort(int *data, int p, int r)
{
int q;
if(p < r) //只有一个或无记录时不须排序
{
q = (int)((p+r)/2); //将data数组分成两半
mergeSort(data, p, q); //递归拆分左数组
mergeSort(data, q+1, r); //递归拆分右数组
merge(data, p, q, r); //合并数组
}
}

void output(int *A){
ofstream output("c:\\textcode.txt",ios_base::out);
output<<"数组元素如下：";
for(int i=0;i<n;i++)
output<<A[i]<<',';
output.close();
ofstream output1("c:\\bincode.bin",ios::binary);
for(int i=0;i<n;i++)
output1<<A[i]<<",";
output1.close ();

}

int main()
{
int A[n];
srand(time(0));
for(int i=0;i<n;i++)
A[i]=rand()%n;

cout<<" 排序算法的性能"<<endl;
cout<<" 1.插入排序"<<endl;
cout<<" 2.希尔排序"<<endl;
cout<<" 3.起泡排序"<<endl;
cout<<" 4.快速排序"<<endl;
cout<<" 5.选择排序"<<endl;
cout<<" 6.堆排序"<<endl;
cout<<" 7.归并排序"<<endl;
cout<<" 8.链表的冒泡排序"<<endl;
cout<<" 请输入选择："<<endl;

int m;
cin>>m;
switch(m){
case 1:

InsertionSort(A,n);
output(A);
cout<<"已经进行插入排序"<<endl;
cout<<"结果已存入文件"<<endl;
break;
case 2:

ShellSort(A, n) ;
output(A);
cout<<"已经进行希尔排序"<<endl;
cout<<"结果已存入文件"<<endl;
break;
case 3:

bubblesort(A,n);
output(A);
cout<<"已经进行起泡排序"<<endl;
cout<<"结果已存入文件"<<endl;
break;
case 4:

quickSort(A,0,n-1);
output(A);
cout<<"已经进行快速排序"<<endl;
cout<<"结果已存入文件"<<endl;
break;
case 5:
SelectSort(A, n);
output(A);
cout<<"已经进行选择排序"<<endl;
cout<<"结果已存入文件"<<endl;
break;
case 6:

HeapSort(A, n);
output(A);
cout<<"已经进行堆排序"<<endl;
cout<<"结果已存入文件"<<endl;
break;
case 7:

mergeSort(A, 0, n-1) ;
output(A);
cout<<"已经进行归并排序"<<endl;
cout<<"结果已存入文件"<<endl;
break;
case 8:

cout<<"冒泡排序的结果为"<<endl;
paixu();
cout<<"链表的冒泡排序"<<endl;
break;
default :
cout<<"您的输入有误"<<endl;
cout<<"请重新输入"<<endl;

}

return 0;
24 / 24