邯山手机网站建设,哪个企业提供电子商务网站建设外包,网站开发技术服务合同范本,网站ico图标 代码一 实验目的
1#xff0e;熟悉并掌握各种排序方法的设计思路。
2#xff0e;掌握各种具体排序算法在计算机上的实现。
3#xff0e;掌握各种排序方法的性能比较。
二 实验内容及要求
实验内容#xff1a;
1. 编程实现如下功能#xff1a;
#xff08;1#xff09…一 实验目的
1熟悉并掌握各种排序方法的设计思路。
2掌握各种具体排序算法在计算机上的实现。
3掌握各种排序方法的性能比较。
二 实验内容及要求
实验内容
1. 编程实现如下功能
1输入同样一组整型数据作为待排序记录的关键字序列。
2在进行直接插入排序的同时统计在排序方法中对关键字的比较次数和移动次数并输出统计结果。
3在进行冒泡排序的同时统计在排序方法中对关键字的比较次数和移动次数并输出统计结果。
4在进行简单选择排序的同时统计在排序方法中对关键字的比较次数和移动次数并输出统计结果。
2. 编程实现如下功能之一
1希尔排序
2快速排序
3堆排序
实验要求
1.键盘输入数据
2.屏幕输出运行结果。
3.要求记录实验源代码及运行结果。
4.运行环境CodeBlocks/Dev c/VC6.0等C编译环境
三 实验方法及运行结果
实验一完成插入排序冒泡排序选择排序的操作并且统计其移动次数和比较次数。
一 算法设计思路
包括五个功能函数 InputSqlist(Sqlist l)、InitialSqlist(Sqlist l)、OutPutSqlist(Sqlist l)、BubbleSort(Sqlist l)、SelectSort(Sqlist l)、 InsertSort(Sqlist l)、和一个主函数
前三个函数分别对应初始化、输入和输出功能。
直接插入排序算法InsertSort(Sqlist l)的思路
初始时将第一个元素视为已排序序列其余元素为未排序序列。然后依次将未排序序列中的元素插入到已排序序列的正确位置直到所有元素都被插入到已排序序列中完成排序。
首先从第二个元素开始将其视为当前要插入的元素。接着将当前元素与已排序序列中的元素逐个比较直到找到插入位置或者已经比较到已排序序列的第一个元素为止。然后在比较的方法中如果当前元素小于已排序序列中的某个元素则将该元素后移一位为当前元素腾出插入位置。将当前元素插入到正确的位置即将其放置在比它大的元素之前。最后重复上面两步直到所有元素都被插入到已排序序列中。
冒泡排序算法BubbleSort(Sqlist l)的思路
基本思想是通过不断比较相邻元素的大小将较大的元素逐步交换到右侧从而实现排序的目的。从序列的第一个元素开始依次比较相邻的两个元素。如果前一个元素大于后一个元素则交换它们的位置将较大的元素往右移动。继续比较下一对相邻元素重复上一步直到比较到序列的倒数第二个元素。重复执行执行上述步骤直到没有需要交换的元素即序列已经完全排序。
选择排序算法SelectSort(Sqlist l)的思路
选择排序是每次从待排序的序列中选择最小或最大的元素放到已排序序列的末尾或开头从而逐步形成有序序列。
首先遍历待排序序列将第一个元素视为当前最小或最大元素。然后从剩余未排序的元素中依次找到最小或最大的元素并记录其位置。接着将找到的最小或最大元素与当前最小或最大元素进行交换将最小或最大元素放到已排序序列的末尾或开头。最后重复上面两步直到所有元素都被放置到正确的位置上。
选择排序算法不断地选择最小或最大元素并将其放置到已排序序列的末尾或开头。这样每一次选择排序都会确定一个元素的最终位置直到所有元素都被放置到正确的位置上完成排序。选择排序每次只需要进行一次交换操作。
二 源程序代码
/*1. 编程实现如下功能
1输入同样一组整型数据作为待排序记录的关键字序列。
2在进行直接插入排序的同时统计在排序过程中对关键字的比较次数和移动次数并输出统计结果。
3在进行冒泡排序的同时统计在排序过程中对关键字的比较次数和移动次数并输出统计结果。
4在进行简单选择排序的同时统计在排序过程中对关键字的比较次数和移动次数并输出统计结果。
*/
#define MAXSIZE 1000
typedef struct Sqlist
{int Arr[MAXSIZE];int Length;int Comparison;int Move;
};
void InsertSort(Sqlist l)
{int j0;//直接排序只有第一个元素有序for ( int i 2; i l.Length; i)//从2开始排序{l.Comparison2;if (l.Arr[i] l.Arr[i - 1]){l.Arr[0] l.Arr[i];l.Arr[i] l.Arr[i - 1];l.Move 4;for (j i - 2; l.Arr[0] l.Arr[j];--j){l.Comparison2;l.Arr[j 1] l.Arr[j];l.Move2;}l.Comparison2;//判断跳出循环还有一次l.Arr[j 1] l.Arr[0];}l.Move2;}
}void InputSqlist(Sqlist l)
{cout 请输入要输入的数组的长度 endl;cin l.Length;cout 请输入数组的数据 endl;for (int i 1; i l.Length; i)cin l.Arr[i];//此处arr[0]作为哨兵单元不放置元素
}
void InitialSqlist(Sqlist l)
{for (int i 0; i MAXSIZE; i)l.Arr[i] 0;l.Length 0;l.Move 0;l.Comparison 0;
}void OutPutSqlist(Sqlist l)
{for (int i 1; i l.Length; i)cout l.Arr[i] ;cout \n此次的比较次数为 l.Comparison endl;cout 此次的移动次数 l.Move endl;
}
void BubbleSort(Sqlist l)
{int max 0, min 0; int tem;for (int j 1; j l.Length-1; j) //此处循环length-1次 就是数组长度-1次内部操作{for (int i 2; i l.Length-j1; i) //一次内部循环可以将一个数“送”到正确位置{ //比如第一次内部循环结束后可以让arr[9]变成最大值9max l.Arr[i - 1];min l.Arr[i];l.Comparison;if (min max){tem max;max min;min tem;}l.Arr[i - 1] max;l.Arr[i] min;l.Move3;}}
}
void SelectSort(Sqlist l)
{for (int i 1; i l.Length; i){int flag i;int tem; int min l.Arr[i];for (int j i1; j l.Length; j){l.Comparison;if (min l.Arr[j]){min l.Arr[j];flag j;}}tem l.Arr[i];l.Arr[i] min;l.Arr[flag] tem;l.Move 3;}
}
int main()
{Sqlist l; int n 0;InitialSqlist(l);InputSqlist(l);cout \n插入排序 endl;InsertSort(l);OutPutSqlist(l);InitialSqlist(l);InputSqlist(l);cout \n冒泡排序 endl;BubbleSort(l);OutPutSqlist(l);InitialSqlist(l);InputSqlist(l);cout \n选择排序 endl;SelectSort(l);OutPutSqlist(l);return 0;
} 实验二完成快速排序、堆排序、希尔排序中任意一个待更新。
一 算法设计思路
快速排序QuickSort (Sqlistl, int left, int right)算法思路
具体的步骤如下选择一个基准元素选择第一个。将序列中的元素分为两部分小于等于基准元素的放在左边大于基准元素的放在右边。这个方法称为分区。对左右两个子序列分别进行快速排序递归地重复上述步骤直到子序列的长度为1或0此时子序列已经有序。合并左子序列、基准元素和右子序列得到最终的有序序列。
二 源程序代码 typedef struct Sqlist
{int Arr[MAXSIZE];int Length;int Comparison;int Move;
};
void InputSqlist(Sqlist l)
{cout 请输入要输入的数组的长度 endl;cin l.Length;cout 请输入数组的数据 endl;for (int i 1; i l.Length; i)cin l.Arr[i];//此处arr[0]作为哨兵单元不放置元素
}
void InitialSqlist(Sqlist l)
{for (int i 0; i MAXSIZE; i)l.Arr[i] 0;l.Length 0;l.Move 0;l.Comparison 0;
}
void OutPutSqlist(Sqlist l)
{for (int i 1; i l.Length; i)cout l.Arr[i] ;/*cout \n此次的比较次数为 l.Comparison endl;cout 此次的移动次数 l.Move endl;*/
}void QuickSort(Sqlistl, int left, int right)
{int i left - 1, j right 1, x l.Arr[left right 1]; //l代表数组起始端 r代表数组结束if (left right) return;//递归结束条件while (i j){do i; while (l.Arr[i] x); //确保l.Arr[i]全是小于x的do j--; while (l.Arr[j] x); //确保l.Arr[j]全是大于x的if (i j) swap(l.Arr[i], l.Arr[j]); //当停下时 i和j 都不满足 所以交换}QuickSort(l, left, j); QuickSort(l, j 1, right);// 也可以是 QuickSort(l.Arr,l,i-1);QuickSort(l.Arr,i,r);
// i本身在左边最后一次执行的时候 到区间中点右边 所以更偏左边的是i-1 ,递归区间实现全覆盖但不交叉所以右边是i,r 左边是 l,i-1
// j和j1同理
}
int main()
{Sqlist l;InitialSqlist(l);InputSqlist(l);QuickSort(l, 1, l.Length);OutPutSqlist(l);
}
四 调试情况、设计技巧及体会
目录
一 实验目的
二 实验内容及要求
实验内容
1. 编程实现如下功能
2. 编程实现如下功能之一
实验要求
三 实验方法及运行结果
实验一完成插入排序冒泡排序选择排序的操作并且统计其移动次数和比较次数。
一 算法设计思路
二 源程序代码 实验二完成快速排序、堆排序、希尔排序中任意一个待更新。
一 算法设计思路
二 源程序代码
四 调试情况、设计技巧及体会 在实现本次实验的相关排序算法的实现方法中以下是我犯的错误以及相应的修改方法以及收获
1.错误未正确处理边界条件。
修改方法在实现插入排序算法时要确保对数组的索引进行正确的边界检查。例如循环变量的范围应该是从1到n数组长度而不是从0到n-1。此外还要确保在插入元素时正确处理数组的边界情况以避免越界错误。
收获在编写代码时始终要注意数组索引的边界情况并进行适当的边界检查。确保循环变量的范围和条件正确设置以避免数组越界错误。
2.错误未正确处理重复元素的情况。
修改方法在实现插入排序算法时要考虑重复元素的情况。如果存在重复元素确保它们被正确地插入到已排序的子数组中并保持它们的相对顺序。可以通过在插入位置之前或之后进行适当的调整来处理重复元素。
收获处理重复元素时要仔细考虑它们的相对顺序并确保它们被正确地插入到已排序的子数组中。可以使用适当的比较条件和调整方法来处理重复元素以获得正确的排序结果。
3.错误未正确统计移动和比较次数。
修改方法在统计移动和比较次数时要确保在实际发生移动和比较操作后进行统计。例如在元素交换或插入位置时增加相应的计数器。同时要注意统计的粒度可以在排序算法的最后输出统计结果或者在每一次移动或比较操作后即时输出统计结果。
收获在编写代码时要注意在正确的位置统计移动和比较次数。确保在实际发生移动和比较操作后进行计数以获得准确的统计结果。同时要灵活选择统计的粒度以适应不同的需求。
4.错误未正确处理数组为空或只有一个元素的情况。
修改方法在实现选择排序算法时要考虑特殊情况如数组为空或只有一个元素的情况。在这种情况下数组已经是有序的无需进行排序操作。可以通过添加条件判断来处理这种情况直接返回或跳过排序操作。
收获在编写代码时要考虑特殊情况并进行相应的处理。特别是在排序算法中要注意处理数组为空或只有一个元素的情况以避免不必要的操作和错误。
在这次实验中我收获了很多这将未我将来学好算法打下良好的基础同时我觉得自己还应该继续加深对这些算法的理解并进行相关的改写来实现一些功能让他们得到应用。
