网站建设有哪些需要注意的关键细节,网站上哪个做相片书好,万网网站设计,网站开发开题报告格式文章目录 1. 引言2. 快速排序算法2.1 传统快速排序2.2 三者取中法 3. 实验内容3.1 实验题目#xff08;一#xff09;输入要求#xff08;二#xff09;输出要求 3.2 算法实现 4. 实验结果 1. 引言 快速排序是一种经典的排序算法#xff0c;其核心思想是通过选择一个基准元… 文章目录 1. 引言2. 快速排序算法2.1 传统快速排序2.2 三者取中法 3. 实验内容3.1 实验题目一输入要求二输出要求 3.2 算法实现 4. 实验结果 1. 引言 快速排序是一种经典的排序算法其核心思想是通过选择一个基准元素将数组分为两个部分左边的元素小于基准右边的元素大于基准然后对左右两部分递归地进行排序。然而在处理基本有序数组时传统的快速排序可能会退化为 O ( n 2 ) O(n^2) O(n2)的时间复杂度。为了解决这个问题引入了三者取中法通过选择数组中的三个元素并取其中值作为基准元素能够在基本有序的情况下提高排序效率。
2. 快速排序算法
2.1 传统快速排序 快速排序的核心思想是通过选择一个基准元素将待排序的数组划分为两个部分左边的元素小于基准右边的元素大于基准然后对左右两部分递归地进行排序其时间复杂度
最好情况 每次分划都能将数组平均地划分成两部分此时的时间复杂度为 O ( n l o g 2 n ) O(n log_2 n) O(nlog2n)。最坏情况 每次分划都选择了数组中最小或最大的元素作为基准导致每次分划只能减少一个元素时间复杂度 O ( n 2 ) O(n^2) O(n2)。平均情况 通过概率分析可以证明时间复杂度为 O ( n l o g 2 n ) O(n log_2 n) O(nlog2n)。
2.2 三者取中法
2. 算法描述 改进的快速排序算法主要区别在于基准元素的选择。在传统快速排序中通常选择随机元素作为基准而在改进算法中则采用三者取中法
3. 实验内容
3.1 实验题目 实现教材233 页下方提及的 Select 算法求第 4 小元素要求文件长度大于等于 5 时调用 Partition2 算法否则调用直接插入排序算法。
一输入要求
第一组输入数据 {12345678910111213141516} 第二组输入数据 {16151413121110987654321}
二输出要求
对每组输入数据输出以下信息要求必须要有关于输出数据的明确的提示信息
输出分划次数输出找到第 4 小元素时文件的状态即输出此时所有记录的值。
3.2 算法实现
#includestdio.h
void Change(int R[],int i,int j)
{int tR[i];R[i]R[j];R[j]t;
}
int Partition2(int R[],int m,int n)
{Change(R,(mn)/2,m1);if(R[m1]R[n]) Change(R,m1,n);if(R[m]R[n]) Change(R,m,n);if(R[m1]R[m]) Change(R,m 1,m);int im,jn1,KR[m];while(ij){i;while(R[i]K) i;j--;while(R[j]K) j--;if(ij)Change(R,i,j);}Change(R,m,j);return j;
}
void InsertSort(int R[],int len)
{int i,j,t;for(i1;ilen;i)if(R[i]R[i-1]){tR[i];R[i]R[i-1];for(ji-1;R[j]tj0;j--){R[j1]R[j];}R[j1]t;}
}
int Select(int R[], int n)
{if(n5){int tPartition2(R,1,n),rounds0;rounds;while(t!4){if(t4) tPartition2(R,t1,n);else tPartition2(R,1,t-1);rounds;}printf(分划次数为%d次\n,rounds);printf(找到第4小元素时文件状态为:);int i;for(i0;in;i)printf(%d ,R[i]);printf(\n);return R[4];}else{InsertSort(R,n);return R[4];}
}
int main()
{//int R[16]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};int R[16]{16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};printf(第4小元素为%d,Select(R,16));return 0;
}
Change 函数用于交换数组中的两个元素。Partition2 函数使用中值法选择主元并使用修改过的Lomuto分区方案对数组进行分区。它返回选择的主元的最终位置。InsertSort 函数对数组执行插入排序。Select 函数是主要的算法。如果数组的大小大于或等于5它使用Partition2 函数递归地找到第4小元素。如果大小小于5它使用 InsertSort 函数对数组进行排序并返回第4个元素。
4. 实验结果
