Learn more about Java basics

This series of notes is based on the geek Time course data Structures and The Beauty of Algorithms

This directory

  • How to analyze sorting algorithms
  • Bubble sort, insert sort, select sort O(n^2)
  • Quick sort, merge sort O(nlogn)
  • Count sort, radix sort, bucket sort O(n)
  • Order to optimize

preface

Sorting methods and complexity classification

  1. Several of the most classic, most commonly used sorting methods: bubble sort, insertion sort, selection sort, quicksort, merge sort, count sort, radix sort, bucket sort.
  2. Complexity classification
    • Bubble sort, insert sort, select sort O(n^2)
    • Quick sort, merge sort O(nlogn)
    • Count sort, radix sort, bucket sort O(n)

How to analyze a “sorting algorithm”?

1. Execution efficiency of the algorithm

  • Best, worst, and average case time complexity.
  • Coefficients, constants, and low orders of time complexity.
  • The number of comparisons, exchanges (or moves).

2. Stability of sorting algorithm

Stability concept: if there are elements with equal values in the sorted sequence, the original order of the elements will not change after sorting. Stability importance: Multiple attributes of an object can be prioritized. For example, sort the “order” in the e-commerce trading system according to the amount of the order data. For the orders of the same amount, sort the time of the following order in the morning and evening. Stable sorting algorithm can be used to solve the problem. The order is sorted according to the order time first, and the stable sorting algorithm is used to reorder according to the order amount after the sorting is completed.

3. Memory loss of sorting algorithm

In situ sorting algorithm: especially the sorting algorithm whose space complexity is O(1).

Order n^2

Bubble sort

Bubble sort only operates on two adjacent pieces of data. Each bubble operation compares the two adjacent elements to see if they meet the size relationship, and if not, swaps them.

  • Stability: Bubble sort is a stable sorting algorithm.
  • Spatial complexity: Bubble sort is an in-place sort algorithm.
  • Time complexity:

    • Best case (full order) : O(n).

    • Worst case (full inversion) : O(n^2).

    • Average case: in the best case, the initial order degree is N *(n-1)/2, in the worst case, the initial order degree is 0, then the average initial order degree is N *(n-1)/4, that is, the switching times is N *(n-1)/4, because the switching times < the comparison times < the worst case time complexity, so the average time complexity is O(n^2).

“Degree of order” and “degree of reverse order” : for an array that is not completely ordered, such as 4,5, 6, 3, 2, 1, the pairs of ordered elements are 3 (4,5), (4,6), (5,6), the degree of order is 3 and the degree of reverse order is 12;

For a completely ordered array, such as 1, 2, 3, 4, 5, 6, the order is n*(n-1)/2, which is 15, called full order; ** reverse order degree = full order degree - order degree; Bubble sort, insert sort swap (or move) times = degree of reverse order. 支那Copy the code

Insertion sort

Insertion sort divides array data into sorted and unsorted ranges. The initial sorted interval has only one element, the first element of the array. Insert an element from the unsorted interval into the appropriate position in the sorted interval until the unsorted interval is empty.

  • Stability: Insertion sort is a stable sort algorithm.
  • Spatial complexity: Insertion sort is an in-place sort algorithm.
  • Time complexity:
    • Best case: O(n).
    • Worst case: O(n^2).
    • Average: O(n^2) (the average time to insert a number into an array is O(n), repeated n times).

Selection sort

Selection sort divides an array into sorted and unsorted ranges. The initial sorted interval is empty. Each time the smallest element selected from the unsorted interval is inserted at the end of the sorted interval until the unsorted interval is empty.

  • Stability: Selection sort is not a stable sort algorithm.
  • Spatial complexity: Selection sort is an in-place sort algorithm.
  • Time complexity :(both O(n^2))
    • Best case: O(n^2).
    • Worst case: O(n^2).
    • Average case: O(n^2).

Order nlogn

Divide and conquer thoughts

  1. Divide and rule thought: divide and rule, thinking clearly, is to divide and rule, a big problem into small sub-problems to solve, small sub-problems solved, the big problem will be solved.
  2. The difference between divide and conquer and recursion: divide and conquer algorithms are generally implemented by recursion. Divide and conquer is a problem solving processing idea, recursion is a programming skill.

Merge sort

The algorithm first divides the array into two parts, then sorts the two parts separately, and then merges the sorted parts together so that the array is in order. That’s the whole idea of merge sort. The recursive formula is as follows:

Merge_sort (p... R) = merge (merge_sort (p... Q), merge_sort (q + 1... R)) termination condition: P >= r no further decompositionCopy the code

The stability of

The key to the stability of merge sort is the merge() function, which is the part of the code that merges two subarrays into an ordered array. If A[p… q] and A[q+1… r] have the same value, we can put the elements of A[p… q] into the TMP array as in the pseudo-code, so that the elements of the same value before and after the merge order remains the same. So merge sort is a stable sort algorithm.

Time complexity

Analyzing the time complexity of merge sort is analyzing the time complexity of recursive code. Recursion applies when:

  1. If a problem A can be decomposed into multiple subproblems B and C, solving problem A can be decomposed into solving problems B and C.
  2. After problems B and C are solved, we combine the results of B and C into the results of A.
  3. If the time for solving problem A is defined as T(a), then the time for solving problem B and C is T(b) and T(c) respectively, then the recurrence formula can be obtained as follows: T(a) = T(b) + T(c) + K, where K is equal to the time consumed to combine the results of two sub-problems B and C into the result of problem A.

Here is an important conclusion: not only the problem of recursive solution can be written as a recursive formula, but also the time complexity of recursive code can be written as a recursive formula. Applying this formula, the time complexity of merge sort can be expressed as:

T (1) = C; When n=1, only constant execution time is required, so it is denoted by C. T(n) = 2 times T(n/2) + n; N >1, where n is the time complexity O(n) of the merge() function merging two subarrays. T(n) = 2*T(n/2) + n = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n = 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n = 8*(2*T(n/16)  + n/8) + 3*n = 16*T(n/16) + 4*n ...... = 2^k * T(n/2^k) + k * n ......Copy the code

When T of n over 2 to the k is equal to T of 1, which is n over 2 to the k is equal to 1, we get k is equal to log base 2n. Plug k into the formula above and you get T(n)=Cn+nlog2n. In big O notation, T(n) is order nlogn. So merge sort is the complexity and the time complexity is order nlogn.

Spatial complexity

Merge sort is not in place sort, it’s order n. Why?

Because of the merge function of merge sort, extra storage is required to merge two arrays into one ordered array.

Why is the space complexity O(n) and not O(nlogn)?

If we follow the method of analyzing the time complexity of recursion, by recursive formula to solve, then the space complexity of the whole merge process is O(nlogn), but this kind of analysis is problematic! Because, in fact, the space complexity of recursive code and not accumulate like time complexity, but such a process, namely in every merger process need to apply for additional memory space, but after the completion of the merger, the memory space of temporary opening off and be released at any time, the CPU will only have a function in the implementation, There is only one temporary memory space in use. No amount of temporary space is larger than n data, so the space complexity is O(n).

Quick sort

The idea of quicksort is this: If we want to sort a set of data in an array with subscripts between P and R, we choose any data between P and R as the pivot (partition point). It then iterates over the data between P and R, placing those less than pivot on the left, those greater than pivot on the right, and povit in the middle. After this step, the data between p and r is divided into three parts. The first part is less than POvit from P to Q-1, the middle part is POvit, and the second part is greater than POvit from q+1 to R. According to the idea of divide-and-conquer and recursion, we can recursively sort the data with subscripts from P to Q-1 and the data with subscripts from q+1 to R until the interval is reduced to 1, indicating that all data are in order.

Quick_sort (p... R) = quick_sort (p... Q-1) + quick_sort(q+1, rCopy the code

The stability of

Since the partitioning process involves swapping, if there are two 8’s in the array, and one of them is pivot, after the partitioning process, the following 8 May be placed before the other 8, and the order will be reversed. Therefore, quicksort is an unstable sorting algorithm.

For example, if the array [1,2,3,9,8,11,8] takes the last 8 as pivot, then the partition swaps the last 8 with the last 9.

Time complexity

Best, worst, and average cases are also implemented recursively, so time complexity can also be expressed by recursive formulas. If each partition operation splits the array into exactly two cells of approximately equal size, the time-complexity recursive solution for quicksort is the same as that for merge.

T (1) = C; When n=1, only constant execution time is required, so it is denoted by C. T(n) = 2 times T(n/2) + n; N >1 therefore, the time complexity of quicksort is also O(nlogn).Copy the code

But the formula works only if, for each partition operation, we choose the right pivot to split the large interval equally. But in practice this is very difficult to achieve. Let me take an extreme example. If the data in the array is already ordered, say 1,3,5,6,8. If we choose the last element as pivot each time, the two intervals will not be equal for each partition. We need to partition approximately n times to complete the whole process of fast sorting. On average, we scan about n/2 elements per partition, in which case the time complexity of quicksort degrades from O(nlogn) to O(n2). The first two cases, partitioning and its equilibrium and partitioning disequilibrium, correspond to the best-case and worst-case time complexity of fast sorting respectively.

So what is the average time complexity of quicksort? T(n) is order nlogn most of the time, only degenerate to order n^2 in extreme cases, and there are many ways to reduce this probability.

Spatial complexity

Quicksort is a sort in place algorithm, order one.

Differences between merge sort and quicksort

  1. Merge sort is a recursive call, and then merge, and then exchange data. So it’s sort from the bottom up. What is bottom-up? That is, solve the child problem first, then solve the parent problem.
  2. Quicksort is partitioning first, and then when you’re doing recursive calls to partition, you’re exchanging data. So it’s sort from the top down. What is top-down? You solve the parent problem first, and then you solve the child problem.

O(n) level sort

Introduction to linear sorting algorithms

  1. Linear sort algorithm includes bucket sort, counting sort and radix sort.
  2. The linear sorting algorithm has O(n) time complexity.
  3. These three sorting algorithms do not involve the comparison between elements, and are non-comparison based sorting algorithms.
  4. The requirements for sorting data are very strict, so it is important to master the applicable scenarios of these three sorting algorithms.

Bucket sort

Algorithm principle:

1. The data to be sorted is sorted into several ordered buckets, and the data in each bucket is sorted separately. 2. After the bucket is sorted, take out the data in each bucket in sequence to form an orderly sequence.Copy the code

Conditions of use

1. The data to be sorted needs to be easily divided into M buckets, and there is a natural size order between buckets. 2. Data is evenly distributed among buckets.Copy the code

Applicable scenario

1. Bucket sort is suitable for external sort. 2. External sort means that a large amount of data is stored on an external disk, but the memory is limited and cannot load all data into the memory.Copy the code

The application case

Requirement description: There is 10GB of order data, which needs to be sorted by order amount (assuming the amount is positive integer), but the memory is limited, only a few hundred MB

Solution: Scan the file and look at the data range of the order amount, such as 1 yuan to 100,000 yuan, then divided into 100 barrels. The first bucket stores orders between 1 and 1000 yuan, the second bucket stores orders between 1001 and 2000 yuan, and so on. Each bucket corresponds to a file and is numbered and named according to the size of the bucket (00,01,02… , 99). Put 100 small files in memory one by one and sort them by quicksort. After all the files are sorted, you only need to read each small file in ascending order and write it to the large file.

Note: If a single file cannot be loaded into the memory, proceed with the preceding procedure for the file.

Counting sort

Algorithm principle

1. Counting is actually a special case of bucket sorting. 2. If the range of n data to be sorted is not large, for example, the maximum value is K, the data is divided into K buckets 3. The data values in each bucket are the same, eliminating the time spent sorting buckets.Copy the code

Conditions of use

1. It can only be used in scenarios with small data range. If the data range K is much larger than the data n to be sorted, it is not suitable for counting sort; 2. Counting sort can only sort non-negative integers. Other types need to be converted to non-negative integers without changing their relative sizes. 3. For example, if your test score is accurate to the last decimal place, you need to multiply all the scores by 10 to round them up.Copy the code

Case Study:

Suppose there are only eight examinees with scores between 0 and 5, and the scores are stored in the array A[8] = [2,5,3,0,2,3,0,3]. Buckets are represented by an array of size 6, C[6], with subscripts corresponding to scores, namely, 0,1,2,3,4,5. C[6] stores the number of examinees. You can get C[6] = [2,0,2,3,0,1] just by iterating the scores of each examinee. The sequential sum of the C[6] array is C[6]=[2,2,4,7,7,8], where C[k] stores the number of candidates less than or equal to the score k. The array R[8] = [0,0,2,2,3,3,3,5] stores the candidate ranking.

So how do I get R[8]?

From the back to the former, in turn, scanning array. A, such as scanning and 3, can from the array subscript 3 value 7 C, that is to say, so far, myself included, the examinee has seven score less than or equal to 3, that is to say, 3 is the seventh element of the array R (that is, the location of the array subscript is 6 in the R). When 3 is placed in R, there are six elements less than or equal to 3 left, and C[3] is subtracted by 1 to become 6.Similarly, when a second candidate with a score of 3 is scanned, it is placed at the position of the sixth element in array R (the subscript 5 position). After scanning array A, the data in array R is sorted in order of fractions.

Radix sort

Suppose we have 100,000 mobile phone numbers and we want to sort them from smallest to largest. What’s a quick way to sort them?

Algorithm principle

1. Compare the size of two mobile phone numbers A and B. If a is bigger than B in the first few digits, don't look at the next few digits. 2. Using the idea of stable sorting algorithm, you can first sort the phone number by the last bit, then resort it by the second to last, and so on, and finally resort it by the first bit. 3. After 11 sorting, the mobile phone number becomes in order. 4. The range of ordered data is small, and bucket or count sort can be used to complete the sorting.Copy the code

Conditions of use

1. Data can be divided into independent "bits" for comparison; 2. There is a progressive relationship between bits. If the high position of data A is larger than that of data B, there is no need to compare the remaining positions. 3. The data range of each bit should not be too large, and linear sorting should be possible; otherwise, the time complexity of radix sorting cannot reach O(n).Copy the code

Order to optimize

Why did you choose quicksort?

  1. Linear sort time complexity is very low but the use of special scenarios, if you want to write a general sort function, can not choose linear sort.
  2. In order to take into account the sorting of arbitrary scale data, the sorting algorithm with O(nlogn) time complexity is generally preferred to implement the sorting function.
  3. Compared to O(nlogn) quicksort and merge sort, merge sort is not an in-place sort algorithm, so the optimal choice is quicksort.

How do I optimize quicksort?

The reason why the time complexity of fast sorting is reduced to O(n) is that the partition point is not properly selected. The optimal partition point is that the two partitions separated by the partition point have the same amount of data.

Optimize the selection of partition points

How to optimize the selection of partition points? There are two common methods, as follows:

  1. Middle method of three numbers
    • Take a number from the beginning, middle and end of the interval, compare the size, and take the middle value as the partition point.
    • If the array to be sorted is large, “middle of three” may not be sufficient, and “middle of five” or “middle of ten” may be used.
  2. Random method: Each time from the range to be sorted, randomly select one element as partition point.

Beware of stack overflow for fast – sorted recursion

In addition, there are two solutions to avoid stack overflow in fast-sorted recursion, as follows:

  1. Limit the recursion depth, stopping recursion once the recursion exceeds a set threshold.
  2. Simulate the implementation of a function call stack on the heap, manually simulate the process of recursively pushing and unloading the stack, so that there is no limit to the size of the system stack.

General sorting function implementation techniques

  1. O(n^2) sorting does not necessarily take longer than O(nlogn) sorting for small amounts of data.
  2. Optimize the selection of fast row partition points when the amount of data is large
  3. To prevent stack overflow, you can choose to manually simulate call stack resolution on the heap
  4. In the sort interval, O(n^2) level insertion sort can be considered when the number of elements is less than a constant
  5. Simplify the code with sentinels, reducing one judgment per sort and optimizing performance as much as possible