# Java Sorting Algorithms - Insert Sorting, Quick Sorting, Selective Sorting, Merge Sorting, Cardinal Sorting

Straight Insertion Sort

The basic operation is to insert a record into an ordered table, which has been arranged in order, so as to get a new ordered table with the number of records increased by 1. Generally speaking, it can be operated directly on the original array. ```public void insertSort(int[] nums) {
for(int i = 1;i < nums.length;i++) {
int val = nums[i];
//1. Find the location of nums[i] to insert
int j = i-1;
while(j >= 0 && nums[j] > val)
j--;
if(j == i-1)//Explain that you don't need to move elements
continue;
//2. Moving Elements
for(int t = i-1;t > j;t--)
nums[t+1] = nums[t];
//3. Insert Elements
nums[j+1] = val;
}
}```

Algorithmic analysis: The basic operations of insertion sort are comparison and moving elements, and the time complexity is as follows And in order to stabilize the sorting, the relative position of the original ordered elements will not be changed in the sorting process.

2. Bubble Sorting

Bubble sorting is to compare the first element with the second element, exchange if it is in reverse order, and then continue to compare the second and the third, and so on. Each lie-down sequence places a maximum value in its corresponding position. For example, from ascending order, the maximum value will be put behind each order. ```public void bubbleSort(int[] nums) {
for(int i = 0;i < nums.length -1 ;i++) {
for(int j = 0;j < nums.length -1 - i;j++) {
if(nums[j] < nums[j+1]) {
int temp = nums[j+1];
nums[j+1] = nums[j];
nums[j] = temp;
}
}
}
}```

Algorithmic analysis: Bubble sorting needs comparison and exchange, and the time complexity is as follows And it's a stable sort

Quick Sort

Through one-time sorting, the waiting records are divided into two separate parts, in which the keywords of one part of the records are smaller than the keywords of the other part of the records, and then the two parts of the records are sorted separately. Specific operations are as follows: setting two pointers low and high, setting pivot key as pivotkey, first from the high point forward search to find the first keyword less than pivotkey records and pivotkey exchange each other, and then from the low point backward search to find the first keyword greater than pivokey records and pivokey. Exchange with each other and repeat these two steps until low=high, where pivoykey is located. Quick sorting of the left and right sides, respectively ```public void quickSort(int[] nums,int low,int high) {
if(low == high || low > high)
return;//Explain that there is only one value
int temp1 = low;
int temp2 = high;
int pivotkey = nums[low];
//Do a sort
while(low < high) {
while(low < high && nums[high] >= pivotkey) {//Start at high to find a number smaller than pivotkey
high--;
}
nums[low] = nums[high];//Exchange with pivotkey when found
while(low < high && nums[low] <= pivotkey) {//Start at low to find a number smaller than pivotkey
low++;
}
nums[high] = nums[low];
}
nums[low] = pivotkey;
//low=high when exiting the loop
quickSort(nums,temp1,low-1);//Sinister
quickSort(nums,low+1,temp2);//Dexter
}```

Algorithmic analysis: Fast scheduling is mainly a comparison, and the time complexity is as follows And it's an unstable sort.

Select Sort

The basic idea of selective sorting: each record lying I n n-i-1 record selects the record with the smallest keyword as the first record of the ordered sequence. ```public void selectSort(int[] nums) {
for(int i = 0;i < nums.length-1;i++) {
int min = nums[i];
int index = i;
for(int j = i+1;j < nums.length;j++) {
if(nums[j] < min) {
min = nums[j];
index = j;
}
}
nums[index] = nums[i];
nums[i] = min;
}
}```

Algorithmic analysis: mainly for comparison, time complexity is It's an unstable sort.

Merging Sort

Merging is to combine two or more ordered tables into a new ordered table. ```//Merge Sort
public void mergeSort(int nums[]) {
if(nums.length < 2)
return;
int mid = nums.length / 2;
int[] left = new int[mid];
int[] right = new int[nums.length - mid];
for(int i = 0; i < mid;i++)
left[i] = nums[i];
for(int i = mid;i < nums.length;i++)
right[i-mid] = nums[i];
//Further decomposition of decomposed arrays
mergeSort(left);
mergeSort(right);
//Merge when no further decomposition is possible
merge(left,right,nums);
}
//Combine two numbers together
private void merge(int[] array1,int[] array2,int[] arrayNew) {
//int[] arrayNew = new int[array1.length + array2.length];
int i = 0;
int j = 0;
int k = 0;
while(i < array1.length && j < array2.length) {
if(array1[i] <= array2[j]) {
arrayNew[k] = array1[i];
i++;
}else {
arrayNew[k] = array2[j];
j++;
}
k++;
}
//There must be an array that's over.
for(;i < array1.length;i++) {
arrayNew[k] = array1[i];
k++;
}
for(;j < array2.length;j++) {
arrayNew[k] = array2[j];
k++;
}
}```

Algorithmic analysis: Time complexity is It's a stable sort.

Heap sorting

Cardinal ordination

8. The above ranking performance comparison table

 Sorting method Average time complexity Worst-case time complexity stability Insertion sort Bubble sort Quick sort Selective Sorting Merge Sort Heap sorting Cardinal sorting

To be continued...

Tags: less

Posted on Wed, 28 Aug 2019 00:10:29 -0700 by paul_r