实验六 排序相关典型算法实现
一 实验目的
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 j=0;
//直接排序只有第一个元素有序
for ( int i = 2; i <= l.Length; i++)//从2开始排序
{
l.Comparison+=2;
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.Comparison+=2;
l.Arr[j + 1] = l.Arr[j];
l.Move+=2;
}
l.Comparison+=2;//判断跳出循环还有一次
l.Arr[j + 1] = l.Arr[0];
}
l.Move+=2;
}
}
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-j+1; i++) //一次内部循环可以将一个数“送”到正确位置
{ //比如第一次内部循环结束后可以让arr[9]变成最大值9
max = 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.Move+=3;
}
}
}
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 = i+1; 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 (Sqlist&l, 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(Sqlist&l, 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和j+1同理
}
int main()
{
Sqlist l;
InitialSqlist(l);
InputSqlist(l);
QuickSort(l, 1, l.Length);
OutPutSqlist(l);
}四 调试情况、设计技巧及体会
目录
实验一：完成插入排序，冒泡排序，选择排序的操作，并且统计其移动次数和比较次数。
实验二：完成快速排序、堆排序、希尔排序中任意一个（待更新）。
在实现本次实验的相关排序算法的实现方法中，以下是我犯的错误以及相应的修改方法以及收获：
1.错误：未正确处理边界条件。
修改方法：在实现插入排序算法时，要确保对数组的索引进行正确的边界检查。例如，循环变量的范围应该是从1到n（数组长度），而不是从0到n-1。此外，还要确保在插入元素时，正确处理数组的边界情况，以避免越界错误。
收获：在编写代码时，始终要注意数组索引的边界情况，并进行适当的边界检查。确保循环变量的范围和条件正确设置，以避免数组越界错误。
2.错误：未正确处理重复元素的情况。
修改方法：在实现插入排序算法时，要考虑重复元素的情况。如果存在重复元素，确保它们被正确地插入到已排序的子数组中，并保持它们的相对顺序。可以通过在插入位置之前或之后进行适当的调整来处理重复元素。
收获：处理重复元素时，要仔细考虑它们的相对顺序，并确保它们被正确地插入到已排序的子数组中。可以使用适当的比较条件和调整方法来处理重复元素，以获得正确的排序结果。
3.错误：未正确统计移动和比较次数。
修改方法：在统计移动和比较次数时，要确保在实际发生移动和比较操作后进行统计。例如，在元素交换或插入位置时，增加相应的计数器。同时，要注意统计的粒度，可以在排序算法的最后输出统计结果，或者在每一次移动或比较操作后即时输出统计结果。
收获：在编写代码时，要注意在正确的位置统计移动和比较次数。确保在实际发生移动和比较操作后进行计数，以获得准确的统计结果。同时，要灵活选择统计的粒度，以适应不同的需求。
4.错误：未正确处理数组为空或只有一个元素的情况。
修改方法：在实现选择排序算法时，要考虑特殊情况，如数组为空或只有一个元素的情况。在这种情况下，数组已经是有序的，无需进行排序操作。可以通过添加条件判断来处理这种情况，直接返回或跳过排序操作。
收获：在编写代码时，要考虑特殊情况，并进行相应的处理。特别是在排序算法中，要注意处理数组为空或只有一个元素的情况，以避免不必要的操作和错误。
在这次实验中我收获了很多，这将未我将来学好算法打下良好的基础，同时我觉得自己还应该继续加深对这些算法的理解，并进行相关的改写来实现一些功能，让他们得到应用。
?
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！