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:

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,

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

When the cursor

, 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)

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

So the time complexity is aboutO(N^2)

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

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

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

,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 gapof all values of the first element), exchange the two, otherwise

, 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

, 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

The model chosen is

. 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 whenn->infinity, the time complexity can be reduced to:

##In the next point,

, 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

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

The idea is actually the above two sorting methods Combining the advantages ofgrouping

insertion

embodies the idea ofdivide 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!