当前位置:网站首页>[C language] merge sort
[C language] merge sort
2022-07-05 19:56:00 【Qihai】
Catalog
Preface :
*(ゝω・*ฺ) hi~ Welcome to my article ~ Here I will introduce two implementation methods of merge sorting : Recursion and non recursion .
notes : The following algorithms are in ascending order , Descending order only needs to be executed under the opposite conditions ~<*))>>=<
Merge sort
Merge sort It's based on Merger An effective method of operation , The stability of the Sorting algorithm , The algorithm adopts Divide and conquer method (Divide and Conquer) A very typical application . The ordered subsequence Merge , Get completely ordered Sequence ; So let's make each subsequence in order , Then make the subsequence segments in order . If two ordered tables are merged into one ordered table , be called Merge two ways .
Merger : Merging is actually dividing the whole into two parts , Then these two parts should be in order , Merge , Combine into a whole and order , If there is no order in these two sub parts, continue to divide , When it comes to monomer or nonexistence, it's orderly , Then step by step back .
Divide and conquer :“ Divide and rule ”, It means to divide a complex problem into several small problems , And then divide up , It can be easily solved , Then the solution of the original problem is actually the combination of the solutions of these small problems . The application here is to divide it into small pieces for sorting , Finally, get together and arrange it once .
1. Recursive version
demonstration :
( Let's say 2 6 3 0 1 4 5 This string of arrays to be sorted for demonstration )
1. Gradually divide into solvable problems ( Single or nonexistent is ordered )
2. Merge from back to front
Realization :
After the above demonstration , It's not hard to see , The first is to put the whole The number to be sorted is gradually divided into small pieces , Then merge . This is obviously a little similar In the following order Algorithm , That is, you should deal with the left and right sides first , Then I'm merging .
Based on this , The program is not difficult to implement :
// Auxiliary merge sort recursive subfunction
void _MergeSort(int* a, int* tmp, int begin, int end)
{
if (begin >= end)
return;// Recursion ends with a single or nonexistent interval
// Similar to the following sequence :
int middle = (begin + end) / 2;
int begin1 = begin;
int end1 = middle;
int begin2 = middle + 1;
int end2 = end;
_MergeSort(a, tmp, begin1, end1);
_MergeSort(a, tmp, begin2, end2);
// At this time, I think [begin1, end1] and [begin2, end2] The two intervals are orderly
// Merge algorithm
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));// Memory manipulation function , You can copy the number of the entire array
}
// Merge sort Recursive version
void MergeSort(int* a, int n)
{
// First malloc An array
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf(" Failed to request memory \n");
exit(-1);
}
// For the first time 0 and n - 1 Incoming closed interval
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
}
tmp Array : When we merged , Need a medium to exchange numbers . If you operate on the original array , Will overwrite the original data , Cause data loss .
malloc: void *malloc( size_t size ); Request continuous space of specified bytes from heap memory .
memcpy:void* memcpy(void* dest, const void* src, size_t count); Copy the contents of a continuous space of specified bytes to dest.
_MergeSort: Subfunctions for recursion , Before merging , First, recurse both sides , Until you find satisfaction begin >= end End recursion when , Go back to the previous recursive function for the next operation , This will ensure that before merging , Both intervals are ordered .
2. Non recursive version
If the recursive version has too much data , Too many iterations , Will cause stack overflow , If we can implement a non recursive version , Make it borrow heap memory to sort , Heap memory is much larger than stack memory , Don't worry about overflow .
The implementation of non recursive version is a little special . I believe you also know the non recursive version of quicksort , That is achieved by using stack or queue data structure to store intervals . But is it applicable to the merge sort here .
From the previous recursive version, we know , This merging sort is to merge the numbers of these two intervals in the form of ranking in front, that is, after ranking . If you use the stack to store these intervals , First, store 0 To n - 1, Then store 0 To middle,middle + 1 To end , Then you can't take it out directly , Because it is uncertain whether these two intervals are orderly , So you need to continue saving into the interval , Relative trouble .
So let's think about it a little bit differently , Not all non recursive implementations need the help of data spaces like stacks , For example, the non recursive implementation of Fibonacci sequence , So can we implement it directly ?
demonstration :
1. Belong to 2 Of n The number of permutations to the power ([0 7])
Be careful , In this demonstration , Each time, they are divided equally , Two, two . In order to achieve the accuracy of the code , Then we should distinguish No 2 Of n Odd and even times of power .
2. Do not belong to 2 Of n Odd order of power ([0 6])
We'll find out , For the first time, the interval 1 Conduct 2 Share 2 If you divide the shares 3 There is nothing to share , that 3 Keep it the same , Until there is 2 When assigned to this group, it can be carried out normally .
3. Do not belong to 2 Of n Even order of power ([0 9])
The same can be found here , The first time is ok 2 Points of , But not later , So after two points in the back , The corresponding ones without groups also remain unchanged , Until there is a corresponding group .
Realization :
Separate directly , Then merge . This code is not easy to write , It mainly distinguishes the three situations in the above demonstration .
We can define one gap Variable to determine the length of each interval , for the first time 1, The second time 2, third time 4, until <n The situation of , If the length of the array to be arranged is not 2 Of n To the power of , It is necessary to deal with it .
There are two processing methods in the following program , For the other two cases in the above demonstration .
// Merge sort Non recursive version
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
printf(" Failed to apply for space \n");
exit(-1);
}
// Whole exchange - 1
//int gap = 1;
//while (gap < n)
//{
// for (int i = 0; i < n; i += 2 * gap)// Cross two groups at a time
// {
// int begin1 = i, end1 = i + gap - 1; // [0, 0] [2, 2] [4, 4] [6, 6]
// int begin2 = i + gap, end2 = i + 2 * gap - 1; // [1, 1] [3, 3] [5, 5] [7, 7]
// // Boundary adjustment :begin1 Certainly not across the border , When end1 When you cross the border
// if (end1 >= n)
// {
// end1 = n - 1;
// // Give Way 2 If the series does not exist
// begin2 = 1;
// end2 = 0;
// }
// else if (begin2 >= n)
// {
// begin2 = 1;
// end2 = 0;
// }
// else if (end2 >= n)
// {
// end2 = n - 1;
// }
// // Merger
// int j = begin1;
// 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);// Whole copy , that No 2 To the power of n We need to adjust the boundary
// gap *= 2;
//}
// Every exchange - 2
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)// Cross two groups at a time
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
if (end1 >= n || begin2 >= n)
{
break;
}
else if (end2 >= n)
{
end2 = n - 1;
}
// Merger
int j = begin1;
int m = end2 - begin1 + 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) * m);// Local copy ,end2 - begin1 + 1
}
gap *= 2;
}
free(tmp);
}
gap:gap It is defined as the interval length of each division , The next time is the area where the two intervals merged last time , therefore gap Each cycle *2 that will do .
begin:begin1 and 2 Are the subscripts at the beginning of the two intervals . according to i The distinction between ,i The first is 0, So according to gap Area length ,begin1 Naturally i,begin2 It has crossed an area , So it is i+gap
end:end1 and 2 Is the subscript at the end of two regions ,end1 Is the last subscript of the first region , Naturally, it is the beginning of the second region minus one , So it is i+gap - 1.end2 Is the last subscript of the second region , So naturally, it is the beginning of the third region minus one , namely i+gap*2-1.
For two special cases , There are two ways to deal with it , In fact, it is a kind of , Just for memcpy It makes a difference whether it is copied section by section or as a whole . One is to skip the next step without processing , One is to deal with , Optimize the boundary .
边栏推荐
- Relationship between floating elements and parent and brother boxes
- Force buckle 1200 Minimum absolute difference
- Complete interview questions for interviewers and senior Android engineers in front-line Internet enterprises
- 深度學習 卷積神經網絡(CNN)基礎
- 【obs】libobs-winrt :CreateDispatcherQueueController
- 如何安全快速地从 Centos迁移到openEuler
- The city chain technology Digital Innovation Strategy Summit was successfully held
- 《乔布斯传》英文原著重点词汇笔记(十二)【 chapter ten & eleven】
- webuploader文件上传 拖拽上传 进度监听 类型控制 上传结果监听控件
- aggregate
猜你喜欢
Worthy of being a boss, byte Daniel spent eight months on another masterpiece
Based on vs2017 and cmake GUI configuration, zxing and opencv are used in win10 x64 environment, and simple detection of data matrix code is realized
Parler de threadlocal insecurerandom
【C语言】字符串函数及模拟实现strlen&&strcpy&&strcat&&strcmp
What is the core value of testing?
众昂矿业:2022年全球萤石行业市场供给现状分析
Let's talk about threadlocalinsecurerandom
Base du réseau neuronal de convolution d'apprentissage profond (CNN)
【硬核干货】数据分析哪家强?选Pandas还是选SQL
【无标题】
随机推荐
MySql的root密码忘记该怎么找回
Postman core function analysis - parameterization and test report
How to safely and quickly migrate from CentOS to openeuler
C - sequential structure
深度學習 卷積神經網絡(CNN)基礎
Debezium series: idea integrates lexical and grammatical analysis ANTLR, and check the DDL, DML and other statements supported by debezium
国信证券在网上开户安全吗?
After 95, Alibaba P7 published the payroll: it's really fragrant to make up this
【硬核干货】数据分析哪家强?选Pandas还是选SQL
淺淺的談一下ThreadLocalInsecureRandom
打新债在哪里操作开户是更安全可靠的呢
The city chain technology Digital Innovation Strategy Summit was successfully held
Common operators and operator priority
Two pits exported using easyexcel template (map empty data columns are disordered and nested objects are not supported)
C#应用程序界面开发基础——窗体控制(6)——菜单栏、工具栏和状态栏控件
1:引文;
C application interface development foundation - form control (5) - grouping control
2023年深圳市绿色低碳产业扶持计划申报指南
Worthy of being a boss, byte Daniel spent eight months on another masterpiece
Tasks in GStreamer