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 followsAnd 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 followsAnd 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 followsAnd 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 isIt'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 isIt'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...