当前位置:网站首页>Shell Sort
Shell Sort
2022-07-05 05:09:00 【ximen502_】
The content of this paper comes from Data structure Textbook (C Language version )
Shell Sort (Shell’s Sort), Also known as reducing incremental sorting (Diminishing Increment Sort), It is also a method of insertion sort , But in terms of time efficiency, it is much better than the previous insertion sorting .
its The basic idea yes : First, divide the whole record sequence to be sorted into several subsequences , separately , Direct insert sort , When the records in the whole sequence are basically in order , Do a direct insertion sort for all records again .
The above picture description is too ambiguous , Hard to understand , The detailed decomposition diagram is as follows :
Sort using increment ( Stepping ) One time for 5, 3, 1, The first round of use 5 For stepping , From the subscript 0 Start backward with the subscript (0+5) Compare the numbers at , Small numbers go forward ( left ), Big numbers go backwards ( On the right side ), Then the subscript is 1 Start , by 2 Start , Step backward in turn until there is no step for 5 The second number of , Then the first round of sorting is completed .
Let's take the first round as an example to analyze in detail :
- First step
- The second step
- The third step
- Step four
- Step five
The above is the detailed process of the first round of sorting , The second round , The third round just changed the step , The basic idea has not changed .
Hill sort algorithm uses Java The implementation is as follows
/** * Specific sorting process * @param arr * @param dk The incremental */
void shellInsert(int[] arr, int dk) {
// An array arr Make a hill insertion sort .
for (int i = dk; i < arr.length; i++) {
if (arr[i] <= arr[i - dk]) {
int temp = arr[i];
int j = 0;
for (j = i - dk; j >= 0 && temp <= arr[j]; j -= dk) {
arr[j + dk] = arr[j];
}
arr[j + dk] = temp;
}
}
}// Shell Insert
void ShellSort(int[] arr, int[] dlta, int t) {
// Sequence by increment dlta[0..t-1] For the sequence table arr Make Hill sort
for (int i = 0; i < t; i++) {
shellInsert(arr, dlta[i]);
}
}
@Test
public void fun1() {
int[] arr = {
49, 38, 65, 97, 76, 13, 27, 49, 55, 04 };
int[] dlta = {
5, 3, 1 };
ShellSort(arr, dlta, dlta.length);
System.out.println(Arrays.toString(arr));
}
The analysis of Hill sort is a complex problem , Because its time is a function of the sequence quantity taken , This involves some unsolved mathematical problems .( The printing time of the textbook 2009 year 2 month , The time of publication is 2007 year , This year, 2019 year , It's about past publication 12 year , I wonder if these mathematical problems have been solved over the years .) The rest is like : Local conclusions drawn from a large number of studies , Taking incremental sequence , Let's read the textbook , There's a lot of content .
边栏推荐
- How to choose a panoramic camera that suits you?
- Rip notes [rip three timers, the role of horizontal segmentation, rip automatic summary, and the role of network]
- stm32Cubemx(8):RTC和RTC唤醒中断
- Recherche de mots pour leetcode (solution rétrospective)
- Use assimp library to read MTL file data
- C4D simple cloth (version above R21)
- Judge the position of the monster in the role under unity3d
- win10虚拟机集群优化方案
- AutoCAD - isometric annotation
- UE4/UE5 虚幻引擎,材质篇,纹理,Compression and Memory压缩和内存
猜你喜欢
随机推荐
2022/7/1学习总结
Out and ref functions of unity
《动手学深度学习》学习笔记
China as resin Market Research and investment forecast report (2022 Edition)
Establish cloth effect in 10 seconds
BUUCTF MISC
中国针状焦行业发展研究与投资价值报告(2022版)
Pause and resume of cocos2dx Lua scenario
Embedded database development programming (zero)
Research and forecast report on China's solution polymerized styrene butadiene rubber (SSBR) industry (2022 Edition)
PMP考生,请查收7月PMP考试注意事项
AutoCAD - command repetition, undo and redo
Create a pyGame window with a blue background
中国金刚烷行业研究与投资预测报告(2022版)
Unity shot tracking object
669. Prune binary search tree ●●
mysql審計日志歸檔
Use of snippets in vscode (code template)
AutoCAD - graphic input and output
Research on the value of background repeat of background tiling