建设部网站 挂证水网站建设

当前位置： 首页 > news >正文

建设部网站 挂证,水网站建设,深圳一元购网站设计公司,甘肃省住房与建设厅网站文章目录 前言一.比较排序算法1.Bubble Sort冒泡排序1.1.冒泡排序原理1.2.冒泡排序过程1.3.代码实现1.4.复杂度和稳定性 2.Quick Sort快速排序2.1递归快速排序2.1.1.递归快速排序原理2.1.2.递归快速排序过程2.1.3.代码实现 2.2.非递归快速排序2.2.1.非递归快速排序原理2.2.2.非… 文章目录 前言一.比较排序算法1.Bubble Sort冒泡排序1.1.冒泡排序原理1.2.冒泡排序过程1.3.代码实现1.4.复杂度和稳定性 2.Quick Sort快速排序2.1递归快速排序2.1.1.递归快速排序原理2.1.2.递归快速排序过程2.1.3.代码实现 2.2.非递归快速排序2.2.1.非递归快速排序原理2.2.2.非递归快速排序过程2.2.3.代码实现 2.3.复杂度和稳定性 二.归并排序算法Merge Sort归并排序1.递归归并排序1.1.递归归并排序原理1.2.递归归并排序过程1.3.代码实现 2.非递归归并排序2.1.非递归归并排序原理2.2.非递归归并排序过程2.3.代码实现 3.复杂度和稳定性 三.非比较排序算法 Cout Sort计数排序计数排序原理计数排序过程代码实现复杂度和稳定性 四.代码文件1.头文件Sort.h2.测试文件test.c3.测试结果 前言 在上一篇文章中主要讲了插入排序希尔排序选择排序堆排序详细可以看我上一篇文章哦在接下来的这篇文章中将重点讲解冒泡排序快速排序归并排序以及计数排序。 一.比较排序算法 1.Bubble Sort冒泡排序 1.1.冒泡排序原理 冒泡排序Bubble Sort是一种简单的排序算法。它重复地遍历要排序的数列一次比较相邻的两个元素如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小或越大的元素会经由交换慢慢“浮”到数列的顶端。 1.2.冒泡排序过程 比较相邻的元素如果第一个比第二个大升序就交换他们两个。 遍历数列对每一对相邻元素做同样的工作从开始的第一对到结尾的最后一对这步结束后最大或最小的元素会在数列的结尾。 针对所有的元素重复以上步骤除了最后一个。 重复上面的步骤直到没有任何一对元素需要比较。 1.3.代码实现 //交换 void Swap(int*a,int*b){int t*a;*a*b;*bt; } void BubbleSort(int*a,int n){for(int j0;jn;j){//设置一个变量用来判断每一趟是否交换bool exchangefalse;//内层循环是每一趟的比较交换for(int i1;in-j;i){if(a[i-1]a[i]){Swap(a[i-1],a[i]);exchangetrue;}}//如果某一趟没有进行交换就是序列已经有序直接结束排序if(exchangefalse){break;}} }1.4.复杂度和稳定性 时间复杂度冒泡排序的平均和最坏时间复杂度都是O(n^2)。空间复杂度冒泡排序的空间复杂度为O(1)。稳定性冒泡排序是稳定的排序算法即相等的元素在排序后的序列中保持原来的顺序。但由于其效率较低通常不被用作主要的排序算法。 2.Quick Sort快速排序 2.1递归快速排序 2.1.1.递归快速排序原理 快速排序Quick Sort是一种高效的排序算法由C. A. R. Hoare在1960年提出。它采用分治Divide and Conquer的策略来把一个序列分为较小和较大的两个子序列然后递归地排序两个子序列。 快速排序的基本思想是通过一趟排序将待排记录分隔成独立的两部分其中一部分的所有记录均比另一部分的所有记录小则可分别对这两部分记录继续进行排序以达到整个序列有序。 2.1.2.递归快速排序过程 选择基准值从代排序的数列中选出一个元素作为基准值key最常用的就是三数取中法通过比较数列的第一个和最后一个以及中间的值选出这三个数的中间值然后和最左端的也就是第一个数交换。基准值的选择对于排序的效率有重要影响。 分区重新排列数列所有比基准值小的元素排在基准值前面比基准值大的元素排在基准值后面相同的数可以放在任意一边。分区的操作有多种实现方法如hoare法挖坑法前后指针法。 1.hoare法 2.挖坑法 3.前后指针法 递归排序子序列递归地将小于基准值的子序列和大于基准值的子序列排序。递归的最底部情形是数列的大小是零活着一也就是已经排好序。
2.1.3.代码实现 //获取基准值 int Getmid(inta,int left, int right) {int mid (left right) / 2;if (a[left] a[mid]) {if (a[mid] a[right]) {return mid;}else if (a[right] a[left]) {return left;}else{return right;}}else {if (a[right] a[mid]) {return mid;}else if (a[left] a[right]) {return left;}else {return right;}} } //hoare法 int keysort1(int a, int left, int right) {int key Getmid(a, left, right);Swap(a[left], a[key]);key left;while (left right) {while (left right a[right] a[key]) {right–;}while (left right a[left] a[key]) {left;}Swap(a[left], a[right]);}Swap(a[left], a[key]);key left;return key; } //挖坑法 int keysort2(int* a, int left, int right) {int key Getmid(a, left, right);Swap(a[left], a[key]);int keyi a[left];int hole left;while (left right) {while (leftright a[right]keyi) {right–;}a[hole] a[right];hole right;while (left right a[left] keyi) {left;}a[hole] a[left];hole left;}a[hole] keyi;hole left;return hole; } //前后指针法 int keysort3(int* a, int left, int right) {int mid Getmid(a, left, right);Swap(a[left], a[mid]);int key left;//后指针int prev left;//快指针int cur left 1;while (cur right) {if (a[cur] a[key] prev ! cur) {Swap(a[cur], a[prev]);}cur;}Swap(a[key], a[prev]);key prev;return key; }void QuickSort(int* a, int left,int right) {if (left right) {return;}int begin left;int end right;//分区三种方法选一种即可int key keysort3(a, left, right);QuickSort(a, begin, key - 1);QuickSort(a, key 1, end); }2.2.非递归快速排序 2.2.1.非递归快速排序原理 非递归快速排序的原理和过程与递归快速排序相似但主要区别在于非递归版本通过显式地使用一个辅助栈或队列来模拟递归过程中的函数调用栈从而避免了递归调用。 2.2.2.非递归快速排序过程 初始化栈 创建一个空栈用于保存待排序子数组的起始和结束索引。 将初始数组的起始和结束索引入栈 这对应于最初的排序问题。 循环处理栈中的元素 当栈不为空时进行以下操作 弹出栈顶的一对索引起始和结束索引这指定了当前要处理的子数组。 在当前子数组上选择一个基准元素并进行分区操作。 (分区操作会将数组分为左右两部分并返回基准元素的最终位置。) 如果基准元素左侧的子数组有超过一个元素则将其起始和结束索引作为一对入栈。 如果基准元素右侧的子数组有超过一个元素也将其起始和结束索引作为一对入栈。 重复步骤3直到栈为空此时所有子数组都已经被正确排序。
2.2.3.代码实现 void QuickSortNoNR(int* a, int left, int right) {//创建栈Stack st;//初始化栈InitStack(st);int begin left;int end right;//将第一个区间入栈pushStack(st, end);pushStack(st, begin);//循环条件栈不为空while (!IsEmpty(st)) {//将区间出栈begin getpopStack(st);popStack(st);end getpopStack(st);popStack(st);//获取key值下标分区int key keysort3(a, begin, end);//右子区间满足条件入栈if (key 1 end) {pushStack(st, end);pushStack(st, key 1);}//左子区间满足条件入栈if (begin key - 1) {pushStack(st, key - 1);pushStack(st, begin);}}//销毁栈DestroyStack(st); }2.3.复杂度和稳定性 时间复杂度快速排序的时间复杂度平均为O(n log n)但在最坏情况下如数组已经有序时会退化到O(n^2)。空间复杂度稳定性快速排序是不稳定的排序算法即相同的元素可能在排序过程中改变相对位置。 二.归并排序算法 Merge Sort归并排序 1.递归归并排序 1.1.递归归并排序原理 递归归并排序是建立在归并操作上的一种有效排序算法它采用分治法Divide and Conquer来进行排序。分治法的基本思想是将一个复杂的问题分解成两个或更多的相同或相似的子问题子问题再继续分解直到这些子问题变得简单到可以直接解决然后再合并子问题的解为原问题的解。 在归并排序中分治法的应用体现在 分解将待排序的数组分解成两个较小的子数组然后子数组再继续分解直到子数组的大小为1即只有一个元素此时认为它是有序的。解决递归地对子数组进行排序并合并得到有序的子数组。合并将两个有序的子数组合并成一个有序的大数组直到合并为1个完整的数组。 1.2.递归归并排序过程 分解 将待排序的数组a[begin…end]分解成两个子数组a[begin…mid]和a[mid1…end]其中mid是begin和end的中间位置mid (begin end) / 2。递归地对这两个子数组进行分解直到子数组的大小为1。 递归排序并合并 对分解得到的子数组进行递归排序。合并两个有序的子数组为一个有序数组。合并过程中通过比较两个子数组的元素将较小的元素依次放入一个新的临时数组tmp中直到所有元素都被合并。 合并 合并过程中使用两个指针begin1,begin2分别指向两个子数组的起始位置比较两个指针所指的元素将较小的元素放入临时数组中并移动该指针。当其中一个子数组的所有元素都被合并后将另一个子数组中剩余的元素依次复制到临时数组的末尾。最后将临时数组中的元素复制回原数组中的相应位置完成合并。 递归终止条件 当子数组的大小为1时递归终止因为单个元素的数组自然是有序的。 排序完成 当整个数组被分解为单个元素的子数组并通过递归合并成有序的大数组时排序完成。 1.3.代码实现 void _MergeSort(int*a,int begin,int end,inttmp){//不满足条件时结束返回if(beginend){return;}//找中间值下标int mid(beginend)/2;//递归分区[begin,mid],[mid1,end]_MergeSort(a,begin,mid,tmp);_MergeSort(a,mid1,end,tmp);//设置分区的下标int begin1begin,end1mid;int begin2mid1,end2end;//循环比较依次存放到tmp数组中//注意这里tmp数组的下标一定要从begin开始而不是从0开始int ibegin;while(begin1end1begin2end2){if(a[begin1]a[begin2]){tmp[i]a[begin1];}else{tmp[i]a[begin2];}}while(begin1end1){tmp[i]a[begin1];}while(begin2end2){tmp[i]a[begin2];}//将tmp数组中排序好的拷贝到原数组中,复制范围是每次函数调用的左右区间memcpy(abegin,tmpbegin,sizeof(int)(end-begin1)); }void MergeSort(int*a,int n){//创建一个临时数组用来存放排好序的序列inttmp(int)malloc(sizeof(int)*n);if(tmpNULL){perror(malloc false);return;}_MergeSort(a,0,n-1,tmp); }2.非递归归并排序 2.1.非递归归并排序原理 非递归归并排序也称为迭代归并排序与递归归并排序在原理上相同都是基于分治法的排序算法。不过在实现方式上非递归归并排序通过循环而不是递归调用来控制排序过程。非递归归并排序也是将数组分解成若干个子数组直到子数组的大小为1即只有一个元素此时认为它是有序的。然后通过迭代的方式逐步合并相邻的有序子数组直到合并成一个完整的有序数组。 2.2.非递归归并排序过程 初始化 定义一个变量gap用于表示当前归并的子数组的大小即每次合并时考虑的元素个数。初始时gap通常设置为1表示每个子数组只包含一个元素。 迭代合并 使用一个外层循环不断增大gap的值直到gap大于等于数组的长度。这个循环控制归并的轮数。在每一轮归并中使用一个内层循环来遍历数组并合并相邻的、大小为gap的有序子数组。合并过程中需要使用一个临时数组tmp来存放合并后的结果。 合并相邻子数组 在内层循环中对于每一对相邻的子数组它们的起始位置相差gap使用类似于递归归并排序中合并函数的方法将它们合并成一个有序的子数组。合并过程中使用两个指针begin1,begin2分别指向两个子数组的起始位置比较两个指针所指的元素将较小的元素放入临时数组中并移动该指针。当其中一个子数组的所有元素都被合并后将另一个子数组中剩余的元素依次复制到临时数组的末尾。最后将临时数组中的元素复制回原数组中的相应位置完成合并。 更新gap 在外层循环的每次迭代结束时将gap的值加倍即gap * 2以便在下一轮归并中合并更大范围的子数组。 排序完成 当gap大于等于数组的长度时排序完成。此时整个数组被合并成一个有序的大数组。 2.3.代码实现 void MergeSortNoNR(inta,int n){//创建一个临时数组用来存放排好序的序列int tmp(int*)malloc(sizeof(int)*n);if(tmpNULL){perror(malloc false);return;}//初始化设置分区间隔值gap从1开始int gap1;//迭代合并while(gapn){//合并相邻子数组for(int i0;in;igap*2){//分区int begin1i,end1igap-1;int begin2igap,end2igap2-1;int ji;//处理临界情况if(begin2n){break;}if(end2n){end2n-1;}//循环比较依次存放到tmp数组中while(begin1end1begin2end2){if(a[begin1]a[begin2]){tmp[j]a[begin1];}else{tmp[j]a[begin2];}}while(begin1end1){tmp[j]a[begin1];}while(begin2end2){tmp[j]a[begin2];}//将tmp数组中排序好的拷贝到原数组中//注意这里用i不用begin1,是因为begin1值已经改变memcpy(ai,tmpi,sizeof(int)(end2-i1));}//更新gap:gap*2;} }3.复杂度和稳定性 时间复杂度归并排序的时间复杂的为O(n*log n)。空间复杂度归并排序的空间复杂度为O(n),因为借助了一个临时数组tmp数组长度为n。稳定性归并排序是一种稳定的排序算法。 三.非比较排序算法 Cout Sort计数排序 计数排序原理 计数排序Counting Sort是通过统计待排序元素的出现次数来确定元素的相对位置从而实现排序。这种算法不是基于比较的排序算法而是通过统计每个元素的出现次数并利用这些信息来重新排列元素。 计数排序过程 找出待排序数组的最大值和最小值 遍历待排序数组找出数组中的最大值max和最小值min。 创建计数数组并初始化 根据最大值和最小值创建一个计数数组countA其长度range为max - min 1如果数组中存在负数则需要对所有元素进行偏移使得所有元素都是非负的。将计数数组的所有元素初始化为0。 统计每个元素的出现次数 再次遍历待排序数组对于数组中的每个元素x将countA[x - min]如果元素是负数或需要特殊偏移则相应调整的值增加1。这样计数数组就记录了每个元素的出现次数。 对计数数组进行累加也称为前缀和 遍历计数数组将每个元素的值更新为从计数数组开始到当前元素位置包括当前元素的所有元素之和。这一步完成后计数数组中的每个元素都表示小于等于该索引对应元素值的元素个数。 根据计数数组将元素放回原数组的正确位置 创建一个临时数组temp其长度与待排序数组相同。从后往前遍历待排序数组这是为了确保排序的稳定性对于每个元素x通过count[x - min] - 1如果元素是负数或需要特殊偏移则相应调整找到其在临时数组中的正确位置并将x放入该位置。然后将count[x - min]的值减1以便下一个相同值的元素能够找到其正确的位置。 将排序后的元素复制回原数组如果需要 如果原数组需要被直接修改以反映排序后的结果则将临时数组temp中的元素复制回原数组。否则可以直接使用临时数组作为排序后的数组。 代码实现 void CountSort(int*a,int n){//找出待排序数组的最大值和最小值int maxa[0],mina[0];for(int i0;in;i){if(a[i]max){maxa[i];}if(a[i]min){mina[i];}}//创建计数数组并初始化int rangemax-min1;intcountA(int)malloc(sizeof(int)*range);if(countANULL){perror(malloc false);return;}//将计数数组的所有元素初始化为0memset(countA,0,sizeof(int)range);//统计每个元素的出现次数for(int i0;in;i){countA[a[i]-min];}//将原数组的元素按照计数数组的个数复制到原数组中int j0;for(int i0;in;i){while(countA[i]–){a[j]imin;}} }复杂度和稳定性 时间复杂度计数排序的的时间复杂度为O(nk)n是待排序数组的长度k是元素范围最大值-最小值加一。空间复杂度空间复杂度为O(nk)需要创建计数数组。稳定性计数排序是一种稳定的排序算法适用于整数或有限范围内的非负整数排序。 四.代码文件 这里附上整个代码文件 头文件Sort.h测试文件test.c接口函数实现文件Sort.c(文件内容就是每个代码实现) 1.头文件Sort.h #pragma once #includestdio.h #includestdlib.h #includestdbool.h #includestring.h //递归快速排序 void QuickSort(int a, int left, int right); //三数取中 int Getmid(int* a, int left, int right); //霍尔版本快速排序 int keysort1(int* a, int left, int right); //挖坑法快速排序 int keysort2(int* a, int left, int right); //前后指针法快速排序 int keysort3(int* a, int left, int right); //非递归快速排序 void QuickSortNoNR(int* a, int left, int right); //递归归并排序 void MergeSort(int* a, int n); void _MergeSort(int* a, int left, int right, int* tmp); //非递归归并排序1 void MergeSortNoNR1(int* a, int n); //非递归归并排序2 void MergeSortNoNR2(int* a, int n); //计数排序 void CountSort(int* a, int n);2.测试文件test.c //冒泡排序测试 void Bubbletest() {int a[10] { 3,6,7,2,1,5,4,9,8,10 };int n (sizeof(a) / sizeof(int));BubbleSort(a, n);printf(冒泡排序\n);PrintArray(a, n); } //快速排序测试 void Quicktest() {int a[20] { 3,6,7,2,1,5,4,9,8,10,-2,7,-4,23,-1,-5,65,4,16,-3 };int n (sizeof(a) / sizeof(int));QuickSortNoNR(a, 0, sizeof(a) / sizeof(int) - 1);printf(快速排序\n);PrintArray(a, n); } //归并排序测试 void Mergetest() {int a[9] { 2,1,7,5,4,9,3,8,6 };int n (sizeof(a) / sizeof(int));MergeSortNoNR2(a, n);printf(归并排序\n);PrintArray(a, n); } //计数排序测试 void Counttest() {int a[9] { 2,1,7,2,4,1,3,8,6 };int n (sizeof(a) / sizeof(int));CountSort(a, n);printf(计数排序\n);PrintArray(a, n); } int main(){Bubbletest();Quicktest();Mergetest();Counttest();return 0; } }3.测试结果 以上就是关于排序部分冒泡排序快速排序归并排序和计数排序的讲解如果哪里有错的话可以在评论区指正也欢迎大家一起讨论学习如果对你的学习有帮助的话点点赞关注支持一下吧