How to sort 100 million random numbers in Java?

1. Direct insertion sorting

1. Illustrated insertion sorting

Idea: Literally, insertion is to put an element into a specific in the set, so we need to divide the sequence into two parts, one part is the ordered set, the other part is the set to be sorted

Illustration:

##In order to facilitate understanding, we will take the most special 4321 sequence as an example.

According to the above ideas, we need to divide the sequence into two parts. For the convenience of coding, we will divide the first one into two parts. Assuming that the elements are ordered sets, then our loop

should start from the second element, which is 3To avoid overwriting 3 in subsequent operations, we choose a temporary Variable to save 3. That is,

val=arr[1]

above, Since we are operating on the array, we also need to get the end of the

ordered set The index of an element is used as the 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 in the above figure) , we move the element 4 back, move the cursor forward, and continue to check whether other elements in the set are smaller than the element to be inserted until the cursor crosses the boundary. , so the loop terminates. The next round of comparison begins2. Code implementation

public static void insertSort(int[]arr){
        for(int i = 1 ; i < arr.length; i++){
            int val = arr[i];
            int valIndex = i - 1; //游标
            while(valIndex >= 0 && val < arr[valIndex]){ //插入的值比游标指示的值小
                arr[valIndex + 1] = arr[valIndex];
                valIndex--; //游标前移
            }
            arr[valIndex+1] = val;
        }
    }
1234567891011

3. Performance testing and time and space complexity

The actual running of 800,000 data takes 1 Minutes and 4 seconds (not an accurate value, each machine may be different)

Direct insertion is more efficient when there are fewer sorting records and the keywords are basically in order. High

Time complexity:

Number of keyword comparisons: KCN=(n^2)/2 Total number of moves:

RMN= (n^2)/2

So the time complexity is about O(N^2)

2. Hill sorting (exchange method )1. Illustration of ideas

#2. Code implementation

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){//开启插入排序
                    if(arr[ j ] > arr[ gap + j ]){ //可以根据升降序修改大于或小于
                        tmp = arr[gap + j];
                        arr[j+gap] = arr[j];
                        arr[j] = tmp;
                    }
                }
            }
            System.out.println(gap);
            System.out.println(Arrays.toString(arr));
        }
    }
12345678910111213141516

The most difficult thing to understand here should be the third for loop.

j = i - gap

, represents the first element in the group, that is,

j=0

,When the first element in the group is greater than the second element (Due to the logical classification, the index of the second element should be the increment gap of all values ​​of the first element), exchange the two, otherwise

j-=gap

, continue to compare or jump out of the loop, After traversing all the groups in this way, reduce the increment (i.e. gap/=2), and then continue the above steps until the increment gap When it is 1, the sequence sorting ends

3. Time complexityThe time complexity of Hill sorting depends on

the function of the incremental sequence

, which requires detailed analysis of specific issues , is not a definite value, which is also the fourth point that needs to be discussed

4. About the choice of incrementWhen we do the above sorting

Increment reduction

The model chosen is

gap/=2

. This is not the optimal choice. The selection of increments is an unsolved problem in the mathematical communitybut it can be determined. Yes, it has been proven through a large number of experiments that when n->infinity, the time complexity can be reduced to:

##In the next point,

In the shift method

, we have also done several experiments. We can be sure that for calculations within a certain scale (such as 800w~100 million), the speed of Hill sorting far exceeds that of heap sorting

, at least this is the case on my computer

3. Hill sorting (shift method)The exchange method is much slower than the shift method, so it is more Use the shift method

, and the shift method is more "like" insertion sorting than the exchange method

1. Idea

The idea is actually the above two sorting methods Combining the advantages of grouping

and

insertion

is very efficient.

embodies the idea of ​​divide and conquer, combining a relatively Cut a large sequence into several smaller sequences

2. Code implementation

public static void shellSort02(int[] arr){ //移位法
        for(int gap = arr.length/2 ; gap > 0 ; gap /= 2){ //分组
            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]){ //开始插排
                       // 插入
                       arr[valIndex] = arr[valIndex-gap];
                       valIndex -= gap; //让valIndex = valIndex-gap (游标前移)
                   }
                }
                arr[valIndex] = val;
            }
        }
    }
12345678910111213141516

3. Experimental results

The above is the detailed content of How to sort 100 million random numbers in Java?. For more information, please follow other related articles on the PHP Chinese website!