Several common sorting algorithms in Java

1. Sorting is the operation of arranging a string of records incrementally or decrementally according to the size of one or some keywords. Sorting algorithm is how to arrange records according to requirements. Sorting algorithm has received considerable attention in many fields, especially in the processing of large amounts of data. An excellent algorithm can save a lot of resources. Considering various limitations and specifications of data in various fields, it takes a lot of reasoning and analysis to get an excellent algorithm in line with the reality.

2. Sorting algorithms can be divided into internal sorting and external sorting.

Internal sorting is the sorting of data records in memory.

External sorting is due to the large sorting data, which can not accommodate all sorting records at one time. External memory needs to be accessed in the sorting process.

Common internal sorting algorithms include bubble sort, selection sort, insertion sort, Hill sort, quick sort, merge sort, etc.

Of course: the actual sorting algorithm can be more than that. If you want to know other algorithms, you can refer to: https://baike.baidu.com/item/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95/5399605?fr=aladdin#3

III. this paper mainly introduces several common sorting algorithms

1) bubble sorting

A. bubble sorting is to obtain the maximum / minimum value through each traversal

B. place the maximum / minimum value at the tail / head

C. then divide the maximum / minimum value, and the remaining data is traversed to obtain the maximum / minimum value

D. code implementation

public static void main(String[] args) {

        int arr[] = {8,5,3,2,4};

        //冒泡
        for (int i = 0; i < arr.length; i++) {
            //外层循环，遍历次数
            for (int j = 0; j < arr.length - i - 1; j++) {
                //内层循环，升序（如果前一个值比后一个值大，则交换）
                //内层循环一次，获取一个最大值
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

-------------------------

E. sorting process (red: moved data)

5,4,8
3,8
2,8

2) Select Sorting

A. regard the first value as the minimum value

B. then compare with the following to find the minimum value and subscript

C. exchange the starting value and minimum value of this traversal

D. Description: during each traversal, take the minimum value found in the front as an ordered list, and the latter as an unordered list, and then traverse the unordered list to find the minimum value each time.

E. code implementation

public static void main(String[] args) {

        int arr[] = {6,4};

        //选择
        for (int i = 0; i < arr.length; i++) {
            //默认第一个是最小的。
            int min = arr[i];
            //记录最小的下标
            int index = i;
            //通过与后面的数据进行比较得出，最小值和下标
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    index = j;
                }
            }
            //然后将最小值与本次循环的，开始值交换
            int temp = arr[i];
            arr[i] = min;
            arr[index] = temp;
            //说明：将i前面的数据看成一个排好的队列，i后面的看成一个无序队列。每次只需要找无需的最小值，做替换
        }
    }

---------------------------

F. sorting process (red: moved data)

2,6,4
2,5
2,6
2,6

3) insert sort

A. by default, the comparison starts from the second data.

B. if the second data is smaller than the first, exchange. Then compare with the third data. If it is smaller than the previous data, insert (cunning). Otherwise, exit the loop

C. Description: by default, the first data is regarded as an ordered list, and the subsequent unordered list circulates each data. If it is smaller than the previous data, insert (exchange). Otherwise, exit.

D. code implementation

public static void main(String[] args) {

        int arr[] = {7,4};

        //插入排序
        for (int i = 1; i < arr.length; i++) {
            //外层循环，从第二个开始比较
            for (int j = i; j > 0; j--) {
                //内存循环，与前面排好序的数据比较，如果后面的数据小于前面的则交换
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = temp;
                } else {
                    //如果不小于，说明插入完毕，退出内层循环
                    break;
                }
            }
        }
    }

--------------------------

E. sorting process (red: orderly, black: disordered)

5,7,4
3,7

4) Hill sort (insert sort variant)

A. It is basically the same as insertion sorting

B. the difference is that the step size of each cycle is halved

C. Description: the basic principle is similar to insertion sorting, but the difference is. Insert sort by spacing multiple data.

D. code implementation

public static void main(String[] args) {

        int arr[] = {7,4};

        //希尔排序（插入排序变种版）
        for (int i = arr.length / 2; i > 0; i /= 2) {
            //i层循环控制步长
            for (int j = i; j < arr.length; j++) {
                //j控制无序端的起始位置
                for (int k = j; k > 0  && k - i >= 0; k -= i) {
                    if (arr[k] < arr[k - i]) {
                        int temp = arr[k - i];
                        arr[k - i] = arr[k];
                        arr[k] = temp;
                    } else {
                        break;
                    }
                }
            }
            //j,k为插入排序，不过步长为i
        }
    }

------------------------------

E. sorting process (step 4 / 2 / 1)

4,1,8,9,7 3,8 1,9

5) quick sort

A. confirm that the first data in the list is an intermediate value, and the first value is regarded as a vacancy (low pointer vacancy).

B. then, in the remaining queue, there are left and right pointers (high and low).

C. start moving the high pointer to the left. If you encounter data less than the middle value, assign the data to the low pointer vacancy, and treat the data of the high pointer as the vacancy value (high pointer vacancy). Then move the low pointer to the right and switch the low pointer movement.

D. when the low pointer moves to greater than the middle value, the value is assigned to the place where the high pointer is empty. Then, first move the high pointer to the left and switch the high pointer movement. Repeat operations c and D.

E. exit until the high pointer and low pointer are equal, and assign the intermediate value to the corresponding pointer position.

F. then view the left and right sides of the intermediate value into a row list for quick sorting.

G. code implementation

 public static void main(String[] args) {

        int arr[] = {7,6};

        //快速排序
        int low = 0;
        int high = arr.length - 1;
        quickSort(arr,low,high);  
    }

    public static void quickSort(int[] arr,int low,int high) {
        //如果指针在同一位置(只有一个数据时)，退出
        if (high - low < 1) {
            return;
        }
        //标记，从高指针开始，还是低指针（默认高指针）
        boolean flag = true;
        //记录指针的其实位置
        int start = low;
        int end = high;
        //默认中间值为低指针的第一个值
        int midValue = arr[low];
        while (true) {
            //高指针移动
            if (flag) {
                //如果列表右方的数据大于中间值，则向左移动
                if (arr[high] > midValue) {
                    high--;
                } else if (arr[high] < midValue) {
                    //如果小于，则覆盖最开始的低指针值，并且移动低指针，标志位改成从低指针开始移动
                    arr[low] = arr[high];
                    low++;
                    flag = false;
                }
            } else {
                //如果低指针数据小于中间值，则低指针向右移动
                if (arr[low] < midValue) {
                    low++;
                } else if (arr[low] > midValue) {
                    //如果低指针的值大于中间值，则覆盖高指针停留时的数据，并向左移动高指针。切换为高指针移动
                    arr[high] = arr[low];
                    high--;
                    flag = true;
                }
            }
            //当两个指针的位置相同时，则找到了中间值的位置，并退出循环
            if (low == high) {
                arr[low] = midValue;
                break;
            }
        }
        //然后出现有，中间值左边的小于中间值。右边的大于中间值。
        //然后在对左右两边的列表在进行快速排序
        quickSort(arr,start,low -1);
        quickSort(arr,low + 1,end);
    }

　　---------------------------

h. Sorting process (cyan: intermediate value, blue: data confirming position, red: data moving)

6,8
1,9

6) merge and sort

A. split the list in a peer-to-peer manner

B. when splitting small and fast, merge the smallest pieces according to the original splitting

C. when merging, start to compare the size through the left of the left and right blocks. Small data is placed in a new block

D. Description: to be simple, first split the two halves into the smallest unit, and then merge the two halves of data into an orderly list.

E. code implementation

public static void main(String[] args) {

        int arr[] = {7,1，6};

        //归并排序
        int start = 0;
        int end = arr.length - 1;
        mergeSort(arr,end);
    }

    public static void mergeSort(int[] arr,int start,int end) {
        //判断拆分的不为最小单位
        if (end - start > 0) {
            //再一次拆分，知道拆成一个一个的数据
            mergeSort(arr,(start + end) / 2);
            mergeSort(arr,(start + end) / 2 + 1,end);
            //记录开始/结束位置
            int left = start;
            int right = (start + end) / 2 + 1;
            //记录每个小单位的排序结果
            int index = 0;
            int[] result = new int[end - start + 1];
            //如果查分后的两块数据，都还存在
            while (left <= (start + end) / 2 && right <= end) {
                //比较两块数据的大小，然后赋值，并且移动下标
                if (arr[left] <= arr[right]) {
                    result[index] = arr[left];
                    left++;
                } else {
                    result[index] = arr[right];
                    right++;
                }
                //移动单位记录的下标
                index++;
            }
            //当某一块数据不存在了时
            while (left <= (start + end) / 2 || right <= end) {
                //直接赋值到记录下标
                if (left <= (start + end) / 2) {
                    result[index] = arr[left];
                    left++;
                } else {
                    result[index] = arr[right];
                    right++;
                }
                index++;
            }
            //最后将新的数据赋值给原来的列表，并且是对应分块后的下标。
            for (int i = start; i <= end; i++) {
                arr[i] = result[i - start];
            }
        }
    }

---------------------------

F. sorting process ()

5,6
5,6
1,7