ps做网站动图,建站教程,辽宁公司网站建设,大气网站背景#x1f4f7; 江池俊#xff1a; 个人主页 #x1f525;个人专栏#xff1a; ✅数据结构冒险记 ✅C语言进阶之路 #x1f305; 有航道的人#xff0c;再渺小也不会迷途。 文章目录 一、归并排序1.1 基本思想 动图演示2.2 递归版本代码实现 算法步骤2.3 非递归版本代… 江池俊 个人主页 个人专栏 ✅数据结构冒险记 ✅C语言进阶之路 有航道的人再渺小也不会迷途。 文章目录 一、归并排序1.1 基本思想 动图演示2.2 递归版本代码实现 算法步骤2.3 非递归版本代码实现 算法步骤2.4 归并排序的特性总结 二、计数排序2.1 基本思想2.2 动图演示2.3 算法步骤2.4 代码实现2.5 计数排序特性总结 三、排序算法复杂度及稳定性分析 一、归并排序
归并排序Merge sort是建立在归并操作上的一种有效的排序算法。该算法是采用分治法Divide and Conquer的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用归并排序的实现由两种方法
自上而下的递归所有递归的方法都可以用迭代重写所以就有了第 2 种方法自下而上的迭代
1.1 基本思想 动图演示
归并排序Merge sort是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。它将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 2.2 递归版本代码实现 算法步骤
归并排序的基本思想是分治思想它包括以下三个步骤
分解Divide将含有n个元素的序列分成两个各自包含大约n/2个元素的子序列。当数组分解成一个时即可认为其有序解决Conquer递归地对这两个子序列进行归并排序。合并Combine将两个排序好的子序列合并成一个最终的排序序列。
归并排序通过不断地将大问题分解成小问题来解决即把大的数组拆分成若干个小的数组然后逐一合并这些有序的小数组来得到最终排序好的整体数组。这种算法非常适用于链表等数据结构在处理大规模数据时尤其高效。
// 归并排序递归函数
void _MergeSort(int* a, int begin, int end, int* temp)
{if (begin end)return;int mid (begin end) / 2;// [begin, mid] [mid1, end]_MergeSort(a, begin, mid, temp);_MergeSort(a, mid1, end, temp);// ... 归并 [begin,mid] [mid1,end]int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){temp[i] a[begin1];}else{temp[i] a[begin2];}}while (begin1 end1){temp[i] a[begin1];}while (begin2 end2){temp[i] a[begin2];}// 拷贝回原数组memcpy(a begin, temp begin, sizeof(int) * (end - begin 1));
}// 归并排序
void MergeSort(int* a, int n)
{// 申请一个与原数组同样大小的空间int* temp (int*)malloc(sizeof(int) * n);if (temp NULL){perror(malloc fail);return;}_MergeSort(a, 0, n - 1, temp);free(temp);
}【递归展开图】
现在我们来分析一下以上代码 这段代码是归并排序Merge Sort的实现。归并排序是一种分治算法它将一个数组分成两半对每一半进行排序然后将两个有序的部分合并成一个有序的数组。以下是这段代码的算法思想和步骤分析 递归划分 在_MergeSort函数中首先检查基准条件即如果begin大于或等于end则数组已经完全有序所以直接返回。然后计算中间索引mid将数组分成两个子数组[begin, mid]和[mid1, end]。对这两个子数组递归地进行归并排序。 合并 在递归调用返回后两个子数组都是有序的。然后将这两个有序的子数组合并成一个有序的数组。合并操作通过双指针技术完成。指针begin1和begin2分别指向两个子数组的开始位置而指针end1和end2分别指向两个子数组的结束位置。开始时从两个子数组中取最小的元素放到临时数组temp中直到其中一个子数组被完全取完。然后将剩余的子数组的所有元素复制到临时数组中。 拷贝回原数组 最后使用memcpy函数将临时数组中的元素复制回原数组。这一步是必要的因为临时数组是在堆上分配的而原数组是在栈上。 主函数 MergeSort函数是归并排序的入口点。它首先在堆上为原数组分配一个同样大小的临时数组。如果分配失败即malloc返回NULL则输出错误信息并返回。然后调用递归函数_MergeSort对原数组进行排序。最后释放临时数组以防止内存泄漏。 稳定性 归并排序是稳定的排序算法这意味着相等的元素在排序后保持其原始顺序。这是因为归并排序在合并两个子数组时总是选择较小的元素而不改变其相对顺序。 时间复杂度 归并排序的时间复杂度为O(nlogn)其中n是数组的大小。这是因为每次递归调用都会将问题规模减半logn并且需要进行n次这样的递归调用n。 空间复杂度 归并排序的空间复杂度为O(n)因为需要一个与原数组同样大小的临时数组来存储合并过程中的中间结果。
2.3 非递归版本代码实现 算法步骤
// 归并排序非递归
void MergeSortNonR(int* a, int n)
{int* temp (int*)malloc(sizeof(int) * n);if (temp NULL){perror(malloc fail);return;}int gap 1; // 通过gap来控制归并的两个区间的大小表示的是这两个区间的大小while (gap n){for (int i 0; i n; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;// [begin1, end1] [begin2, end2] 归并// 边界处理if (end1 n || begin2 n){break;}if (end2 n){end2 n - 1;}// 归并int j begin1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){temp[j] a[begin1];}else{temp[j] a[begin2];}}while (begin1 end1){temp[j] a[begin1];}while (begin2 end2){temp[j] a[begin2];}// 拷贝回原数组边归并边拷贝 --- 因为最后可能有一个区间不需要归并所以这一个区间的元素是不需要改变的即不需要拷贝回去若一次性拷贝回原数组会使这个区间的元素全部变为随机值memcpy(a i, temp i, sizeof(int) * (end2 - i 1));}gap * 2;}free(temp);
}对于上述代码我们接着来分析一下它的算法步骤
【算法步骤】 初始化 定义一个临时数组temp其大小为输入数组a的大小。初始化一个变量gap为1它表示每次归并时每组数据的个数。 归并循环 当gap小于输入数组的长度n时进入循环。在每次循环中将数组分为两个子数组每个子数组的大小为gap并对这两个子数组进行归并。 子数组归并 定义两个子数组的起始和结束索引begin1到end1和begin2到end2。处理边界情况如果其中一个子数组超出数组范围则退出循环。使用一个临时数组temp来存储归并的结果。使用一个双指针方法类似于两个指针比较和交换来将两个子数组合并为一个有序数组。 拷贝回原数组 使用memcpy函数将临时数组中的数据拷贝回原数组。这一步是为了在归并过程中更新原数组。 扩大gap 在每次循环结束时将gap乘以2以便在下一次循环中处理更大的子数组。 释放内存 归并完成后释放临时数组temp的内存。
2.4 归并排序的特性总结
归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定 二、计数排序
2.1 基本思想
思想计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。 操作步骤
统计相同元素出现次数根据统计的结果将序列回收到原来的序列中 2.2 动图演示 2.3 算法步骤
这段代码是实现计数排序算法的C语言代码。以下是该代码的算法步骤和思想分析
算法步骤
找出数组中的最小值和最大值这是计数排序的一个重要步骤因为算法需要对数组中的每个元素进行计数所以需要知道元素的可能范围。计算范围根据最小值和最大值计算出元素的可能范围。计数遍历输入数组对每个元素在其可能的范围内进行计数。构建输出数组根据计数结果将每个元素放到它在输出数组中的正确位置。
2.4 代码实现
// 计数排序
// 时间复杂度O(Nrange) 空间复杂度O(range)
void CountSort(int* a, int n)
{int min a[0], max a[0];for (int i 1; i n; i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}int range max - min 1;int* count (int*)calloc(range, sizeof(int));if (count NULL){perror(calloc fail);return;}// 统计次数for (int i 0; i n; i){count[a[i] - min];}// 排序int i 0;for (int j 0; j range; j){while (count[j]--){a[i] j min;}}
}2.5 计数排序特性总结
计数排序在数据范围集中时效率很高但是适用范围及场景有限。数排序适用于整数且范围较小的情况。对于范围较大的整数或小数需要更复杂的排序算法。时间复杂度O(MAX(N,范围))由于算法只涉及到一次遍历输入数组和一次遍历计数数组所以时间复杂度为O(MAX(N,范围))。空间复杂度O(范围)由于需要创建一个与范围大小相等的计数数组所以空间复杂度为O(范围)。稳定性稳定相等的元素在排序后保持其原始顺序 三、排序算法复杂度及稳定性分析
