Shulou(Shulou.com)06/02 Report--

This article mainly introduces "what is recursion and sorting in programming". In daily operations, I believe that many people have doubts about what recursion and sorting are in programming. The editor consulted all kinds of data and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the doubts of "what are recursion and sorting respectively in programming?" Next, please follow the editor to study!

Three conditions to be satisfied by Recursive Recursion

The solution of a problem can be divided into the solution of several subproblems.

The solution of this problem is exactly the same as that of the sub-problem, except that the data scale is different.

There is a recursive termination condition

How to write recursive code

The key to writing recursive code is to find out the law of how to decompose a big problem into a small problem, and write a recursive formula based on this, and then deliberate the termination condition, and finally translate the recursive formula and termination condition into code.

As long as we encounter recursion, we abstract it into a recursive formula, do not think about layer by layer of calling relationship, do not try to use the human brain to decompose each step of recursion.

Recursive considerations

Beware of stack overflow

If the recursive call layer is deep, a stack overflow may occur; this problem can be solved by limiting the maximum depth: an error is returned directly beyond a certain depth.

Avoid double counting

Save the solved expression through a hash table; when the expression is called recursively, it is judged that it has been solved.

Sort

The most common sort: bubble sort, insert sort, select sort, merge sort, quick sort, count sort, cardinality sort, bucket sort.

How to analyze an algorithm

Execution efficiency of sorting algorithm

Best-case, worst-case, average time complexity

Coefficient, constant, low order of time complexity

Number of comparisons and times of exchange (or movement)

Memory consumption of sorting algorithm

The memory consumption of the algorithm can be measured by space complexity; in-situ sorting refers to a sorting algorithm with a space complexity of O (1).

Stability of sorting algorithm

There are elements with equal values in the sequence to be sorted. After sorting, the original order of the equal elements remains unchanged.

A stable sorting algorithm can keep the same two objects in the same order before and after sorting.

Bubbling sort

Bubble sorting only operates on two adjacent elements, compares the two adjacent elements in each operation to determine whether they meet the size relationship requirements, and swaps positions when they are not satisfied.

In terms of execution efficiency, the best-case time complexity of bubble sorting is O (n), the worst-case time complexity is O (n ^ 2), and the average case time complexity is O (n ^ 2).

In terms of memory consumption, bubble sorting only involves the exchange of adjacent elements, so the space complexity is O (1), which is an in-situ sorting algorithm.

From the stability point of view: we do not exchange when the two adjacent elements are of the same size, so the order of the two elements of the same size will not change after sorting, which is a stable sorting algorithm.

Code implementation

Public static T [] bubbleSort (T [] arrays) {for (int I = 0; I)

< arrays.length; i++) { boolean unUse = true; for (int j = 1; j < arrays.length - i; j++) { //如果前一个元素大于当前元素 就交换双方位置 if (arrays[j - 1].compareTo(arrays[j]) >

0) {T t = arrays [j-1]; arrays [j-1] = arrays [j]; arrays [j] = t; unUse = false;}} / / if there is no exchange action after the whole round, if (unUse) break;} return arrays;} insertion sorting is completed

Insert sorting divides the array into sorted and unsorted areas. the core idea is to take the elements of the unsorted area to find a suitable position to insert in the sorted area to ensure that the data of the sorted area is always orderly.

In terms of execution efficiency, the best-case time complexity of insertion sorting is O (n), the worst-case time complexity is O (n ^ 2), and the average case time complexity is O (n ^ 2).

From the memory consumption point of view: insert sorting does not need additional storage space, so the space complexity is O (1), which is an in-situ sorting algorithm.

From the perspective of stability: for elements with the same value, the latter elements are inserted behind the previous elements, so the order of the two elements will not change after sorting, which belongs to a stable sorting algorithm.

Code implementation

Public static T [] insertionSort (T [] arrays) {if (arrays.length < 2) return arrays; for (int I = 1; I < arrays.length; I +) {T t = arrays [I]; for (int j = 0; j < I; jacks +) {if (t.compareTo (arrays) < 0) {System.arraycopy (arrays, j, arrays, j + 1, I-j) Arrays [j] = t; break;} return arrays;} Select sort

Selective sorting also divides the data into sorted and unsorted areas, unlike insert sorting: each time the smallest element in the unsorted area is placed at the end of the sorted area.

In terms of execution efficiency, the best-case time complexity of insertion sorting is O (n ^ 2), the worst-case time complexity is O (n ^ 2), and the average case time complexity is also O (n ^ 2).

From the memory consumption point of view: the selection of sorting does not need additional storage space, so the space complexity is O (1), which is an in-situ sorting algorithm.

In terms of stability, when the minimum element in the unsorted area exchanges positions with the first element, the order of the two elements with the same value may be changed, so the selective sorting belongs to the unstable sorting algorithm.

Code implementation

Public static T [] selectionSort (T [] arrays) {if (arrays.length < 2) return arrays; for (int I = 0; I < arrays.length; iindex +) {int minIndex = I min / define minimum index T min = arrays [minIndex]; / / the first one by default is the minimum for (int j = I + 1; j < arrays.length) ) {if (arrays [j] .compareto (min) < 0) {minIndex = j; min = arrays [minIndex];}} / / Exchange value arrays [minIndex] = arrays [I]; arrays [I] = min;} return arrays;} Summary

We analyze three sorting algorithms with time complexity of O (n ^ 2) from three aspects of execution efficiency, memory consumption and stability.

At this point, the study of "what is recursion and sorting in programming" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.