Java several sorting algorithm implementation and simple analysis

This paper illustrates the implementation and simple analysis of several sorting algorithms in Java. Share with you for your reference. The details are as follows:

package test;
public class first {

public void insertSort(int[] list) {
int i, j;
list[0] = -999;
//It's like setting up a surveillance sentry, without having to judge whether or not the line is crossed,
//But you want the array to start with the second number which is I =1
for (i = 1; i < list.length; i++) {
j = i;
while (list[j] < list[j - 1]) {
int temp = list[j];
list[j] = list[j - 1];
list[j - 1] = temp;
j = j - 1;
}
}
}

public void binInsertSort(int[] r, int low, int high) {
for (int i = low + 1; i <= high; i++)
{
int temp = r[i]; //Save the element to be inserted
int hi = i - 1;
int lo = low; //Set the initial interval
while (lo <= hi)
{ //Halving to determine insertion position
int mid = (lo + hi) / 2;
if (temp < r[mid])
hi = mid - 1;
else
lo = mid + 1;
}
for (int j = i - 1; j > hi; j--)
r[j + 1] = r[j]; //Mobile elements
r[hi + 1] = temp; //Insert elements
}
}

public void shellSort(int[] r, int low, int high, int[] delta){
for (int k=0;k<delta.length;k++)
shellInsert(r, low, high, delta[k]);
}
private void shellInsert(int[] r, int low, int high, int deltaK){
for (int i=low+deltaK; i<=high; i++)
if (r[i]<r[i-deltaK]){
int temp = r[i];
int j = i-deltaK;
for(; j>=low&&temp<r[j]; j=j-deltaK)
r[j+deltaK] = r[j];
r[j+deltaK] = temp;
}
}

public void selectSort(int[] r, int low, int high) {
for (int k = low; k < high - 1; k++) { //Let's do n minus 1
int min = k;
for (int i = min + 1; i <= high; i++)
//Select the smallest element of the keyword
if (r[i] < r[min])
min = i;
if (k != min) {
int temp = r[k]; //The smallest element of the keyword is swapped with the element r[k]
r[k] = r[min];
r[min] = temp;
}// end of if
}
}

public void heapSort(int[] r){
int n = r.length - 1;
for (int i=n/2; i>=1; i--)
heapAdjust(r,i,n);
for (int i=n; i>1; i--){
int temp = r[1];
r[1] = r[i];
r[i] = temp;
heapAdjust(r,1,i-1);
}
}
//Adjust the heap
private void heapAdjust(int[] r, int low, int high){
int temp = r[low];
for (int j = 2 * low; j <= high; j = j * 2) {
if (j < high && r[j] < r[j + 1])
j++;
if (temp > r[j])
break;
r[low] = r[j];
low = j;
}
r[low] = temp;
}
public static void main(String[] args) {
first fs = new first();
int[] a = { 100, 9, 8, 9, 9, 7, 7, 0, 0, 99, 55, 7, 6, 5, 4, 3, 2, 1 };
int[] k={5,3,1};
// fs.insertSort(a);
//fs.binInsertSort(a, 0, a.length - 1);
//fs.shellSort(a, 0,a.length-1,k);
//fs.selectSort(a, 0, a.length-1);
fs.heapSort(a);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}

Insertion sort, exchange sort, selection sort, merge sort and other sort methods all have a common feature, that is, they determine the relative position between elements by comparing the size of the elements, that is, the above sort methods are sort methods based on comparison. Below, we make a comparison and summary on the sorting method based on comparison.
We compare the sorting methods from the aspects of average time complexity, worst time complexity, space complexity and stability of sorting.

Sorting method average time complexity worst time complexity stability of space complexity
Direct insertion sort Ο (n2) Ο (n2) Ο (1) is stable
Bubble sort Ο (n2) Ο (n2) Ο (1) is stable
Quick sort Ο (n log n) Ο (n2) Ο (log n) is not stable
Simple selection sort Ο (n2) Ο (n2) Ο (1) is not stable
Heap sort Ο Ο (n log n) (n log n) Ο (1) is not stable
Merge sort Ο (n log n) Ο Ο (n log n) (n) stability

In terms of time performance, quicksort is actually the best among all sorting algorithms, while quicksort's worst-case time performance is not as good as heap sort and merge sort. This can be avoided by improving quicksort, a kind of random quicksort by randomly selecting pivot elements, which makes the probability of a worst-case scenario so small that it can be considered nonexistent in practice. In the comparison between heap sort and merge sort, when n is large, merge sort takes less time, but it requires more secondary storage space.

From the method stability point of view, most of the time complexity of Ο (n2) the ranking method of sorting are stable, in addition to simple selection sort. Most of the time better sorting methods, such as quicksort, heap sort, and hill sort, are unstable. In general, the comparison in the sort process is between two adjacent elements and the sort method is stable.

Moreover, the stability of the sorting method is determined by the method itself. For the unstable sorting method, regardless of its description form, an unstable instance can always be found.

In summary, among all the sorting methods discussed above, none of them is absolutely optimal. In the actual use process, the appropriate sorting method should be selected according to different situations.

I hope this article has been helpful to your Java programming.