Shulou(Shulou.com)06/02 Report--

This article introduces the knowledge of "what is the order of C++ Hill". In the operation of practical cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Hill ranking

The average efficiency of the previous algorithms is not very good, but we notice that when the keys are basically orderly, the efficiency is * *, and when the number of keys is very small, the gap between n and N2 is not so obvious. Based on the above facts, D.L.Shell proposed reduced incremental sorting in 1959. The basic idea is to take an interval (gap), divide the sequence into several sub-sequences, and sort each sub-sequence by direct insertion; then gradually reduce the interval and repeat the above process until the interval is 1. At the beginning, there are few keys in each subsequence, and the efficiency of direct insertion is very high; with the reduction of the interval, the keys of the subsequence become more and more, but on the basis of the previous sorting, the keys are basically in order. the efficiency of direct insertion is still very high.

The time complexity of Hill sorting is difficult to measure, and the choice of gap is inconclusive. The program of gap= [gap/2] is written by *. As for why, just write.

Template void ShellSort (T a [], int N, int& KCN, int& RMN) {KCN = 0; RMN = 0; for (int gap = Namp 2; gap; gap = gap/2) for (int I = gap; I

= gap & & + + KCN & & temp < a [j-gap]; j-= gap) {a [j] = a [j-gap]; RMN++;} a [j] = temp; RMN++;}}

Test results:

Sort ascending N ^ 2 = 0.00120005 KCN/NlogN=0.903128 RMN=240010 RMN/N=24.001 RMN/ N ^ 2 = 0.0024001 RMN/NlogN=1.80626 Sort randomness N ^ 2 = 0.0024001 RMN/NlogN=1.80626 Sort randomness N ^ 2 = 0.00258935 KCN/NlogN=1.94868 RMN=383849 RMN/N=38.3849 RMN/ N ^ 2 = 0.00383849 RMN/NlogN=2.88875 Sort descending N ^ 2 = 0.00383849 RMN/NlogN=2.88875 Sort descending N ^ 2 = 0.00172578 KCN/NlogN=1.29878 RMN=302570 RMN/N=30.257 RMN/ N ^ 2 = 0.0030257 RMN/NlogN=2.27707

Notice that the test results are very inaccurate at this time, and the sort of 10000 integers can no longer be tested (it is estimated that the new machines are all 0ms, and I also have individual cases that are all zeros). So, the following is retested with a sort of 100000 integers:

Sort ascending N ^ 2 = 0.000150001KCN/NlogN=0.903094 RMN=3000012 RMN/N=30.0001 RMN/ N ^ 2 = 0.000300001RMN/NlogN=1.80619 Sort randomness N ^ 2 = 0.000300001RMN/NlogN=1.80619 Sort randomness N ^ 2: 230ms KCN=4041917 KCN/N=40.4192 KCN/ N ^ 2 = 0.000404192KCN/NlogN=2.43348 RMN=5598883 RMN/N=55.9888 RMN/ N ^ 2 = 0.000559888RMN/NlogN=3.37086 Sort descending Nang 100000 TimeSpared: 151ms KCN=2244585 KCN/N=22.4459 KCN/ N ^ 2 = 0.000224459KCN/NlogN=1.35137 RMN=3844572 RMN/N=38.4457 RMN/ N ^ 2 = 0.000384457RMN/NlogN=2.31466

The results show that Hill sorting is almost no worst-case scenario, whether it is positive order, reverse order, disorder, it does not take a lot of time, and the additional storage is O (1), which is really good. It's a really good choice until I figure out quick sort and heap sort, and I used it all the time.

This is the end of the content of "what is the order of C++ Hill?" thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.