Algorithmically, the most basic is the sorting algorithm, almost in the interview, more or less you will be asked to hand write some of the basic algorithms. Today, Fish brother will take you to review these basic algorithms.
Quick sort
Introduction:
Quicksort is an improvement on bubbling sort.
Quicksort was proposed by C. A. R. Hoare in 1960. Its basic idea is: by a trip to sort to sort data split into separate two parts, one part of all the data are smaller than the other part of all data, and then of the two parts data respectively according to the method of quick sort, the entire sorting process can be recursive, to achieve the whole data into an orderly sequence.
Steps:
1) Set two variables I and j, when sorting starts: I =0, j= n-1;
2) Assign the first array element to key, i.e. key=A[0];
3) Start from j to search forward, that is, start from back to search forward (j–), find the first value A[j] less than key, and exchange the values of A[j] and A[I];
A[I] = A[j]; b [I] = A[j]; c [I] = A[j];
5) Repeat steps 3 and 4 until I =j; (In step 3 and step 4, no qualified value is found, that is, in step 3, A[j] is not less than key; in step 4, when A[I] is not greater than key, the values of j and I are changed so that j=j-1 and I = I +1 are found. Find the value that meets the condition, and the position of the I and j Pointers remain unchanged during the exchange. In addition, the process I ==j must be exactly when I + or j- is completed, at which point the loop ends.
Code:
//  Private void quickSort(int[] a,int left,int right){if(left < right){int I,j,t,temp; temp=a[left]; // I =left; j=right; while(i! J) = {/ / order is very important, first to find it from the right side while (a [j] > = temp & & I < j, j); While (a[I]<=temp && I <j) I ++; If (I <j) {t=a[I]; a[i]=a[j]; a[j]=t; } // a[left]=a[I]; a[i]=temp; quickSort(a,left,i-1); QuickSort (a, I +1,right); // To continue with the left, there is a recursive procedure quickSort(a, I +1,right); // Continue with the right-hand side, here is a recursive process}} //  Call / / & emsp; quickSort(a,0,a.length-1);Copy the codeMerge sort
Introduction:
Merge-sort is an effective sorting algorithm based on MERGE operation. 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.
Steps:
1. Apply for a space equal to the sum of the two sorted sequences, which is used to store the combined sequence;
2. Set two Pointers, the initial positions are respectively the starting positions of the two sorted sequences;
3. Compare the elements pointed to by the two Pointers, select the relatively small element into the merge space, and move the pointer to the next position;
4. Repeat Step 3 until a pointer reaches the end of the sequence;
5. Copy all remaining elements of the other sequence directly to the end of the merged sequence.
Code:
//  public class MergeSort { //  private  static  long  sum  =  0; /** *   *  <pre> *   *  Merge of two ways. *  Principle: Merge two ordered tables and one ordered table. *  </pre> *   * *   *  @param  a *   *  @param  s *   *  The starting index of the first ordered table *   *  @param  m *   *  The starting index of the second ordered table *   *  @param  t *   *  The end index of the second ordered table. * */ private static void merge(int[] a, int s, int m, int t) { int[] tmp = new int[t - s + 1]; int i = s, j = m, k = 0; while (i < m && j <= t) { if (a[i] <= a[j]) { tmp[k] = a[i]; k++; i++; } else { tmp[k] = a[j]; j++; k++; } } while (i < m) { tmp[k] = a[i]; i++; k++; } while (j <= t) { tmp[k] = a[j]; j++; k++; } System.arraycopy(tmp, 0, a, s, tmp.length); } /** ** ** public static void mergeSort(int[] a, int s, int len) {int size = a.length; int mid = size / (len << 1); int c = size & ((len << 1) - 1); //  -- -- -- -- -- -- -- merge to only one end of an ordered set of algorithm -- -- -- -- -- -- -- / / if (mid = = 0) return; //  ------ merge sort -------// for (int I = 0; i < mid; ++i) { s = i * 2 * len; merge(a, s, s + len, (len << 1) + s - 1); } //  ------- merge the remaining number and the reciprocal of an ordered set -------// if (c! = 0) merge(a, size - c - 2 * len, size - c, size - 1); //  -- -- -- -- -- -- -- recursive implementation next merge sort -- -- -- -- -- - / / mergeSort (a, 0, 2 * len); } public static void main(String[] args) { int[] a = new int[]{4, 3, 6, 1, 2, 5}; mergeSort(a, 0, 1); for (int i = 0; i < a.length; ++i) { System.out.print(a[i] + " " ); }}Copy the code}
Heap sort
Introduction:
Heapsort refers to a sort algorithm designed by using heap data structure. A heap is a nearly complete binary tree structure that also satisfies the property of a heap: the key value or index of a child node is always smaller than (or greater than) its parent node.
Steps:
Recommend a look at this article: www.cnblogs.com/chengxiao/p…
Code:
To create a large root heap:
// Build a big root heap: Private int[] buildMaxHeap(int[] array){// Start with the parent (array.length-1-1) /2 of array.length-1 and end with the root (0), For (int I =(array.length-2)/2; i>=0; i--){ adjustDownToUp(array, i,array.length); } return array; AdjustDownToUp (int[] array,int k,int length){int adjustDownToUp = adjustDownToUp(int[] array,int k,int length); for(int i=2*k+1; i<length-1; If (I <length && array[I]<array[I +1]){if(I <length && array[I]<array[I +1]){if(I <length && array[I]<array[I +1]){if(I <length && array[I]<array[I +1]){ } if(temp>=array[I]){// Root node >= If the keyword of the left and right children is larger than that of the left and right children, break is adjusted. }else{// array[k] = array[I]; Array [I] = array[I]; }} array[k] = temp; // The value of the adjusted node is placed at the final position}Copy the codeThe sorting
Public int[] heapSort(int[] array){array = buildMaxHeap(array); For (int I =array.length-1; i>1; i--){ int temp = array[0]; Array [0] = array[I]; array[0] = array[I]; array[i] = temp; adjustDownToUp(array, 0,i); } return array; }Copy the codeDelete the top element (that is, the maximum value in the sequence) : first swap the last element of the heap with the top element. Since the nature of the heap is destroyed at this time, the root node needs to be adjusted down.
Public int[] deleteMax(int[] array){array[0] = array[array.length-1]; array[array.length-1] = -99999; AdjustDownToUp (array, 0, array.length); adjustDownToUp(adjustDownToUp, 0, array.length) return array; }Copy the codeInsert to heap: place the new node at the end of the heap and then adjust the new node up.
Assume that the last element of the array array[array.length-1] is empty, and that the newly inserted node was initially placed there.
Public int[] insertData(int[] array, int data){array[array.length-1] = data; Int k = array.length-1; Int parent = (k-1)/2; // Parent node while(parent >=0 && data>array[parent]){array[k] = array[parent]; // parent node drop k = parent; if(parent ! = 0){ parent = (parent-1)/2; }else{// The root node has been adjusted, break the loop; } } array[k] = data; // Insert the node into the correct position return array; }Copy the codeSelection sort
Introduction:
Selection sort is a simple and intuitive sorting algorithm. It works by selecting the smallest (or largest) element from the data elements to be sorted and storing it at the beginning of the sequence. Then, it continues to find the smallest (or largest) element from the remaining unsorted elements and puts it at the end of the sorted sequence. And so on, until all the data elements to be sorted are sorted. Selection sort is an unstable sort.
Sorting effect:
Code:
//public static void selectSort(int[] a) { if((a == null) || (a.length == 0)) return ; for(int i = 0; i < a.length - 1; i ++){ int minIndex = i; For (int j = I + 1; j < a.length; If (a[j] < a[minIndex]){minIndex = j; if(a[j] < a[minIndex]){minIndex = j; Int temp = a[I]; int temp = a[I]; a[i] = a[minIndex]; a[minIndex] = temp; }Copy the code}
Bubble sort
Introduction:
Bubble Sort is a simple sorting algorithm in the field of computer science. It repeatedly walks through the column of elements to be sorted, comparing two adjacent elements in turn, and swapping them if they are in the wrong order (from largest to smallest, from A to Z). The task of visiting an element is repeated until no neighboring elements need to be swapped, that is, the element column has been sorted.
Steps:
1. Compare adjacent elements. If the first one is bigger than the second, swap them both.
2. Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair. At this point, the last element is going to be the largest number.
3. Repeat for all elements except the last one.
4. Keep repeating the above steps for fewer and fewer elements at a time until there are no more pairs to compare.
Code:
//public static void bubbleSort(int []arr) {int[] arr = {12,23,34,56,56,56, 56,78}; for(int i =0; i<arr.length-1; i++) { for(int j=0; j<arr.length-i-1; J++) {/ / - 1 in order to prevent overflow the if (arr [j] > arr [j + 1]) {int temp = arr [j]; arr[j]=arr[j+1]; arr[j+1]=temp; }}Copy the code}
Sorting effect:
Insertion sort
Introduction:
Insertion sort is a simple, intuitive and stable sorting algorithm. If there is an orderly data sequence, the requirements in this has been inserted into a row of good data sequence number, but still request after inserting the data sequence order, this time using a new method for sorting, insertion sort, insertion sort of basic operation is to insert a data to the already sorted data in order, The algorithm is suitable for sorting a small amount of data, and the time complexity is O(n^2). It’s a stable sorting method. The insertion algorithm divides the array to be sorted into two parts: the first part contains all the elements of the array but excludes the last element (the array has one more space to insert), and the second part contains only that element (the element to be inserted). After the first part is sorted, insert the last element into the sorted first part
Steps:
1. From the first element, the element can be considered sorted;
2. Take out the next element and scan from back to front in the sorted element sequence;
3. If the element (sorted) is larger than the new element, move the element to the next position;
4. Repeat step 3 until you find the position where the sorted element is less than or equal to the new element.
5. Insert the new element into the position and repeat Step 2.
Sort code:
Private void InsertSort(int[] a) {private void InsertSort(int I = 1; i < a.length; I ++) {// Int temp = a[I]; int j; for (j = i - 1; j >= 0; J -) {/ / will be bigger than the temp of moving back one if (a) [j] > temp) {a [j + 1) = a, [j]. } else { break; } } a[j + 1] = temp; // insert in}}Copy the codeHill sorting
Introduction:
Shell’s Sort, also known as “Diminishing Increment Sort”, is a more efficient and improved version of direct insert Sort. 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. [1]
Steps:
Can this blog, illustrated edition, very detailed: www.cnblogs.com/chengxiao/p…
Code:
/ / public static void main (String [] args) {int [] a = {49,38,65,97,76,13,27,49,78,34,12,64,1}; Int d=a.length; while(true) { d=d/2; for(int x=0; x<d; x++) { for(int i=x+d; i<a.length; i=i+d) { int temp=a[i]; int j; for(j=i-d; j>=0&&a[j]>temp; j=j-d) { a[j+d]=a[j]; } a[j+d]=temp; } } if(d==1) { break; }} system.out.println (" sort after: "); for(int i=0; i<a.length; i++) { System.out.print(a[i]+" "); }}Copy the code