Common sorting algorithm two

 1  //O(n2)
 2     public static void selectSort(int[] arr){
 3         for (int i = 0; i < arr.length-1; i++) {
 4             //Let's say the minimum is I
 5             int minIndex = i;
 6             //J starts at I plus 1
 7             for (int j = i+1; j <arr.length ; j++) {
 8                 //If the assumed minimum is greater than arr[j], then minIndex refers to arr[j]. 9                 //Otherwise, no if judgment is entered
10                 if(arr[minIndex]>arr[j]){
11                     minIndex = j;
12                 }
13             }
14             //If minIndex does not change, that is, minIndex is arr[I], and no swap is required
15             if(minIndex! =i) {
16                 int tmp = arr[i];
17                 arr[i] = arr[minIndex];
18                 arr[minIndex] = tmp;
19             }
20         }
21     }

 1 public class HeapSort {
 2 
 3     public static void  heapSort(int[] arr) {
 4         int temp= 0;
 5 //        int arr[] = {4, 6, 8, 5, 9};
 6         //Unordered sequences are built into a heap, and large or small top heaps are selected according to ascending or descending requirements
 7         for (int i = arr.length/2-1; i >= 0; i--) {
 8             adjustHeap(arr,i,arr.length);
 9         }
10         //System.out.println(Arrays.toString(arr));
11         //2). Swap the top element with the end element, and "sink" the largest element to the end of the array;12         //3). Rearrange the structure so that it meets the heap definition, and then continue swapping the top element with the current end element, repeating the adjust + swap step until the whole sequence is in order.
13         for (int j = arr.length-1; j >0 ; j--) {
14             temp = arr[j];
15             arr[j] = arr[0];
16             arr[0] = temp;
17             adjustHeap(arr,0,j);
18         }
19         //System.out.println(Arrays.toString(arr));
20     }
21 
22     //Resize an array (binary tree) into a large top heap
23     / * *
24 * Function: To complete the tree with I corresponding to the non-leaf nodes into the big top heap25 Int arr[] = {4, 6, 8, 5, 9}; => adjustHeap => {4, 9, 8, 5, 6}26 * If we call adjustHeap again and pass in I = 0 => we get {4, 9, 8,5, 6} => {9,6,8,5, 4}27      * @paramArr The array to be adjusted28      * @paramI means non-leaf nodes are indexed in the array29      * @paramLenght says that the length is gradually reduced as the number of elements continues to be adjusted30      * /
31     private static void adjustHeap(int arr[], int i,int length){
32         //First fetch the value of the current element and store it in a temporary variable
33         int temp = arr[i];
34         //Began to adjust35         //instructions36         //1. K = I * 2 + 1
37         for (int k = i*2+1; k <length; k=i*2+1) {
38             //Note The value of the left child is smaller than that of the right child
39             if(k+1<length && arr[k]<arr[k+1]) {40                 //K points to the right child
41                 k++;
42             }
43             //If the child is bigger than the parent
44             if(arr[k]>temp){
45                 //Assign the larger value to the current node
46                 arr[i] = arr[k];
47                 //!!!!!!!!! I points to k, and we keep going
48                 i=k;
49             }else{
50                 break;
51             }
52         }
53         //When the for loop is done, we've put the maximum value of the tree that has parent I at the top.
54         arr[i] = temp;//Place the temp value in the adjusted position
55     }
56 }

 1 public class MergeSort {
 2     public static void sort(int[] arr, int left, int right, int[] temp) {
 3         if (left < right) {
 4             int mid = (left + right) / 2;
 5             //I recurse to the left
 6             sort(arr, left, mid, temp);
 7             //I'm going to recurse to the right
 8             sort(arr, mid + 1, right, temp);
 9             //merge
10             merge(arr, left, mid, right, temp);
11         }
12     }
13 
14     / * *
15      * @paramArr sorted the original array16      * @paramLeft The initial index of the left ordered sequence17      * @paramMid intermediate index18      * @paramRight index19      * @paramTemp is an array for transfer20      * /
21     private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
22         int i = left; //Initialize I, the initial index of the ordered sequence on the left
23         int j = mid + 1; //Initialize j, the initial index of the ordered sequence on the right
24         int t = 0; //Points to the current index of the Temp array25         //(一)
26         //First, the left and right (ordered) data is regularly populated into the Temp array27         //Until one of the ordered sequences on the left and the right is done
28         while (i <= mid && j <= right) {
29             //If the current element of the ordered sequence on the left is less than or equal to the current element of the ordered sequence on the right30             //Fill the temp array with the current element on the left31             //Then t++, i++
32             if (arr[i] <= arr[j]) {
33                 temp[t++] = arr[i++];
34             } else {
35                 temp[t++] = arr[j++];
36             }
37         }
38 
39         //(二)
40         //Fill all the data on the side with remaining data in turn into Temp
41         while (i <= mid) {//The ordered sequence on the left, with any remaining elements, is filled with temp
42             temp[t++] = arr[i++];
43         }
44         while (j <= right) {//The ordered sequence on the right, with any remaining elements, is filled with temp
45             temp[t++] = arr[j++];
46         }
47 
48         //(三)
49         //Copy the elements of the TEMP array to arR50         //Note that you don't copy everything every time
51         t=0;
52         int tempLeft=left;
53         //First merge tempLeft = 0, right = 1//tempLeft = 2 right = 354         //Last time tempLeft = 0 and right = 7
55         while (tempLeft<=right){
56             arr[tempLeft++]=temp[t++];
57         }
58     }
59 }

 1 public class RadixSort {
 2     public static void sort(int[] arr){
 3         //1. Get the number of digits of the largest number in the array
 4         int max = arr[0]; //Let's say the first number is the largest number
 5         for (int i = 1; i <arr.length ; i++) {
 6             if(arr[i]>max){
 7                 max=arr[i];
 8             }
 9         }
10         //I'm going to get the largest number of digits
11         int maxlength =(max+"").length();
12         //Define a two-dimensional array representing 10 buckets, each of which is a one-dimensional array13         //instructions14         //1. A two-dimensional array contains 10 one-dimensional arrays15         //2. Each one-dimensional array (bucket) is set to arr.length in order to prevent data overflow when placing numbers16         //3. The name is clear, radix sort is a classical algorithm using space for time
17         int[][] bucket = new int[10][arr.length];
18         //To keep track of how much data is actually stored in each bucket, we define a one-dimensional array to keep track of how much data is put into each bucket at a time19         //You can understand it here20         //For example, bucketElementCounts[0] records the amount of data that can be put into a bucket[0]
21         int[] bucketElementCounts = new int[10];
22         for (int i = 0,n=1; i <maxlength ; i++,n*=10) {
23             //The first time is the bit, the second time is the tens place, the third time is the hundreds place..
24             for (int j = 0; j <arr.length ; j++) {
25                 int digitOfElement=arr[j]/n%10;
26                 bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];
27                 bucketElementCounts[digitOfElement]++;
28             }
29             //In the order of the bucket (the indices of the one-dimensional array are retrieved and placed in the original array)
30             int index =0;
31             //Iterate over each bucket and place the data in the bucket into the original array
32             for (int k = 0; k < bucketElementCounts.length; k++) {
33                 //If there's data in the bucket, we put it in the original array
34                 if(bucketElementCounts[k]! = 0) {35                     //Loop through the bucket, the KTH bucket (the KTH one-dimensional array), and put it into
36                     for (int l = 0; l < bucketElementCounts[k]; l++) {
37                         arr[index++]=bucket[k][l];
38                     }
39                 }
40                 //After round I +1, each bucketElementCounts[k] = 0 ！！！！
41                 bucketElementCounts[k]=0;
42             }
43            // System.out.println(Arrays.toString(arr));
44         }
45 
46     }
47 }