This is the 20th day of my participation in the August Text Challenge.More challenges in August”
The last article covered basic and bubbling sort in data structures and algorithms. The main content of today’s article:
- Quick sort
- Insertion sort
- Selection sort
- Hill sorting
- Merge sort
Quick sort
1. introduce
Quicksort is an improvement on bubbling sort. By sorting the sorted data into two independent parts, one part of all the data is smaller than the other part of all the data, and then according to this method to the two parts of the data respectively for quick sorting, the whole sorting process can be carried out recursively, in order to achieve the whole data into an ordered sequence
2. Schematic diagram
3. Code implementation
Public class QuickSort {public static void main(String[] args) {public static void main(String[] args) {int[] arrays = new int[]{2,9,4,7,3,1,6,5}; sort(arrays,0,arrays.length-1); System.out.println(Arrays.toString(arrays)); } public static void sort(int[] arrays,int left,int right){ int l = left; // int r = right; Int pivot = Array [(left+right)/2]; Int temp = 0; /** * The purpose of the loop is to put the values less than Pivot on the left and the values greater than pivot on the right */ while (l<r){// Find the values greater than or equal to pivot on the left and exit from while (Arrays [L]<pivot){l+=1; Array [r]> Pivot {r-=1; If (l>=r){break; if (l>=r){break; } /** * temp = arrays[l]; arrays[l] = arrays[r]; arrays[r] = temp; /** * Array [l] == PiovT value, then r--; */ if (arrays[l]==pivot){ r-=1; Array [r] == piovt value, l++; */ if (arrays[r] == pivot){ l+=1; } / * * * if l must l++ = = r, r -, or a stack overflow * / if (l = = r) {l + = 1; r-=1; } if (left<r){ sort(arrays,left,r); } if (right>l){ sort(arrays,l,right); }}}}Copy the codeInsertion sort
1. introduce
Insertion sort belongs to internal sort, which is to find the appropriate position of the sorted element by insertion, and has achieved the purpose of sorting.
2. Schematic diagram
3. Code implementation
Public class InsertSort {public static void main(String[]) Args) {int[] arrays = new int[]{2,6,4,1,3,7,5}; sort(arrays); System.out.println(Arrays.toString(arrays)); } public static void sort(int[] arrays){ int[] arr = arrays; int temp; for (int i=1; i<arr.length; I ++){system.out.println (" "+ I +"); for (int j=i; j>=1; j--){ if (arr[j]<arr[j-1]){ temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; }else { break; } } } } }Copy the codeSelection sort
1. introduce
Selection sorting is also an internal sorting method, which selects an element from the data to be sorted according to the specified rules, and then exchanges positions with the rules to achieve the sorting purpose.
Here’s how it works:
The smallest (or largest) element is first selected from the data elements to be sorted and stored at the beginning of the sequence. The smallest (or largest) element is then found from the remaining unsorted elements and placed at the end of the sorted sequence. And so on until the total number of data elements to be sorted is zero. Selection sort is an unstable sort method.
2. Schematic diagram
3.The source code to achieve
Public class SelectSort {public static void main(String[]) Args) {int[] arrays = new int[]{2,6,4,1,3,7,5}; sort(arrays); System.out.println(Arrays.toString(arrays)); } public static void sort(int[] arrays){ for (int i=0; i<arrays.length; i++){ System.out.println(" "+i); int index = i; for (int j=arrays.length-1; j>i; j--){ if (arrays[j]<arrays[index]){ index = j; int temp = 0; temp = arrays[j]; arrays[j] = arrays[i]; arrays[i] = temp; } } } } }Copy the codeHill sorting
1. introduce
Shell’s Sort, also known as Diminishing Increment Sort, is a more efficient and improved version of the insertion Sort algorithm. Hill sort is an unstable sort algorithm. The method is named after D.L.Shell, who proposed it in 1959.
Hill sort is to group the records by a certain increment of the index and sort each group by direct insertion sort algorithm. As the increments decrease, each group contains more and more keywords, and when the increments decrease to 1, the entire file is exactly grouped and the algorithm terminates.
2. Schematic diagram:
3. The source code to achieve
Public class ShellSort {public static void main(String[] args) {int[] array = {7,3,2,5,9,4,8,1,6}; // shellSort(array); // Exchange method shellSort2(array); @param Arrays public static void shellSort(int[] Arrays){int temp = 0; int count = 0; for (int gap = arrays.length/2; gap>0; gap/=2){ for (int i=gap; i<arrays.length; i++){ for (int j=i-gap; j>=0; j-=gap){ if (arrays[j]>arrays[j+gap]){ temp=arrays[j]; arrays[j] = arrays[j+gap]; arrays[j+gap] = temp; }}} System. Out. Println (" first "+ + + the count () +" = "+ Arrays. ToString (Arrays)); Public static void shellSort2(int[] arrays){for (int gap= array.length /2; gap>0; gap/=2){ for (int i=gap; i<arrays.length; i++){ int j=i; int temp = arrays[j]; If (Arrays [J]< Arrays [j-gap]){while (j-gap>=0 &&temp <arrays[J-Gap]){// Movable Arrays [J] = Arrays [J-gap]; j-=gap; } arrays[j] = temp; } } } System.out.println(Arrays.toString(arrays)); }}Copy the codeMerge sort
1. introduce
Merge Sort is an efficient and stable sorting algorithm based on Merge operations. It is a typical application of Divide and Conquer. The ordered subsequences are combined to obtain a fully ordered sequence. That is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are merged into one ordered table, it is called binary merge.
2. Schematic diagram
We need to merge two already ordered subsequences into one ordered sequence, such as the last merge above, combining [2,4,5,6] and [1,3,7,8] already ordered subsequences into the final sequence [1,2,3,4,5,6,7,8]
3. The source code to achieve
Public class MergetSort {public static void main(String[]) public static void main(String[] Args) {int[] arrays = {8,4,7,2,3,6,1,5}; /** * Define a temporary array */ int[] temp = new int[array.length]; mSort(arrays,0,arrays.length-1,temp); System.out.println(Arrays.toString(arrays)); } public static void mSort(int[] array,int left,int right,int[] temp){ if (left<right){ int mid = (left+right)/2; /** * mSort(array,left,mid,temp); / mSort(array,mid+1,right,temp); / * * * combined * / sort (array, left, right, mid, temp); }} public static void sort(int[] arrays,int left,int right,int mid,int[] temp){ */ int I = left; Int j = mid+1; int j = mid+1; /** * int t = 0; /** * int t = 0; /** * Fill the temp array with the ordered order of the left and right data * until the ordered order of the left and right data * While (I <=mid &&j <=right){/** * if the current element of the left ordered sequence is less than or equal to the current element of the right ordered sequence, T ++, I ++ */ if (arrays[I]<=arrays[j]){temp[t] =arrays[I]; t+=1; i+=1; }else { temp[t] = arrays[j]; t+=1; j+=1; }} /** * fill the remaining data side of the data into temp all at once; */ while (i<=mid){ temp[t] = arrays[i]; t+=1; i+=1; } while (j<=right){ temp[t] = arrays[j]; t+=1; j+=1; } /** * copies elements from the Temp array to the Arrays array. So instead of copying everything at a time */ t=0; int tempIndex = left; while (tempIndex<=right){ arrays[tempIndex] = temp[t]; t+=1; tempIndex +=1; }}}Copy the code