当前位置:网站首页>Hill sort of sorting
Hill sort of sorting
2022-07-05 00:28:00 【Building Zzzz】
Catalog
Two 、 Specific code implementation
3、 ... and 、 Spatial complexity , Time complexity and stability
Preface
Previously, we learned about direct insertion sorting , Direct insertion sorting is used when the data is in reverse order , Time complexity will reach O(N^2), This is a high time complexity for a sort , So today we will optimize the direct insertion sort , The more ordered the data, the faster the speed of direct insertion sorting is used to optimize it .
One 、 What is Hill sort
Hill's ranking method is also called reducing increment method . The basic idea of Hill's ranking is : Divide all the records in the file to be sorted into groups ( The specific grouping is a complex problem , This function changes with the data , It's an unsolved problem , So far, there is no good incremental sequence to solve , It can be said that this incremental sequence can be taken in various ways , However, it should be noted that the value in the incremental sequence should not be divided 1 The common factor outside is to try to be prime , And the last increment value must be taken 1 To end the overall sorting , All the previous sorts are pre sort , The last increment sequence is 1 Time is the real sort ), All records with the distance of this group number are divided into the same group , And sort the records in each group . Then repeat the above grouping and sorting . When the number of groups reaches 1 when , The sorting of the overall number of groups can be completed by arranging all data records in a unified group . The specific sorting method still uses direct insertion sorting, but as the whole sequence becomes more and more orderly, the speed will be faster , Therefore, Hill sort is the optimization of direct insertion sort .
Two 、 Specific code implementation
/**
* In fact, it is a direct insertion sort
* @param array Sequence to be sorted
* @param gap Group number
*/
public static void shell(int[] array,int gap) {
for (int i = gap + 1; i < array.length; i++) {
int j = i - gap;
int tmp = array[i];
for (; j >= 0; j -= gap) {
if(tmp < array[j]){
array[j + gap] = array[j];
}else{
break;
}
}
array[j + gap] = tmp;
}
}
public static void shellSort(int[] array) {
int gap = array.length;
while (gap > 1) {
shell(array,gap);// Sort by changing the number of groups each time
gap /= 2;
}
shell(array,1);// Make sure the end is 1 Group
}
3、 ... and 、 Spatial complexity , Time complexity and stability
Time complexity :( Increment related )O(n ^ 1.3 - n ^ 1.5) Spatial complexity : O(1)( No more variables are used ) stability : unstable ( If there is a jump change in the sorting process, it is unstable )
summary
Hill sort is an optimization of direct sort , In fact, we can divide the specific groups randomly, but in the end, we must press 1 To distribute , Then it is to sort the whole , This also optimizes the insertion sort , But Hill sort is rarely used , But we must know how to do this !
边栏推荐
- 【C】(笔试题)指针与数组,指针
- Netcore3.1 JSON web token Middleware
- Complete knapsack problem (template)
- Deux nombres se remplacent
- How many triangles are there in the golden K-line diagram?
- Design of emergency lighting evacuation indication system for urban rail transit station
- 【北京大学】Tensorflow2.0-1-开篇
- 圖解網絡:什麼是網關負載均衡協議GLBP?
- 海思3559万能平台搭建:YUV422的踩坑记录
- 业务场景功能的继续修改
猜你喜欢
电力运维云平台:开启电力系统“无人值班、少人值守”新模式
业务场景功能的继续修改
雅思考试流程、需要具体注意些什么、怎么复习?
人脸识别5- insight-face-paddle-代码实战笔记
Fast analysis -- easy to use intranet security software
Fs8b711s14 electric wine bottle opener MCU IC scheme development special integrated IC
Application of fire fighting system based on 3D GIS platform
How many triangles are there in the golden K-line diagram?
Continuous modification of business scenario functions
Skills in analyzing the trend chart of London Silver
随机推荐
GDB common commands
Acrel-EMS综合能效平台在校园建设的意义
【雅思阅读】王希伟阅读P3(Heading)
How many triangles are there in the golden K-line diagram?
How to do the project of computer remote company in foreign Internet?
Hologres Query管理及超时处理
巩固表达式C# 案例简单变量运算
打新债开户注册安全吗?有没有风险的?靠谱吗?
PermissionError: [Errno 13] Permission denied: ‘data. csv‘
js如何实现数组转树
Enterprise application business scenarios, function addition and modification of C source code
Advanced template
Consolidated expression C case simple variable operation
Application of multi loop instrument in base station "switching to direct"
[paper reading] Tun det: a novel network for meridian ultra sound nodule detection
Leetcode70 (Advanced), 322
《论文笔记》Multi-UAV Collaborative Monocular SLAM
lambda expressions
Complete knapsack problem (template)
Remember to build wheels repeatedly at one time (the setting instructions of obsidian plug-in are translated into Chinese)