Summary of 7 commonly used sorting algorithms in Java

I have been free for a while, so I took some time to summarize the seven commonly used sorting algorithms in Java. I hope I can review them later!

1. Insertion sort algorithm

The basic idea of ​​insertion sort is that in the process of traversing the array, it is assumed that the elements before serial number i, that is, [0..i-1], have been sorted. This trip needs to find the correct position k of the element x corresponding to i, and in the process of finding this position k, move the compared elements back one position one by one to "make room" for the element x, and finally assign the element value corresponding to k to x. In general, the time complexity and space complexity of insertion sort are O(n2) and O(1), respectively.

 /**
 * @param int[] unsorted array
 * @return int[] sorted array
 */   
 
 public   int [] sortInsert( int [] array){
 for ( int i= 1 ;i<array.length;i++){
 int temp = array[i];
 int j;
 for (j=i- 1 ;j >= 0 && temp< array[j]; j--){
 array[j + 1 ] = array[j];
 }
 array[j + 1 ] = temp;
 }
 return array;
 }

2. Selection sort algorithm

The basic idea of ​​selection sort is to traverse the array, with i representing the number that needs to be sorted, and then find the minimum value in the remaining [i…n-1], and then exchange the minimum value found with the value pointed to by i. Because there is a sub-process of selecting the highest value in each process of determining the element, people figuratively call it selection sort. The time complexity and space complexity of selection sort are O(n2) and O(1) respectively.

 /**
 * @param int[] unsorted array
 * @return int[] sorted array
 */   
 
 public   int [] sortSelect( int [] arr){
 for ( int i = 0 ; i < arr.length; i++) {
 int miniPost = i;
 for ( int m = i + 1 ; m < arr.length; m++) {
 if (arr[m] < arr[miniPost]) {
 miniPost = m;
 }
 } 
 
 if (arr[i] > arr[miniPost]) {
 int temp;
 temp = arr[i];
 arr[i] = arr[miniPost];
 arr[miniPost] = temp;
 }
 }
 return arr;
 }

3. Bubble sort algorithm

Bubble sort is to put larger numbers at the bottom and smaller numbers at the top.

 /**
 * @param int[] unsorted array
 * @return int[] sorted array
 */   
 
 public   int [] sortBubble( int [] array){
 int temp;
 // First level loop: indicates the number of comparisons, for example, if there are length elements, the number of comparisons is length-1 (it is definitely not necessary to compare with itself)  
 for ( int i= 0 ;i<array.length- 1 ;i++){
 for ( int j = array.length - 1 ; j > i; j--) {
 if (array[j] < array[j - 1 ]) {
 temp = array[j];
 array[j] = array[j - 1 ];
 array[j - 1 ] = temp;
 }
 }
 }
 return array;
 }

4. Quick sort algorithm

Through a sorting process, the records to be sorted are divided into two independent parts. The keywords of one part of the records are smaller than those of the other part. Then, the two parts of the records can be sorted separately to achieve the purpose of ordering the entire sequence. The essence is to find a base position (pivot, watershed, which is smaller than the left and larger than the right. It can be random and named base. First, start from the rightmost side of the sequence to find a smaller one than base. If it is smaller, change the position, so that the base moves to the position on the right just now (smaller than the base when compared) (recorded as a temporary high position), so that the right side of the base is larger than the base. Then, start from the leftmost side of the sequence to find a larger one than base. If it is larger, change the position, so that the base moves to the position on the left just now (larger than the base when compared) (recorded as a temporary low position), so that the left side of the base is smaller than the base. Repeat the above two steps until low == high, which makes the pivot and watershed truly found. Return to this position, and recurse on the sequences on the left and right of the watershed respectively.

 /**
 * @param int[] unsorted array
 * @return int[] sorted array
 */   
 
 public   int [] sortQuick( int [] array){
 return quickSort(array, 0 , array.length- 1 );
 } 
 
 private   int [] quickSort( int [] arr, int low, int high) {
 if (low < height) {
 int division = partition(arr, low, high);
 quickSort(arr, low, division - 1 );
 quickSort(arr, division + 1 , high);
 }
 return arr;
 } 
 
 // Watershed, base, the ones on the left are smaller than this position, the ones on the right are larger  
 private   int partition( int [] arr, int low, int high) {
 int base = arr[low]; //Use the first record of the subtable as the pivot (watershed) record  
 while (low < heigh) { //Scan alternately from both ends of the table to the middle  
 while (low < high && arr[heigh] >= base) {
 heigh--;
 }
 // base is assigned to the current heigh position, base is moved (swapped) here, the right side of the heigh position is larger than base  
 swap(arr,heigh,low);
 while (low < high && arr[low] <= base) {
 low++;
 }
 // When the value on the left is larger than the base value, change the position  
 swap(arr,heigh,low);
 }
 // now low = high;  
 return low;
 } 
 
 private   void swap( int [] arr, int a, int b) {
 int temp;
 temp = arr[a];
 arr[a] = arr[b];
 arr[b] = temp;
 }

5. Merge sort algorithm

Merge sort is implemented recursively, which belongs to the "divide and conquer" method. The target array is divided into two from the middle, and then the two arrays are sorted separately. After the sorting is completed, the two sorted arrays are "merged" together. The most important thing about merge sort is the "merging" process. The merging process requires additional space that is the same length as the two arrays to be merged.

 /**
 * @param int[] unsorted array
 * @return int[] sorted array
 */  
 private   int [] sort( int [] nums, int low, int high) {
 int mid = (low + high) / 2 ;
 if (low < high) {
 // left  
 sort(nums, low, mid);
 // Right  
 sort(nums, mid + 1 , high);
 // Merge left and right  
 merge(nums, low, mid, high);
 }
 return nums;
 } 
 
 private   void merge( int [] nums, int low, int mid, int high) {
 int [] temp = new   int [high - low + 1 ];
 int i = low; // left pointer  
 int j = mid + 1 ; // right pointer  
 int k = 0 ;
 // Move the smaller numbers to the new array first  
 while (i <= mid && j <= high) {
 if (nums[i] < nums[j]) {
 temp[k++] = nums[i++];
 } else {
 temp[k++] = nums[j++];
 }
 }
 // Move the remaining numbers on the left into the array  
 while (i <= mid) {
 temp[k++] = nums[i++];
 }
 // Move the remaining numbers on the right into the array  
 while (j <= high) {
 temp[k++] = nums[j++];
 }
 // Overwrite the nums array with the numbers in the new array  
 for ( int k2 = 0 ; k2 < temp.length; k2++) {
 nums[k2 + low] = temp[k2];
 }
 } 
 
 public   int [] sortMerge( int [] array) {
 return sort(array, 0 , array.length - 1 );
 }

6. Shell sort algorithm

Shell sort was born because insertion sort encounters the problem of moving too many elements when processing large-scale arrays. The idea of ​​Shell sort is to "divide and conquer" a large array into several small arrays, divided by gap. For example, the array [1, 2, 3, 4, 5, 6, 7, 8], if divided by gap = 2, can be divided into two arrays [1, 3, 5, 7] and [2, 4, 6, 8] (correspondingly, if gap = 3, the divided arrays are: [1, 4, 7], [2, 5, 8], [3, 6]) and then insert sort the divided arrays separately. After each sub-array is sorted, reduce the gap value and repeat the previous steps until gap = 1, that is, insert sort the entire array. At this time, the array is basically sorted, so the elements that need to be moved will be very small, which solves the problem of a large number of moves when inserting sort is processing large arrays.

Shell sort is an improved version of insertion sort. It is very helpful to improve efficiency when the amount of data is large. When the amount of data is small, it is recommended to use insertion sort directly.

 /**
 * @param int[] unsorted array
 * @return int[] sorted array
 */   
 
 public   int [] sortShell( int [] array) {
 // Get the increment  
 int step = array.length / 2 ;
 while (step >= 1 ) {
 for ( int i = step; i < array.length; i++) {
 int temp = array[i];
 int j = 0 ;
 // The difference from insertion sort is here  
 for (j = i - step; j >= 0 && temp < array[j]; j -= step) {
 array[j + step] = array[j];
 }
 array[j + step] = temp;
 }
 step /= 2 ;
 }
 return array;
 }

7. Heap sort algorithm

The essence is to first construct a big top heap, parent is larger than children, the root node is the *** node, swap the *** node (root) with the tail node (the *** node, which is smaller), leaving the *** tail node, now ***, and the rest, starting from the *** element to the position before the tail node, construct a big top heap recursively.

 /**
 * @param int[] unsorted array
 * @return int[] sorted array
 */  
 public   int [] sortHeap( int [] array) {
 buildHeap(array); // Build heap  
 int n = array.length;
 int i = 0 ;
 for (i = n - 1 ; i >= 1 ; i--) {
 swap(array, 0 , i);
 heapify(array, 0 , i);
 } 
 
 return array;
 } 
 
 private   void buildHeap( int [] array) {
 int n = array.length; // Number of elements in the array  
 for ( int i = n / 2 - 1 ; i >= 0 ; i--)
 heapify(array, i, n);
 } 
 
 private   void heapify( int [] A, int idx, int max) {
 int left = 2 * idx + 1 ; // index of left child (if it exists)  
 int right = 2 * idx + 2 ; // index of left child (if it exists)  
 int largest = 0 ; // Find the index of the node with the largest value among the three nodes  
 if (left < max && A[left] > A[idx])
 largest = left;
 else  
 largest = idx;
 if (right < max && A[right] > A[largest])
 largest = right;
 if (largest != idx) {
 swap(A, largest, idx);
 heapify(A, largest, max);
 }
 }
 }
 // Create a heap function, assuming that only s is in [s, m]  
 // The corresponding keyword does not meet the definition of a big heap. Make [s, m] a big heap by adjusting ==========================================================  
 public   static   void heapAdjust( int [] array, int s, int m) {
 // Use the 0 subscript element as the temporary storage unit  
 array[ 0 ] = array[s];
 // Filter down along the larger child nodes  
 for ( int j = 2 * s; j <= m; j *= 2 ) {
 // Ensure that j is the subscript of the larger child node, j < m, ensure that j+1 <= m, and do not cross the boundary  
 if (j < m && array[j] < array[j + 1 ]) {
 j++;
 }
 if (!(array[ 0 ] < array[j])) {
 break ;
 }
 // If S is smaller, the larger child should be moved up  
 array[s] = array[j];
 // The value of the larger child becomes the smaller value of the S position, which may cause an imbalance in the top heap, so the heap where it is located is screened  
 s = j;
 }
 // If the S bit is larger, the value remains unchanged; otherwise, the S bit moves down to 2*s, 4*s, . . .  
 array[s] = array[ 0 ];