大连网站设计 仟亿科技,蒲城网站建设wzjseo,北京公司网站建设公司,朝阳网站优化目录
一#xff0c;归并排序的递归
二#xff0c;归并排序的非递归
三#xff0c;计数排序
四#xff0c;排序算法的综合分析 一#xff0c;归并排序的递归
基本思想#xff1a; 归并采用的是分治思想#xff0c;是分治法的一个经典的运用。该算法先将原数据进行拆…目录
一归并排序的递归
二归并排序的非递归
三计数排序
四排序算法的综合分析 一归并排序的递归
基本思想 归并采用的是分治思想是分治法的一个经典的运用。该算法先将原数据进行拆分此步骤与二叉树的拆分思想一样因此运用递归比较简单然后将最终拆分后的每一小部分排序最后将已有序的子序列进行合并得到完全有序的序列其中关键为要使每个分割后的子序列有序再使子序列段间有序即合并有序序列。以上中将两个有序表合并成一个有序表称为二路归并。思想图如下以升序为例 上图中先以中间数据为界将一堆数据进行不断分解当分解完全后再进行合并而在合并时其实就是边排序边合并。由于在排序中要改动原数据因此我们可再创建一个数组进行改动然后将改动后的数据赋值给原数据块即可代码和导图如下
代码运行导图 导图中先取中间值以此下标为界限分开左右区间然后再不断递归分割最后一次分割为leftbegin leftendrightbegin rightend此时就要进行排序组合组合完子序列后即可往原序列就行赋值此为一趟遍历然后递归就不断进行返回即不断就行合并排序最终全部元素有序。
归并代码 void MergeFunction(int* a, int* nums, int n, int begin, int end) { //当分割区间为1个数据时就要停止分割即此时begin end if (begin end) { return; } int middle (begin end) / 2;//中间数据控制界限 //在左区间[begin, middle]和右区间[middle 1, end]进行不断分割 MergeFunction(a, nums, n, begin, middle); MergeFunction(a, nums, n, middle 1, end); //分割后下面是进行左右区间的排序 int leftbegin begin, leftend middle; int rightbegin middle 1, rightend end; int insert begin; //以下是进行分割后的排序 while (leftbegin leftend rightbegin rightend) { if (a[leftbegin] a[rightbegin]) { nums[insert] a[leftbegin]; } else { nums[insert] a[rightbegin]; } } while (leftbegin leftend) { nums[insert] a[leftbegin]; } while (rightbegin rightend) { nums[insert] a[rightbegin]; } //拷贝数组 memcpy(a begin, nums begin, sizeof(int) * (end - begin 1)); } void MergeSort(int* a, int n) { int* nums (int*)malloc(sizeof(int) * n);//此数组用于临时放入数据 if (!nums) { perror(nums malloc); exit(-1); } MergeFunction(a, nums, n, 0, n - 1); free(nums); } 样例代码将以下中数组a进行排序(升序)
#include stdio.h
#include stdlib.h
#include string.h
void MergeFunction(int* a, int* nums, int n, int begin, int end) {//当分割为1个时就要停止分割即此时begin endif (begin end) {return;}int middle (begin end) / 2;//中间数据控制界限//在左区间[begin, middle]和右区间[middle 1, end]进行不断分割MergeFunction(a, nums, n, begin, middle);MergeFunction(a, nums, n, middle 1, end);//分割后下面是进行左右区间的排序int leftbegin begin, leftend middle;int rightbegin middle 1, rightend end;int insert begin;//以下是进行分割后的排序while (leftbegin leftend rightbegin rightend) {if (a[leftbegin] a[rightbegin]) {nums[insert] a[leftbegin];}else {nums[insert] a[rightbegin];}}while (leftbegin leftend) {nums[insert] a[leftbegin];}while (rightbegin rightend) {nums[insert] a[rightbegin];}//拷贝数组memcpy(a begin, nums begin, sizeof(int) * (end - begin 1));
}
void MergeSort(int* a, int n) {int* nums (int*)malloc(sizeof(int) * n);//此数组用于临时放入数据if (!nums) {perror(nums malloc);exit(-1);}MergeFunction(a, nums, n, 0, n - 1);free(nums);
}
int main() {int a[] { 10,6,7,1,3,9,4,2 };MergeSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i) {fprintf(stdout, %d , a[i]);}puts();return 0;
}
运行图 二归并排序的非递归 我们平常将递归改成非递归首先可能想起要运用栈结构但是我们先理一下归并的思路当我们不断分割时确实可以用栈结构来控制区间但是当回并时可能就比较麻烦因此本人不建议用栈结构不是不可以是有更好的方法。 归并递归时是将数据不断进行二分即分治思想当用非递归时我们可设置一个间隔gap以次模仿递归时的二分思想每次循环结束后将此间隔乘二即可。非递归思路导图如下 由以上图不难发现此种非递归合并的思路与递归合并的思路有些不太一样此种非递归的思想是一旦有了一个间隔值后就一次性的将全部数据按照此间隔值进行间隔归并。 非递归归并的时候要注意一个点当数据个数为奇数时不难发现左区间[leftbegin,leftend]无影响但右区间[rightbegin,rightend]将会溢出此时情况如果rightbegin溢出的话那么可之间退出因为据上图中所示每一趟归并时就相当于将下一趟的左区间就排列有序了如果rightend溢出的话直接令rightend为最后一个元素的下标进行归并排序即可。当数据个数为偶数时不会出现溢出情况。
代码如下 void MergeSortNonR(int* a, int n) { int* nums (int*)malloc(sizeof(int) * n); //gap是每次隔离的间隔也可理解为将要排序的元素个数 int gap 1; //控制gap间据的大小 while (gap n) { for (int i 0; i n; i 2 * gap) { //以gap为间距分割左区间[leftbegin,leftend]共有gap个元素 int leftbegin i, leftend i gap - 1; //以gap为间距分割当原始数有偶数的元素时右区间[rightbegin,rightend]有gap个元素 int rightbegin i gap, rightend i gap gap - 1; int insert i; //以下是当元素个数为奇数时的情况 if (rightbegin n) { break; } if (rightend n) { rightend n - 1; } //开始进行排序,排列的数据区间为[leftbegin, rightend] while (leftbegin leftend rightbegin rightend) { if (a[leftbegin] a[rightbegin]) { nums[insert] a[leftbegin]; } else { nums[insert] a[rightbegin]; } } while (leftbegin leftend) { nums[insert] a[leftbegin]; } while (rightbegin rightend) { nums[insert] a[rightbegin]; } //将排列的区间[leftbegin, rightend]进行拷贝因为leftbegin和rightbegin都已改变所以不能用这两个数据 memcpy(a i, nums i, sizeof(int) * (rightend - i 1)); } gap * 2; } free(nums); } 样例代码将以下中数组a进行排序(升序)
#include stdio.h
#include stdlib.h
#include string.h
void MergeSortNonR(int* a, int n) {int* nums (int*)malloc(sizeof(int) * n);//gap是每次隔离的间隔也可理解为将要排序的元素个数int gap 1;while (gap n) {for (int i 0; i n; i 2 * gap) {//leftbegin和leftend理解为在gap区间内的元素int leftbegin i, leftend i gap - 1;//rightbegin和rightend可理解为在预排序gap区间的后面的元素int rightbegin i gap, rightend i gap gap - 1;int insert i;//以下是当元素为奇数时的情况if (rightbegin n) {break;}if (rightend n) {rightend n - 1;}//开始进行排序,排列的数据区间为[leftbegin, rightend]while (leftbegin leftend rightbegin rightend) {if (a[leftbegin] a[rightbegin]) {nums[insert] a[leftbegin];}else {nums[insert] a[rightbegin];}}while (leftbegin leftend) {nums[insert] a[leftbegin];}while (rightbegin rightend) {nums[insert] a[rightbegin];}//将排列的区间[leftbegin, rightend]进行拷贝因为leftbegin和rightbegin都以改变所以不能用这两个数据memcpy(a i, nums i, sizeof(int) * (rightend - i 1));}gap * 2;}free(nums);
}
int main() {int a[] { 10,6,7,1,3,9,4,2 };MergeSortNonR(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i) {fprintf(stdout, %d , a[i]);}puts();return 0;
}
运行图 运算发的效率 最后我们来谈论一下此算法的效率不难发现由于此算法中运用的是二分思想所以时间复杂度为O(nlogn)空间复杂度O(n)。由此可见此算法的效率也算高跟快排不同的是此算法与原始数据的初始位置并无太大影响效率比较稳定。 三计数排序 计数排序可从字面意思理解通过数组的下标来计数来间接实现数据的排序。首先我们需设置一个数组此数组是通过下标来进行计数的原数据中最大数据个数为max - min 1(max是原数据的最大元素min是原数据最小的元素)即幅度range在区间[0max - min]中因此我们可设置数组大小为max - min 1(不包括重复数组重复的数据我们可用相同下标对应的数值记录出现的次数)即最大下标为max - min记录最大元素的位置下标的设置思想为原数据 - min。然后将设置数组初始化为0(也可选举其它值但选举0是最为简单的)0表示原数据中没有此元素然后幅度range遍历一旦存在此元素加1表示出现元素的次数最后将其设置数组中出现过元素的下标加上min赋给原数据即可得到有序序列思维导图如下 代码如下(以升序为例) void CountSort(int* a, int n) { //以下是寻找最大值max和最小值min为了后面确定幅度range int min a[0], max a[n - 1], j 0; for (int i 0; i n; i) { if (a[i] max) { max a[i]; } if (a[i] min) { min a[i]; } } //最大元素个数为range下标为“原数据 - min” int range max - min 1; int* count (int*)malloc(sizeof(int) * range); memset(count, 0, sizeof(int) * range);//初始化0表元素个数为0 for (int i 0; i n; i) { //用计数数组count的有序下标来进行有序计数,记录出现过元素的次数 count[a[i] - min];//注意: 不能count[a[i] - min] 1,因为可能有重复数据 } //最后遍历一旦存在此值将下标 min即为数据 for (int i 0; i range; i) { while (count[i]--) { a[j] i min; } } free(count); } 代码演示(以升序为例)
#include stdio.h
#include stdlib.h
#include string.h
void CountSort(int* a, int n) {//以下是寻找最大值max和最小值min为了后面确定幅度rangeint min a[0], max a[n - 1], j 0;for (int i 0; i n; i) {if (a[i] max) {max a[i];}if (a[i] min) {min a[i];}}//最大元素个数为range下标为“原数据 - min”int range max - min 1;int* count (int*)malloc(sizeof(int) * range);memset(count, 0, sizeof(int) * range);//初始化0表元素个数为0for (int i 0; i n; i) {//用计数数组count的有序下标来进行有序计数,记录出现过元素的次数count[a[i] - min];//注意: 不能count[a[i] - min] 1,因为可能有重复数据}//最后遍历一旦存在此值将下标 min即为数据for (int i 0; i range; i) {while (count[i]--) {a[j] i min;}}free(count);
}
int main() {int a[] { 10,6,7,1,3,9,4,2 };CountSort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i) {fprintf(stdout, %d , a[i]);}puts();return 0;
}
运行图 计数效率与注意要点 计数排序的时间复杂度为O(range n) 空间复杂度为O(range)效率是非常高的因为无论什么排序算法最好的时间效率无非是O(n)而计数排序的时间复杂度达到O(range n)已经非常接近O(n)。无论是希尔排序堆排序快速排序还是归并排序都达不到此效率但此算法也不是最优选择因为此算法完全可以说是那空间换时间当range非常大时会消耗很大的空间而且由于此算法是运用数组下标进行间接排序的因此此算法只能对整型排序不能对其它数据类型进行排序使得此算法有了很大的局限性。 四排序算法的综合分析
1算法的效率分析 排序算法的效率不能只根据时间复杂度和空间复杂度因为两者的计算都是取最好情况和最坏情况进行概率的综合分析最终取平均比如排序的原始序列不同快排算法直接插入算法和冒泡算法的效率比较大直接插入和冒泡最好的情况都是有序的情况此时时间复杂度都为O(n)而快排最好的情况是基准值每次在中间此时时间复杂度为O(nlogn)。但大多数情况下我们根本预测不了原始序列和原始数据所以在大多数情况下可直接根据时间复杂度和空间复杂度直接判断若对数据比较敏感的话就要根据具体情况进行具体分析从而选取最优算法。
2算法的稳定性 稳定性相同的数据排序后相对位置是否发生变化若两者之间的相对位置没有发生变化则算法稳定发生变化算法不稳定。 在初学情况下稳定性确实不算太重要但是在后面深入学习系统操作和程序等先后顺序就显得尤为重要例如一个程序要对学生进行考试排名其中高成绩出现了两个99分的和两个98分这时两个99分的学生谁先排入第一名和两个98分的学生谁排入第三名就显得尤为重要这就要求排序算法的稳定性。最后总结一下各个算法的效率和稳定性 其中计数排序没必要加上因为计数局限性太强了在后面的学习中基本用不到并且提醒一下以上中的算法效率和稳定性千万不要死记因为之前说过这些算法的效率基本都不稳定不同的情况可能出现不同的效率而某些算法的设计不同可能稳定也可能不稳定因此理解算法的思想和如何实现尤为重要。
