当前位置:网站首页>Insert sort and Hill sort
Insert sort and Hill sort
2022-07-06 22:05:00 【Hou Jiashu】
Insertion sort
Insert an element into the sorted array
You can think of the first element of an unordered array as An ordered array with only one element
Then insert the elements in the array one by one into the appropriate position in the ordered array
When all elements are inserted into an ordered array , This array has been set to order
Dynamic diagram demonstration
The code logic is as follows :
Take ascending order
Pass the inserted element through tmp preservation
hypothesis At this time, there are i+1 Elements
The last element of the ordered array ( Largest element ) The subscript , Write it down as end
adopt end Traversal array , Find out the appropriate position for element insertion
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
take tmp And a[end] Compare ,
When a[end] > tmp when , take a[end] Move back one position , after end--
Then with tmp Compare , Until you find the right place
Two cases of suitable location
1. tmp > end
2.tmp Less than all elements in the array
When you find the right place , The cycle ends , Store the data in the right place (end + 1)
This is the step of inserting an element into an ordered array
Yes n Inserting and sorting an array of elements can be understood as
Insert... Into an ordered array containing one element n-1 Elements
When converted into code, it is
// Insertion sort
void InsertSort(int* a, int n)
{
int i = 0;
for(i=0;i<n-1;i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
The time complexity is O(N^2)
Shell Sort
Hill sort is an advanced sort of insert sort , Greatly optimize the efficiency of the insertion sort algorithm
Basic idea and code analysis implementation
Suppose the array has N Elements
Take one less than N The positive integer gap
Set the distance in the array to gap The elements of are divided into a group
Be careful : The elements between the groups do not coincide , When taking elements , The first group is marked below 0 The element of is the first element
The second type is marked as 1 The element of is the second element
......
Insert and sort each group of elements
int j = 0;
// Sort each group of elements
for (j = 0; j < gap; j++)
{
int i = 0;
// Sort a set of elements
for (i = j; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
After the gap Reduce and repeat the above steps
Take ascending order as an example
When gap > 1 when
This process is called pre sorting , In order to facilitate better and faster insertion sorting
gap The bigger it is , Large elements will reach the rear faster , Small elements move faster to the front
gap The smaller it is , The closer the data is to order
When gap == 1 when
Sort for insertion
in summary
void ShellSort(int* a, int n)
{
// according to gap Do the nesting
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
int j = 0;
for (j = 0; j < gap; j++)
{
int i = j;
for (i = 0; i < n - gap; i += gap)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
}
边栏推荐
- Explain ESM module and commonjs module in simple terms
- What can one line of code do?
- Search element topic (DFS)
- Happy sound 2[sing.2]
- GPS du début à l'abandon (XIII), surveillance autonome de l'intégrité du récepteur (raim)
- Four data streams of grpc
- Record the process of cleaning up mining viruses
- GNN,请你的网络层数再深一点~
- GNN, please deepen your network layer~
- [MySQL] online DDL details
猜你喜欢
Efficiency tool +wps check box shows the solution to the sun problem
The golden age of the U.S. technology industry has ended, and there have been constant lamentations about chip sales and 30000 layoffs
GPS从入门到放弃(十九)、精密星历(sp3格式)
GNN,请你的网络层数再深一点~
20 large visual screens that are highly praised by the boss, with source code templates!
GPS从入门到放弃(十二)、 多普勒定速
make menuconfig出现recipe for target ‘menuconfig‘ failed错误
LeetCode:1189. The maximum number of "balloons" -- simple
Happy sound 2[sing.2]
GPS從入門到放弃(十三)、接收機自主完好性監測(RAIM)
随机推荐
Reinforcement learning - learning notes 5 | alphago
GPS from getting started to giving up (12), Doppler constant speed
Basic introduction of figure
PostgreSQL modifies the password of the database user
Explain ESM module and commonjs module in simple terms
GPS from getting started to giving up (XV), DCB differential code deviation
ViT论文详解
QT | UDP broadcast communication, simple use case
Checkpoint of RDD in spark
Some problems about the use of char[] array assignment through scanf..
Search element topic (DFS)
Qt | UDP广播通信、简单使用案例
JS method to stop foreach
【sciter】: 基于 sciter 封装通知栏组件
Efficiency tool +wps check box shows the solution to the sun problem
MySQL related terms
What is the RDD operator in spark
About the professional ethics of programmers, let's talk about it from the way of craftsmanship and neatness
VIP case introduction and in-depth analysis of brokerage XX system node exceptions
【10点公开课】:视频质量评价基础与实践