当前位置:网站首页>Merge sort and non comparison sort
Merge sort and non comparison sort
2022-07-07 08:27:00 【Old fish 37】
Merging and sorting is still difficult to understand , We should master the recursive and non recursive methods of merge sorting .
Now let's first understand what merge sorting is :
Four words ---- Divide and rule
First merge from the whole small , Then to the overall consolidation
Complete code :
void _MerGetSort(int* arr, int begin, int end, int* tmp)
{
if (begin >= end)
{
return;
}// Divide the area
int mid = (begin + end) / 2;
// recursive
_MerGetSort(arr, begin, mid, tmp);
_MerGetSort(arr, mid + 1, end, tmp);
// Merge and compare
int begin1 = begin;
int end1 = mid;
int begin2 = mid + 1;
int end2 = end;
int i = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[i++] = arr[begin1++];
}
else
{
tmp[i++] = arr[begin2++];
}
}
// One of them must have finished Merge the rest into tmp in
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}// It's over , take tmp Copy back arr Array
memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MerGetSort(int* arr, int len)
{
// Open up an array
int* tmp = (int *)malloc(sizeof(int) * len);
_MerGetSort(arr, 0, len - 1, tmp);
free(tmp);
}
void PrintSort(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[] = { 3,1,2,4,9,5,6};
int len = sizeof(arr) / sizeof(arr[0]);
MerGetSort(arr, len);
PrintSort(arr, len);
}
The following describes non recursive writing :
void MerGetSort(int* arr, int len)
{
// Create a new array
int* tmp = (int*)malloc(sizeof(int) * len);
if (tmp == NULL)// Judge
{
printf("malloc fail\n");
exit(-1);
}
int gap = 1;// determine gap
while (gap < len)
{
printf("%d->", gap);
for (int i = 0; i < len; i += 2 * gap)
{
//[i, i + gap - 1] [gap + i, i + 2 * gap - 1] Divide the area
int begin1 = i, end1 = i + gap - 1;
int begin2 = gap + i, end2 = i + 2 * gap - 1;
printf("[%d][%d] [%d][%d]", begin1, end1, begin2, end2);
// Judge the cross-border area , And then modify
// because gap How much is the begin1 Will be the last , So from end1 Start to modify
if (end1 >= len)
{
end1 = len - 1;
begin2 = len; // here [begin2,end2]----[len,len-1] unreasonable , They don't execute
end2 = len - 1;
}
else if (begin2 >= len)// Invalid area modify
{
begin2 = len;
end2 = len - 1;
}
else if (end2 >= len)
{
end2 = len - 1;
}
int i = begin1;
// Then merge and compare
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[i++] = arr[begin1++];
}
else
{
tmp[i++] = arr[begin2++];
}
}
// After a walk , Put the remaining data into tmp
while (begin1 <= end1)
{
tmp[i++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = arr[begin2++];
}
}
printf("\n");
memcpy(arr, tmp, sizeof(int) * len);// Copy
gap = gap * 2;
}
}
void PrintSort(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[] = { 3,1,2,4,9,5,6};
int len = sizeof(arr) / sizeof(arr[0]);
MerGetSort(arr, len);
PrintSort(arr, len);
}
As for the invalid area, it refers to :
If you don't want to change the boundary , It can also be skipped directly , Revised as follows :
Method 2 :
such memcpy It's copied piece by piece , The first way is to copy all together , There are two ways to look at personal preferences .
Next, we will introduce non comparison sorting
What we will learn next is counting and sorting
Learn about counting sorting
This sort of counting has limitations :
1、 If it's a floating point number , String cannot be played
2、 If the data range is large , The space complexity will be very high , You can't play
3、 Generally, the difference between these data is relatively small
When you meet 100、1000 These data , If it's not much different , Using relative mapping is very practical .
// Count sorting
void CountSort(int* arr, int len)
{
int min = arr[0], max = arr[0];// The smallest and largest are the first Go to the back
for (int i = 1; i < len; i++)
{
if (arr[i] < min)
{
min = arr[i];
}
if (arr[i] > max)
{
max = arr[i];
}
}
// The largest and smallest have been found Open up space
int range = max - min + 1;
int* count = (int *)malloc(sizeof(int) * range);
if (count == NULL)
{
printf("malloc fail\n");
exit(-1);
}
memset(count, 0, sizeof(int) * range);// All initialized to 0// Count the number of times
for (int i = 0; i < len; i++)
{
count[arr[i] - min]++;
}// Write back sort
int j = 0;
for (int i = 0; i < range; i++)
{
while (count[i]--)
{
arr[j++] = i + min;
}
}
}
void PrintSort(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[] = { 1003,1001,1002,1004,1009,1005,1006};
int len = sizeof(arr) / sizeof(arr[0]);
CountSort(arr, len);
PrintSort(arr, len);
}
Here we classify the previous sorts , And flawed assessment
I hope all my friends can learn these sorting , Your support is my driving force !
If there is a mistake , Your smile !
边栏推荐
- 漏洞複現-Fastjson 反序列化
- 在 Rainbond 中一键安装高可用 Nacos 集群
- 藏书馆App基于Rainbond实现云原生DevOps的实践
- [quick start of Digital IC Verification] 11. Introduction to Verilog testbench (VTB)
- Obsidan之数学公式的输入
- MySQL introduction - crud Foundation (establishment of the prototype of the idea of adding, deleting, changing and searching)
- Leetcode medium question my schedule I
- Opencv learning note 4 - expansion / corrosion / open operation / close operation
- Iptables' state module (FTP service exercise)
- Qinglong panel -- finishing usable scripts
猜你喜欢
opencv学习笔记三——图像平滑/去噪处理
Lua programming learning notes
Battery and motor technology have received great attention, but electric control technology is rarely mentioned?
opencv学习笔记二——图像基本操作
JS copy picture to clipboard read clipboard
Low success rate of unit test report
Openvscode cloud ide joins rainbow integrated development system
iptables 之 state模块(ftp服务练习)
Installation and configuration of PLSQL
The single value view in Splunk uses to replace numeric values with text
随机推荐
Ebpf cilium practice (2) - underlying network observability
[quick start of Digital IC Verification] 10. Verilog RTL design must know FIFO
Offer harvester: add and sum two long string numbers (classic interview algorithm question)
Lua 编程学习笔记
Bisenet features
[quick start of Digital IC Verification] 13. SystemVerilog interface and program learning
AVL平衡二叉搜索树
Kotlin combines flatmap for filtering and zip merge operators
Deit learning notes
Practice of combining rook CEPH and rainbow, a cloud native storage solution
Openvscode cloud ide joins rainbow integrated development system
Give full play to the wide practicality of maker education space
数据中台落地实施之法
Zcmu--1396: queue problem (2)
The largest 3 same digits in the string of leetcode simple question
[IELTS speaking] Anna's oral learning records Part3
The truth of robot education in hands-on practice
饥荒云服管理脚本
在 Rainbond 中一键安装高可用 Nacos 集群
一文了解如何源码编译Rainbond基础组件