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

This article mainly introduces Java how to arrange 100 million random numbers, the article is very detailed, has a certain reference value, interested friends must read it!

First, directly insert sort 1. Graphic arrangement

Idea: literally, insertion is to put an element into a specific set according to a certain rule, so we need to divide the sequence into two pieces, one is an ordered set, the other is a set to be sorted.

Illustration:

To make it easier to understand, let's take the most special 4321 sequence as an example.

According to the above idea, we need to divide the sequence into two parts. For coding convenience, we assume that the first element is an ordered set, so our loop should start with the second element, that is, 3.

To avoid overwriting 3 later, we choose a temporary variable to save 3. That is, val=arr above [1]

Since we are operating on array successors, we also need to get the index of the last element of the ordered collection as a cursor

When the cursor does not cross the boundary and the value to be inserted is less than the position indicated by the cursor (4 = 0 & & val in the figure above)

< arr[valIndex]){ //插入的值比游标指示的值小 arr[valIndex + 1] = arr[valIndex]; valIndex--; //游标前移 } arr[valIndex+1] = val; } }12345678910113.性能检测与时空复杂度 实际运行80w个数据耗时1分4秒(非准确值,每台机器可能都不一样) 直接插排在排序记录较少, 关键字基本有序的情况下效率较高 时间复杂度 : 关键字比较次数 : KCN=(n^2)/2 总移动次数 : RMN= (n^2)/2 因此时间复杂度约为 O(N^2) 二、希尔排序(交换法)1. 思路图解 2. 代码实现public static void shellSort(int[] arr){ //交换法 int tmp = 0; for(int gap = arr.length / 2 ; gap >

0; gap / = 2) {for (int I = gap; I

< arr.length ; i++){ //先遍历所有数组 for(int j = i - gap ; j >

= 0; j-= gap) {/ / enable insertion sorting if (arr [j] > arr [gap + j]) {/ / can be modified greater or less than tmp = arr [gap + j]; arr [j+gap] = arr [j]; arr [j] = tmp according to ascending or descending order } System.out.println (gap); System.out.println (Arrays.toString (arr));} 12345678910111213141516

The most difficult thing to understand here is the third for loop, j = I-gap, which represents the first element in the group, that is, jroom0

When the first element in the group is larger than the second element (because of the logical classification, the index of the second element should be all values of the first element + incremental gap), exchange the two, otherwise j-=gap, continue to compare or jump out of the loop

After traversing all the teams back and forth, reduce the increment (that is, gap/=2), and then continue the above steps until the increment gap is 1 and the sequence sorting ends

3. Time complexity

The time complexity of Hill sorting depends on the function of the incremental sequence, which requires a specific analysis of the specific problem, but not a definite value, which is also the fourth point that needs to be discussed.

4. About the choice of increment

The above-mentioned gap/=2 model is selected by incremental reduction when we do sorting, which is not the best choice. The selection of increment is an unsolved problem in the field of mathematics.

But what is certain is that through a large number of experiments, when n-> infinity, the time complexity can be reduced to:

In the next point, in the shift method, we have also done several experiments, and it is certain that Hill sorting is much faster than heap sorting for calculations in a certain scale (such as 80W ~ 100 million), at least on the author's computer.

III. Hill sorting (shift method)

The speed of the exchange method is much slower than the shift method, so it is more likely to use the ground shift method, and the shift method is more "like" insertion sort than the exchange method.

1. Train of thought

In fact, the idea is the combination of the above two kinds of sorting, which combines the advantages of grouping and insertion, which is very efficient.

It embodies the idea of divide and conquer, cutting a larger sequence into several smaller sequences.

two。 Code implementation public static void shellSort02 (int [] arr) {/ / shift for (int gap = arr.length/2; gap > 0; gap / = 2) {/ / grouped for (int I = gap; I

< arr.length ; i++){ //遍历 int valIndex = i; int val = arr[valIndex]; if(val < arr[valIndex-gap]){ //插入的值小于组内另一个值 while(valIndex - gap >

= 0 & & val < arr [valIndex-gap]) {/ / start insertion / / insert arr [valIndex] = arr [valIndex-gap]; valIndex- = gap; / / Let valIndex = valIndex-gap}} arr [valIndex] = val } 123456789101112131415163. Experimental results

These are all the contents of the article "how to arrange 100 million random numbers in Java". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

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.