当前位置:网站首页>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 .
边栏推荐
- An article takes you to thoroughly understand descriptors
- Use the command character to close the keyboard command of the notebook
- Research and investment forecast report of adamantane industry in China (2022 Edition)
- 2020-10-27
- Simple HelloWorld color change
- Learning notes of "hands on learning in depth"
- django连接数据库报错,这是什么原因
- Pdf to DWG in CAD
- Three dimensional dice realize 3D cool rotation effect (with complete source code) (with animation code)
- 【论文笔记】Multi-Goal Reinforcement Learning: Challenging Robotics Environments and Request for Research
猜你喜欢
小程序直播+電商,想做新零售電商就用它吧!
十年不用一次的JVM调用
C4D simple cloth (version above R21)
win10虚拟机集群优化方案
UE4/UE5 虚幻引擎,材质篇,纹理,Compression and Memory压缩和内存
3dsmax scanning function point connection drawing connection line
Detailed introduction of OSPF header message
AutoCAD - continuous annotation
Unity3d learning notes
JVM call not used once in ten years
随机推荐
Common database statements in unity
Judge the position of the monster in the role under unity3d
Research on the value of background repeat of background tiling
Magnifying glass effect
中国聚氨酯硬泡市场调研与投资预测报告(2022版)
When will Wei Lai, who has been watched by public opinion, start to "build high-rise buildings" again?
2022/7/1 learning summary
Unity find the coordinates of a point on the circle
Cocos create Jiugongge pictures
64 horses, 8 tracks, how many times does it take to find the fastest 4 horses at least
PR first time
stm32Cubemx(8):RTC和RTC唤醒中断
Unity and database
Django reports an error when connecting to the database. What is the reason
UE fantasy engine, project structure
3dsmax scanning function point connection drawing connection line
Common technologies of unity
Use the command character to close the keyboard command of the notebook
"Measuring curve length" of CAD dream drawing
中国金刚烷行业研究与投资预测报告(2022版)