Select Sort Algorithms and Hill Sort Algorithms Detailed

Choosing the sort algorithm is one of the classic algorithms. You can imagine you are playing cards. Each card you get is the one to be sorted. You need to compare each card with the previous one and insert the card in the right place.The same is true for selection sorting, which treats the entire array as two parts, an ordered part and an unordered part.Now you need to compare the number of the disordered part to the ordered part and insert it in the right place

The following code is an inner loop for inserting a sort:

while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
    arr[insertIndex + 1] = arr[insertIndex];
    insertIndex--;
}

The while loop determines whether the current number is smaller than the previous number of the ordered part, and the previous index that must satisfy the ordered part is greater than 0, otherwise the bounds will be crossed.Value assignment occurs within the loop.The meaning is that when the judgment is correct, the number representing the current number is smaller than that of the ordered part, so a shift is needed, that is, assign the previous number to the latter number, and then move the subscript forward.Place the full code below:

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        //Number of insert operations required
        int insertVal = arr[i];
        int insertIndex = i - 1;
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];
            insertIndex--;
        }
        arr[insertIndex + 1] = insertVal;
    }
}

Finally, test the processing time of this algorithm when processing 10w data

public static void main(String[] args) {
    int[] arr = new int[100000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) (Math.random() * 8000000);
    }
    // System.out.println(Arrays.toString(arr));
    SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String start = sdf.format(new Date());
    System.out.println(start);
    insertSort(arr);

    String end = sdf.format(new Date());
    System.out.println(end);

}

The final result is:

But choosing a sort algorithm can be optimized, for example

{2,3,4,5,6,7,8,9,1} Like the current set of data, if sorted by a traditional insertion, a large number of shifts occur when the last digit is judged and shifted.To solve this problem, you need to set a step to insert and sort arrays into multiple decimal arrays.This simplifies the problem.

The code is as follows:

public static void shellSort(int[] arr) {
    for (int step = arr.length / 2; step > 0; step /= 2) {
        for (int i = step; i < arr.length; i++) {
            int j = i;
            int value = arr[i];
            if (arr[j] < arr[j - step]) {
                while (j - step >= 0 && value < arr[j - step]) {
                    arr[j] = arr[j - step];
                    j -= step;
                }
                arr[j] = value;
            }
        }
    }
}

The first level of loop in the code is to control the step loop, so that you can divide the array into several small arrays, and at step 1 the array becomes a basically ordered array, which makes sorting this array much more efficient.

Finally, test the processing time of this algorithm when processing 10w data

public static void main(String[] args) {
    int[] arr = new int[100000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) (Math.random() * 8000000);
    }
    // System.out.println(Arrays.toString(arr));
    SimpleDateFormat sdf = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String start = sdf.format(new Date());
    System.out.println(start);
    shellSort(arr);

    String end = sdf.format(new Date());
    System.out.println(end);

}

The final result is:

It is clear that this algorithm is still very efficient.

Tags: Java

Posted on Wed, 27 May 2020 09:54:19 -0700 by coffejor