Writing in the front

  • Full text data structure

The complexity of the

Time complexity

  • It’s essentially the growth trend of the function. Avoid exponential algorithms
  • Time frequency,T(n)A for loop is n, two parallel for loops are 2n, and two nested for loops are n^2. Ignore constant terms, low order terms (order of magnitude large enough), and coefficients (power is ok, power is not).
  • Time complexity,O(n)omitT(n)Constant term, low degree term, coefficient

type

  • The constant order, no matter how many rows you execute, as long as there’s no loop, is O(1), doesn’t grow as the variable grows
  • The logarithmic order,log2n.2^x = nIn other words, it was executedxThe logarithmic order is just x
int i = 1;
while (i < n) {
    i = i * 2;
}
Copy the code
  • Linear order, n cycles at a time
  • Linear logarithmic order, linear order loop nested logarithmic order
  • Square order, linear order nested linear order
  • Exponential order, recursion, perform nested recursion of n rows and n columns, for example if 8 queens problem, unlimitedmaxSize, will go down infinitely; If a quadratic loop is nested n timesO(2^n)

Spatial complexity

  • The amount of memory consumed, the amount of storage temporarily occupied by an algorithm
  • In actual development, hardware cost is not considered, and most algorithms are adoptedSpace for timeTo optimize

Sorting algorithm

  • Internal sort, all the data that needs to be processed are loaded into internal memory for sorting
  • External sort: The amount of data is too large to be loaded into the memory. You need to use external storage for sorting

Bubble sort

  • By treating the sorted sequence from front to back, starting from the element with the smaller subscript, compare the value of adjacent elements in turn, if the previous element is found to be large, then swap, and finally formascending, from front to back, rising like bubbles
  • Optimization, sorting, where the elements are getting closer and closer to where they are, and if there’s no swapping going on, it means that the sequence is in order, because by settingFlag flagsAvoid unnecessary sorting
  • A total ofArray size -1 timesSort, compare in pairs, the first trip is the largest, the second trip is the second largest, and so on
  • becausebigIt’s transitive, the number from the beginning to the end must be greater than all the preceding numbers
//3, 9, -1, 10, -2 int[] arr = {3, 9, -1, 10, -2}; int temp = 0; // The first row is the biggest, the second row is the last.... //0 1 2 3 //-1 -2 -3 -4 for (int j = 0; j < arr.length - 1; j++) { for (int i = 0; i < arr.length - j - 1; i++) { if (arr[i] > arr[i+1]) { temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; } } System.out.println(Arrays.toString(arr)); }Copy the code

To optimize the

  • If there is no change in one run, output directly; Record with identifier bits
int[] arr = {-1, 2, 3, 10, 9}; int temp = 0; // flag, whether changes have been made Boolean flag = false; for (int j = 0; j < arr.length - 1; j++) { for (int i = 0; i < arr.length - j - 1; i++) { if (arr[i] > arr[i+1]) { flag = true; temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; }} System. Out. Println (" first "+ (j + 1) +" trip "+ Arrays. ToString (arr)); If (flag == false) { } else {// If there is a change, set the flag back to false, record the next time flag = false; }}Copy the code

Selection sort

  • From the data to be sorted, select an element according to the specified rules, and then switch positions according to the specified
  • The first time, from0 ~ n - 1Pick the minimum andarr[0]Switch, the second time from1~n-1Select the minimum value, andarr[1]Swap, and so on
Int index = 0; Int min = 0; for (int i = 0; i < arr.length - 1; I ++) {// Assume that the ith is the smallest, starting with the ith each time, and rank the smallest first in each round index = I; min = arr[i]; For (int j =0 + I; for (int j =0 + I; j < arr.length; J ++) {// If (min > arr[j]) {min = arr[j]; index = j; }} // If, not the minimum assumed, change if (index! Arr [index] = arr[I]; arr[index] = arr[I]; arr[i] = min; }}Copy the code

Insertion sort

  • It is similar to playing poker, in which one card is picked up out of order, and the second card is picked up compared to the first card; When picking up the third sheet, compare it with the first two sheets and the largest sheet before the first two sheets
  • N sorted elements are regarded as an ordered table and an unordered table. At the beginning, the ordered table contains only one element, and the unordered table contains n-1 elements. During the sorting process, the first element is removed from the unordered table, compared with the ordered table in turn, and inserted
  • I just insertlength-1time
  • Time complexity,O(n^1)~O(n^2)
  • theinsertIndexThink of it as a pointer, looking for position
Int insertVal = 0; {{101}, {34, 119, 1}} {101}, {34, 119, 1}} {101}, {34, 119, 1} int insertIndex = 0; for (int i = 1; i < arr.length; i++) { insertVal = arr[i]; insertIndex = i - 1; Arr [n] = arr[n]; While (insertIndex >= 0 && insertVal < ARr [insertIndex]) {arr[insertIndex + 1] = arr[insertIndex]; insertIndex --; } //insertIndex+1 = I if (insertVal! Arr [I]) {// insertIndex + 1 arr[I] = insertVal; }}Copy the code

Hill sorting

  • Grouping sorting
  • Reduced increment sort is an insertion sort. Group by a certain increment of the subscript, sort each group by direct insertion sort, as the increment gradually decreases, when the increment is 1, insert sort, get the final result
  • For example, ten numbers10/2, according to the same step5 groups(increments), respectively, insert sort; again5/2, according to the same stepThe 2 groups, performing insertion sort; The last2/2Group 1, insert sort

Exchange method

  • Example analysis
int temp = 0; / / 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 / / I = 5 6 7 8 9 j = 0 1 2 3 4 / / {5, 0} {1} 6 better... for (int i = 5; i < arr.length; For (int j = i-5; int j = i-5; j >= 0; J - = 5) {if (arr [j] > arr + 5 [j]) {/ / if {0} 5 more arr [0] > arr [5] temp = arr [j]; arr[j] = arr[j+5]; arr[j+5] = temp; } } } System.out.println(Arrays.toString(arr)); // I = 2, 3, 4, 5, 6, 7, 8, 9 //j = 0 1 2 0 3 1 4 2 0 5 3 1 6 4 2 0 7 5 3 1 for (int I = 2; i < arr.length; For (int j = I - 2; int j = I - 2; j >= 0; j-= 2) { if (arr[j] > arr[j+2]) { temp = arr[j]; arr[j] = arr[j+2]; arr[j+2] = temp; } } } System.out.println(Arrays.toString(arr)); for (int i = 1; i < arr.length; I ++) {// for (int j = I - 1; j >= 0; j-= 1) { if (arr[j] > arr[j+1]) { temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } System.out.println(Arrays.toString(arr));Copy the code
  • extracting
int temp = 0; for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { for (int j = i - gap; j >= 0; j-= gap) { if (arr[j] > arr[j+gap]) { temp = arr[j]; arr[j] = arr[j+gap]; arr[j+gap] = temp; }}}}Copy the code

Mobile method

  • The swap method is insertion
for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; I ++) {// insert int insertVal = arr[I]; int insertIndex = i - gap; while (insertIndex >= 0 && insertVal < arr[insertIndex]) { arr[insertIndex + gap] = arr[insertIndex]; insertIndex -= gap; } if (insertVal ! = arr[i]) { arr[insertIndex + gap] = insertVal; }}}Copy the code

Quick sort

  • The improvement to bubble sort is that the array to be sorted is divided into two parts, one part smaller than the other, and implemented recursively
  • And the idea is, in each loop, you’re doing grouping recursion, and then you’re comparing two numbers, and you’re determining the order
  • Time complexityO(nlog2n)~O(n^2)

Describe the process

  • The rule of quickqueue is passKeep making the number on the left less than the number on the rightAnd reach the end of the processing through recursiontwo, until you are done, exit the recursion in turn. Assuming thatThe cardinality points to the middle (it can point anywhere), fromLeft and right sidesAt the same time, start moving towards the centerFind something larger than the base on the left or find the base and stop on the leftandFind something smaller than the base on the right or find the base and stop on the right
  • So, given these conditions, there are four possibilities
  • The first kind,Find the big ones on the left and the small ones on the right
  • The second,Find the small one on the right and the cardinal one on the left
  • The third,Find the large one on the left and the cardinal one on the right
  • The fourth,Find the cardinality at the same time
  • When you hit the first one, you switch the two numbers and keep looking until you reach the other three possibilities
  • And when you get to the second one, you switch the two numbers, and thenThe right hand side will go to the cardinal number, and the left hand side will go to the small number, if at this timeThere's still something in between, the loop will continue; If at this timeThere's no number between left and rightProceed to the next ruleThe left plus 1 points to the baseAt this time,Both left and right point to the cardinality and break out of the loop
  • When you get to the third, you switch the two numbers,The left hand side will point to the cardinal number, and the right hand side will point to larger numbers, if at this timeThere's still something in between, the loop will continue; If at this timeThere's no number between left and rightProceed to the next ruleThe plus one on the right-hand side points to the baseAnd now there’s another judgmentSo once you go to the base on the right, you go to the next oneAt this time,The position on the left is bigger than the position on the right
  • When you hit number four, jump out
  • So, at this point, it’s passedHandle one level of recursion, and to carry out sub-recursive pretreatment, at this time, there are two possibilities left in the face of the previous layer
  • The first kind,The left and right are equal, pointing to the same number
  • The second,The left side is bigger than the right side
  • When you encounter the first, you need to proceedPlus 1 on the left, minus 1 on the right, makes the position on the left larger than the position on the right. The reason is that if you don’t do this and add only one number to the left and right (there are only three or two numbers in total), you will recurse infinitely, because you can’t reach itLeft >= right critical valueandRight <= left critical value
  • In the second case, you don’t need to do this, because left and right are already staggered, and if there are only two or three numbers, left and right can’t go to the next level of recursion; And if you do that, you’re going to miss something in the middle, because you’re going to have to rebase every recursion
public static void quickSort(int[] arr, int left, int right) { int l = left; // int r = right; // right subscript int pivot = arr[(left + right) / 2]; Int temp = 0; While (arr[l] < pivot) {l += 1; while (arr[l] < pivot) {l += 1; While (arr[r] > pivot) {r -= 1; } // specify the same pointer, Pivot = pivot arr[r] = pivot arr[r] = pivot arr[r] = pivot arr if (l ==r)  { break; } temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; // If arr[l] == pivot, r is pointing to pivot's index. // Piovt's right is larger than Pivot's right, and pivot's left is pointing to pivot's left. If (arr[l] == pivot) {r -= 1; if (arr[l] == pivot) {r -= 1; } // If the switch is complete, arr[r] == pivot indicates that the median has been switched, l++ has moved, same as above. Then 'l>r' if (arr[r] == pivot) {l += 1; }} // If 'l' ==r 'points to' pivot ', then the position of the number in the subtree has been determined, so move 'L' and 'r' forward; // If I move in any case, I will miss the middle number; If arr[r] == pivot && arr[l] > pivot, then arr[r] == pivot && arr[l] > pivot, then arr[r] == pivot && arr[l]! = pivot's requirement to switch places with pivot, or to jump out of l == r when the left is all small and the right is all big. If (l == r) {l+ = 1; if(l == r) {l+ = 1; r -= 1; } if (left < r) {quickSort(arr, left, r); } if (right > l) {quickSort(arr, l, right); }}Copy the code

Merge sort

  • merge-sort
  • Using the idea of merging, using the classic divide-and-conquer strategy, the problempointsInto small problems, and then recursively solve them, andcureThe stage will bepointsThe answers are put together
  • Divide and combine
//8, 4, 5, 7, 1, 3, 6, 2 public static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left < right) { int mid = (left + right) / 2; /* left < right '; /* left < right '; /* left < right '; */ mergeSort(ARR, left, mid, Temp); // right // Even array 8, middle index 3, right from 4; // Mid +1 mergeSort(arr, mid+1, right,temp); Merge (arR, left, mid, right, temp); }}Copy the code
  • merge
/** * @param arr primitive array * @param left * @param mid * @param right * @param temp temporary array */ public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; Int j = mid + 1; Int t = 0; While (I <= mid &&j <= right) {// If the current element of the left ordered sequence is the same as the current element of the left ordered sequence, If (arr[I] <= arr[j]) {temp[t] = arr[I]; t ++; i ++; } else {// Right than left temp[t] = arr[j]; t ++; j ++; If (I <= mid) {if (I <= mid) {if (I <= mid) {if (temp[t] = arr[I]; t ++; i ++; } while (j <= right) {temp[t] = arr[j]; t ++; j ++; } // Copy the elements of the temp array to arr t = 0; int tempLeft = left; While (tempLeft <= right) {// While (tempLeft <= right) {// While (tempLeft <= right) {// While (tempLeft <= right) { Arr [tempLeft] = temp[t]; t ++; tempLeft ++; }}Copy the code

Radix sort

  • Space for time
  • Belong toThe distribution typeSorting,Bucket methodBy the value of each bit of the key value, the element to be sorted is assigned to somebarrelTo achieve the purpose of sorting
  • All the values to be compared are unified into the same digit length, and the number with shorter digit length is filled with zeros before it, and then sorted from the lowest digit
  • To compare theSingle digitsAnd makeSame order of magnitude (single digit only)Produces the order, and then comparesTen digitsThe process will beNumbers of the same order of magnitudePut it in a bucket and put it againA number with the same units and different tensCompare it out
  • Three numbers, for example53 52 2First roundIn the ones digit.52 2I put it in a bucket52 2 53; There is already an order for the units digit of each number, for example52 comes before 53. The second roundCompare tens.52 and 53In a bucket, and2In the first bucket, when placed in order,52 and 53Put them in a bucket in sequence, while2 and 52There is also a comparison of results
  • This shows that radix sort (bucket sort) compares many groups simultaneously in a single sort, such as in the process of comparing tensThe group with the same units digitandGroups of the same order of magnitudeAnd ifTen digit equalityBenefited from the previous roundThe order in which comparisons of the units digit occur

Rounds on

  • First round, playBits barrel
Arr. Length int[][] bucket = new int[10][arr. Length]; // To keep track of how much data is actually stored in each bucket, //bucketElementCounts[digitOfElement] int[] bucketElementCounts = new int[bucket.length]; for (int j = 0; j < arr.length; J ++) {// int digitOfElement = arr[j]; // Add it to the appropriate bucket. 'bucketElementCounts[digitOfElement]' bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; // bucketElementCounts[digitOfElement]++; Int index = 0; int index = 0; for (int k = 0; k < bucketElementCounts.length; If (bucketElementCounts[k]!) {if (bucketElementCounts[k]! = 0) { for (int l = 0; l < bucketElementCounts[k]; Arr [index] = bucket[k][l]; // Add index to array ++ index ++; BucketElementCounts [k] bucketElementCounts[k] = 0; bucketElementCounts[k] = 0; }Copy the code
  • Round two, play10 barrels
for (int j = 0; j < arr.length; J ++) {// int digitOfElement = arr[j] / 10%10; // 748/10 = 74%10 = 4 // add to the corresponding bucket 'digitOfElement' bucketElementCounts[digitOfElement] bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; // bucketElementCounts[digitOfElement]++; } // Add index = 0; for (int k = 0; k < bucketElementCounts.length; If (bucketElementCounts[k]!) {if (bucketElementCounts[k]! = 0) { for (int l = 0; l < bucketElementCounts[k]; Arr [index] = bucket[k][l]; // Add index to array ++ index ++; }}}Copy the code

Complete code

  • BucketElementCounts arrayDetermines the amount of memory in the KTH bucket, and when you need to copy the array back to the original array,Bucket [k] Number of bucket cyclesbybucketElementCounts[k]Decided to zero out after each round
Int Max = arr[0]; for (int i = 0; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; Int maxLength = (Max + "").length(); Arr. Length int[][] bucket = new int[10][arr. Length]; // To keep track of how much data is actually stored in each bucket, //bucketElementCounts[digitOfElement] int[] bucketElementCounts = new int[bucket.length]; for (int i = 0, n = 1; i < maxLength; I++, n *= 10) {// for (int j = 0; j < arr.length; J ++) {// int digitOfElement = arr[j] / n % 10; // Add to your bucket // add to your bucket // add to your bucket 'bucketElementCounts[digitOfElement]' bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j]; // bucketElementCounts[digitOfElement]++; Int index = 0; int index = 0; for (int k = 0; k < bucket.length; If (bucketElementCounts[k]!) {if (bucketElementCounts[k]! = 0) { for (int l = 0; l < bucketElementCounts[k]; Arr [index] = bucket[k][l]; arr[index] = bucket[k]; // Add index to array ++ index ++; BucketElementCounts [k] bucketElementCounts[k] = 0; bucketElementCounts[k] = 0; }}Copy the code

To deal with negative

  • The first idea is to separate the positive and negative arrays, deal with the absolute value of the complex number, and then undo it
ArrayList<Integer> postive = new ArrayList<>(); ArrayList<Integer> negative = new ArrayList<>(); for (int i : originArr) { if (i < 0) { negative.add(Math.abs(i)); } else { postive.add(i); } } Integer[] postiveArr = postive.toArray(length -> new Integer[length]); Integer[] negativeArr = negative.toArray(length -> new Integer[length]); / / sorting radixSort (postiveArr); radixSort(negativeArr); Int temp = 0; // If length is 7, I is 0, 1, 2, 3, 6, 5, 4. i < negativeArr.length / 2; I ++) {//negativeArr. Length -i -1 temp = negativeArr[negativeArr. Length -i -1] * -1; negativeArr[negativeArr.length - i - 1] = negativeArr[i] * -1; negativeArr[i] = temp; } // restore for (int I = 0; i < negativeArr.length; i++) { originArr[i] = negativeArr[i]; } for (int i = 0; i < postiveArr.length; i++) { originArr[negativeArr.length + i] = postiveArr[i]; }Copy the code
  • The second idea is to add an extra large value and then restore it
For (int I = 0; i < arr.length; i++) { arr[i] = arr[i] + 1000; } sort radixSort(arr); // restore for (int I = 0; i < arr.length; i++) { arr[i] = arr[i] - 1000; }Copy the code