做一个网站怎么赚钱,网站建设方向,响应式布局代码怎么写,网站地图后缀朋友们、伙计们#xff0c;我们又见面了#xff0c;本期来给大家解读一下有关排序算法的相关知识点#xff0c;如果看完之后对你有一定的启发#xff0c;那么请留下你的三连#xff0c;祝大家心想事成#xff01; C 语 言 专 栏#xff1a;C语言#xff1a;从入门到精通… 朋友们、伙计们我们又见面了本期来给大家解读一下有关排序算法的相关知识点如果看完之后对你有一定的启发那么请留下你的三连祝大家心想事成 C 语 言 专 栏C语言从入门到精通 数据结构专栏数据结构 个 人 主 页 stackY、
目录 1.归并排序
1.1递归版本
代码演示
1.2非递归版本
代码演示
测试排序
改正代码1
测试排序
改正代码2
1.3递归版本的优化
代码演示
2.归并排序特性 1.归并排序 基本思想 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 归并排序也分为递归和非递归版本下面我们就来逐步学习 1.1递归版本 从上面的图中我们可以看出归并排序是分为两个阶段分解和合并那么转化为代码的思想就是先划分小区间然后将区间中最小的单独拿出来在另外的一个数组中进行尾插等到最后一组数据排完之后再将尾插排序完的整个数组再拷贝至原数组这样子就完成了整个数组的排序。 那么通过这个过程可以发现归并排序是需要单独开一个数组的所以它的 空间复杂度是ON另外归并排序是先划分小区间再进行排序那么就和二叉树中的后序遍历逻辑类似先将整个数据一分为二使得左区间和右区间有序然后再将左右两个区间进行排序那么整个数据就有序了所以需要让左右区间再有序也需要将做右区间各划分为两个区间并且让它们的左右区间再有序以此类推直到区间内只剩一个数据就不需要再划分了然后取两个区间小的值尾插到单独的一个数组最后再次整体拷贝至原数组。 在递归时要注意几个问题 1. 在递归的时候需要保存两个区间的起始和终止位置以便访问。 2. 当一个区间已经尾插完毕那么直接将另外一个区间的数据依次尾插。 3. 两个区间的数据都尾插完毕至tmp数组时需要将tmp数组的数据再次拷贝至原数组。 4. 在拷贝到原数组时需要注意尾插的哪一个区间就拷贝哪一个区间。 代码演示 void _MergerSort(int* a, int begin, int end, int* tmp)
{//递归截止条件if (begin end)return;//划分区间int mid (begin end) / 2;//[begin,mid] [mid1,end]//递归左右区间_MergerSort(a, begin, mid, tmp);_MergerSort(a, mid 1, end, tmp);//将区间保存int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;//取两个区间小的值尾插//一个区间尾插完毕另一个区间直接尾插即可while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}//再将剩余数据依次尾插//哪个区间还没有尾插就尾插哪一个while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}//再重新拷贝至原数组//尾插的哪个区间就将哪个区间拷贝memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1));
}//归并排序
void MergerSort(int* a, int n)
{//先创建一个数组int* tmp (int*)malloc(sizeof(int) * n);_MergerSort(a, 0, n - 1, tmp);//释放free(tmp);
} 归并排序的特性总结 1. 归并的缺点在于需要 O(N) 的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度 O(N*logN) 3. 空间复杂度 O(N) 4. 稳定性稳定 1.2非递归版本 由于递归代码在数据太多时可能会因为递归太深出现问题所以我们也需要写出它们所对应的非递归版本的排序代码非递归版本的归并排序直接可以使用循环来完成但是坑点非常多接下来我们就来慢慢排查。 我们可以先一个数据为一组然后两两进行排序然后将排序完的整体结果再重新拷贝至原数组这样子就完成了一次排序然后再将排序完的结果两个数据为一组然后两两排序然后将排序完的数据再拷贝至原数组这样子就完成了第二次的排序然后将数据四个分为一组两两进行排序再将排序完的数据拷贝至原数组直到每组的数据超过或者等于数据的总长度即不需要在进行排序。 首先我们先创建一个开辟一个数组然后设置一个gap用来分组然后记录两个区间对两个区间的数进行比较小的尾插再将剩余数据继续尾插然后完成了一趟排序再将排完序的数据再拷贝至原数组再将gap * 2继续完成剩余的排序直到划分组的gap大于等于数据总长度即可完成全部的排序 代码演示 //归并排序
//非递归
void MergerSortNonR(int* a, int n)
{//创建数组int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(tmp);exit(-1);}//划分组数int gap 1;while (gap n){int j 0;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;//取两个区间小的值尾插//一个区间尾插完毕另一个区间直接尾插即可while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}//再将剩余数据依次尾插//哪个区间还没有尾插就尾插哪一个while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}}//将数据重新拷贝至原数组memcpy(a, tmp, sizeof(int) * n);//更新gapgap * 2;}//释放free(tmp);
} 测试排序 void PrintArry(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void TestMergerSortNonR()
{int a[] { 10,6,7,1,3,9,4,2 };PrintArry(a, sizeof(a) / sizeof(int));MergerSortNonR(a, sizeof(a) / sizeof(int));PrintArry(a, sizeof(a) / sizeof(int));
}int main()
{TestMergerSortNonR();return 0;
} 可以看到排序完成而且还完成的不错那么我们再来几组数据进行测试 在这里我们使用的是8个数据那如果我们使用9个或者10个数据呢 void PrintArry(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void TestMergerSortNonR()
{int a[] { 10,6,7,1,3,9,4,2,8,5 };PrintArry(a, sizeof(a) / sizeof(int));MergerSortNonR(a, sizeof(a) / sizeof(int));PrintArry(a, sizeof(a) / sizeof(int));
}int main()
{TestMergerSortNonR();return 0;
} 可以看到数据发生错误那么到底是为什么呢我们可以来一起观察一下 随着gap的2倍递增那么会发生数据区间越界的问题因为当数据是10个的时候gap会递增到8因此在访问数据的时候会发生越界我们也可以观察一下这个越界的现象 可以将数据访问的区间打印出来 那么该怎么解决这个问题呢 1. 首先不能排完一次序然后将数据整体拷贝需要排完一组拷贝一组。 2. 其次当发生越界中的第一、二种时可以直接break。 3. 当发生越界中的第三种时可以将边界进行修正。 改正代码1 //归并排序
//非递归
void MergerSortNonR(int* a, int n)
{//创建数组int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(tmp);exit(-1);}//划分组数int gap 1;while (gap n){int j 0;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;//end1和begin2越界直接跳出if (end1 n || begin2 n){break;}//end2越界可以进行修正if (end2 n){end2 n - 1;}//取两个区间小的值尾插//一个区间尾插完毕另一个区间直接尾插即可while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}//再将剩余数据依次尾插//哪个区间还没有尾插就尾插哪一个while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}//归并一组拷贝一组memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}//释放free(tmp);
} 测试排序 void PrintArry(int* a, int n)
{for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}void TestMergerSortNonR()
{int a[] { 10,6,7,1,3,9,4,2,8,5 };PrintArry(a, sizeof(a) / sizeof(int));MergerSortNonR(a, sizeof(a) / sizeof(int));PrintArry(a, sizeof(a) / sizeof(int));printf(\n);int a2[] { 10,6,7,1,3,9,4,2 };PrintArry(a2, sizeof(a2) / sizeof(int));MergerSortNonR(a2, sizeof(a2) / sizeof(int));PrintArry(a2, sizeof(a2) / sizeof(int));printf(\n);int a3[] { 10,6,7,1,3,9,4,2,8 };PrintArry(a3, sizeof(a3) / sizeof(int));MergerSortNonR(a3, sizeof(a3) / sizeof(int));PrintArry(a3, sizeof(a3) / sizeof(int));printf(\n);}int main()
{TestMergerSortNonR();return 0;
} 改正过后就完全的解决了越界的问题那么这种改进方法是归并一组拷贝一组。 我们也可以将全部越界的区间进行修正然后排序完一次将整个数据拷贝。 改正代码2 将越界区间全部修正也是可以达到改进的目的我们就以归并数据的逻辑为基础然后修改区间因此需要将越界的区间改为不存在的区间即可 //归并排序
//非递归
//改进代码2
void MergerSortNonR(int* a, int n)
{//创建数组int* tmp (int*)malloc(sizeof(int) * n);//划分组数int gap 1;while (gap n){int j 0;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;//将越界的区间修改为不存在的区间if (end1 n){end1 n - 1;//修改为不存在的区间begin2 n;end2 n - 1;}else if (begin2 n){//不存在的区间begin2 n;end2 n - 1;}else if (end2 n){end2 n - 1;}//取两个区间小的值尾插//一个区间尾插完毕另一个区间直接尾插即可while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[j] a[begin1];}else{tmp[j] a[begin2];}}//再将剩余数据依次尾插//哪个区间还没有尾插就尾插哪一个while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}}//整体拷贝memcpy(a, tmp, sizeof(int) * n);gap * 2;}//释放free(tmp);
} 1.3递归版本的优化 当数据量非常多的时候使用递归版本可以进行一个优化当递归到小区间的时候我们可以采用插入排序来进行优化这个优化只限于递归版本在进行小区间中的插入排序时需要注意在前面的步骤递归到了哪个区间就使用插入排序排序哪个区间所以在进行插入排序的时候需要注意排序的区间。 代码演示 void _MergerSort(int* a, int begin, int end, int* tmp)
{//递归截止条件if (begin end)return;小区间优化//区间过小时直接使用插入排序减少递归损耗if (end - begin 1 10){// 注意排序的区间InsertSort(a begin, end - begin 1); return;}//划分区间int mid (begin end) / 2;//[begin,mid] [mid1,end]//递归左右区间_MergerSort(a, begin, mid, tmp);_MergerSort(a, mid 1, end, tmp);//将区间保存int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;//取两个区间小的值尾插//一个区间尾插完毕另一个区间直接尾插即可while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}//再将剩余数据依次尾插//哪个区间还没有尾插就尾插哪一个while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}//再重新拷贝至原数组//尾插的哪个区间就将哪个区间拷贝memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1));
}//归并排序
void MergerSort(int* a, int n)
{//先创建一个数组int* tmp (int*)malloc(sizeof(int) * n);_MergerSort(a, 0, n - 1, tmp);//释放free(tmp);
}2.归并排序特性 1. 归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 2. 时间复杂度O(N*logN) 3. 空间复杂度O(N) 4. 稳定性稳定 朋友们、伙计们美好的时光总是短暂的我们本期的的分享就到此结束最后看完别忘了留下你们弥足珍贵的三连喔感谢大家的支持
