对多维信号进行插入排序、希尔排序、快速排序、堆排序

2024-06-18 01:34| 来源: 网络整理| 查看: 265

1.实验目的

深入理解各种排序的算法思想、方法、稳定性及时间和空间复杂度；掌握插入排序、交换排序、选择排序的算法实现；能够实现多维信号的排序操作；提高实际动手进行程序设计的能力。 2.实验内容与要求实验内容：多维数字信号的排序算法实验要求： 1)深入理解各种排序的算法思想、方法、稳定性及时间和空间复杂度；建议采用C、C++等高级语言；不能基于已有的模板类库和算法库实现上述功能，但可参考开源代码；课前编写实现实验内容的程序；所设计的程序需要包含一个测试主函数，用于运行验证所设计程序的正确性； 6)测试程序的输入数据以文本文件形式提供，输出亦为文本文件形式；各个数据点之间以回车换行分开，每个数据点的各维之间以逗号分隔开。 7)数据点个数要大于1000，每个数据点的维数至少为2.提交实验报告。 3.算法描述与流程插入排序：外层循环表示的是排序的趟数，n个数字需要n-1趟，因此，外层循环的次数是n-1次；同时也代表数的位置。内层循环表示的是每一趟排序的数字。根据插入排序的思想，第i趟排序时，有序数组中的数字就有i个，就需要进行i次比较，因此循环i次。注意采用的是从后往前进行比较。从后往前扫描的时候，如果必须插入的数大于有序数组中当前位置的数，则有序数组中的数和它之后的数均往后移一个位置，否则，把插入的数插入到有序数组中。

希尔排序: 希尔排序又叫做缩小增量排序，其本质还是插入排序，只是在将待排序序列按照某种规则分成几个子序列，分别对这几个子序列进行直接插入排序，这个规则的体现就是增量的选取，如果选择增量为1那么就是直接插入排序。而希尔排序的每一趟排序都会使整个序列变得有序，等到整个序列有序了，那么再使用增量为1的插入排序的话那么就会使得排序的效率提高。

快速排序: 分解：在R[low…high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low…pivotpos-1)和R[pivotpos+1…high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。划分的关键是要求出基准记录所在的位置pivotpos。　求解：通过递归调用快速排序对左、右子区间R[low…pivotpos-1]和R[pivotpos+1…high]快速排序。组合：因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。

堆排序: 1.首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端 2.将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1 3.将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组

#include #include #include #include #include #include const int NDIM = 3; typedef float KeyType; typedef int InfoType; const int test_num =10000; typedef struct { KeyType key;//关键字项 InfoType ID;//其他数据项，类型为 float Item[NDIM];//NDIM维数组 }RecType;//查找元素的类型 int LoadFile(RecType rec[]) { int i,n=1; FILE* fp=fopen("db.txt","r+"); if(fp==NULL)return 0; while(!feof(fp)) { fscanf(fp,"%d,",&rec[n].ID); fscanf(fp,"%f,",&rec[n].key); for(i=0;i fprintf(fp,"%d,%f,",rec[i].ID,rec[i].key); for(j=0;j rec[i].ID=i; sum=0; for(j=0;j int i,j; for(i = 2;i rec[j+1] = rec[j];//若不是合适位置，有序组元素向后移动 j--; } rec[j+1] = rec[0];//找到合适位置，将元素插入。 } } void ShellSort(RecType rec[],int n) { int i,j,gap; //步长 for (gap = n / 2; gap >= 1; gap /= 2) { // 步长初始化为数组长度的一半，每次遍历后步长减半 for (i = 1 + gap; i rec[j + gap] = rec[j]; //将在a[i]前且比temp的值大的元素向后移动一位 j -= gap; } rec[j + gap] = rec[0]; } } } void QuickSort(RecType rec[] ,int l, int r) { int i = l, j = r; RecType t; RecType x = rec[l]; while (j > i) { while (rec[j].key >= x.key && i i++; } if (j > i) { t=rec[i]; rec[i] = rec[j]; rec[j] = t; } } rec[l] = rec[i]; rec[i] = x; if(i>l) QuickSort(rec, l, i - 1); if(j if(j HeapAdjust(rec,i,n); } for(i=n;i>0;i--) { temp=rec[1]; rec[1]=rec[i]; rec[i]=temp;//将堆顶记录与未排序的最后一个记录交换 HeapAdjust(rec,1,i-1);//重新调整为顶堆 } } int main() { RecType* rec; rec=(RecType*)malloc(sizeof(RecType)*test_num); int i,n; clock_t start,end; SpanFile();//生成测试数据 n=LoadFile(rec);//读取数据 start = clock(); InsertionSort(rec,n);//插入排序 end =clock(); printf("插入排序后(耗时=%f秒):\n", (double)(end - start) / CLOCKS_PER_SEC); WriteFile(rec,test_num,"InsertionSort.txt");//写入文件查看结果 n=LoadFile(rec);//读取数据 start = clock(); ShellSort(rec,n);//插入排序 end =clock(); printf("希尔排序后(耗时=%f秒):\n", (double)(end - start) / CLOCKS_PER_SEC); WriteFile(rec,test_num,"ShellSort.txt");//写入文件查看结果 n=LoadFile(rec);//读取数据 start = clock(); QuickSort(rec,1,n-1);//插入排序 end =clock(); printf("快速排序后(耗时=%f秒):\n", (double)(end - start) / CLOCKS_PER_SEC); WriteFile(rec,test_num,"QuickSort.txt");//写入文件查看结果 n=LoadFile(rec);//读取数据 start = clock(); HeapSort(rec,n-1);//插入排序 end =clock(); printf("堆排序后(耗时=%f秒):\n", (double)(end - start) / CLOCKS_PER_SEC); WriteFile(rec,test_num,"HeapSort.txt");//写入文件查看结果 /* for(i=1;i

【本文地址】

公司简介

联系我们