Network Security Internet Technology Development Database Servers Mobile Phone Android Software Apple Software Computer Software News IT Information

In addition to Weibo, there is also WeChat

Please pay attention

WeChat public account

Shulou

What are the knowledge points of Python algorithm series?

2025-01-21 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Development >

Share

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

This article mainly explains the "Python algorithm series of knowledge points", the article explains the content is simple and clear, easy to learn and understand, the following please follow the editor's ideas slowly in depth, together to study and learn "what are the Python algorithm series knowledge points" bar!

Main ideas

Divide-and-conquer algorithm, that is, divide and conquer: divide a complex problem into two or more identical or similar sub-problems, until the final sub-problem can be solved directly, and finally merge the solution of the sub-problem into the solution of the original problem.

Merge sorting is a typical divide-and-conquer algorithm.

Three steps

Like stuffing an elephant into a refrigerator, the divide-and-conquer algorithm can follow three steps: decompose-> solve-> merge.

1. Decomposition: decompose the original problem into subproblems with the same structure (that is, looking for subproblems)

two。 Solution: when decomposed to a boundary that is easy to solve, recursively solve the problem.

3. Merge: merge the solution of a subproblem into the solution of the original problem.

Does that still seem a little abstract? Then we experience the core idea of the divide-and-conquer algorithm by merging and sorting the classical sorting algorithm.

Merge and sort

Thought

The idea of merging and sorting is that in order to make the sequence orderly, the subsequence must be ordered first. That is, each subsequence is ordered first, and then the subsequence is merged into an ordered list.

Therefore, the sub-problem in merge sorting is to make the subsequences in order.

Three steps

Now that we have found the sub-problem of the problem, it is time to apply our above three-step approach. The "three steps" for merging are as follows:

1. Decompose: divide a sequence into two parts

two。 Solution: recursively merge and sort the two subsequences respectively

3. Merge: two subsequences after merging and sorting

Give an example

Let's look at a specific example.

There is now a sequence to sort:

10, 4, 6, 3, 8, 2, 5, 7

First decompose the sequence and split the sequence in two until it cannot be split. The whole split process is as follows:

Then sort and merge the decomposed sequence in pairs:

10, 4 sort merged: 4, 10

6, 3 sort merged: 3, 6

8, 2 sort merged: 2, 8

Sort 5, 7 after merging: 5, 7

……

The complete process of merging and sorting is as follows:

Realize

Def merge_sort (lst): # returns a sequence of length 1 if len (lst) from recursion

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.

Views: 228

*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.

Share To

Development

Wechat

© 2024 shulou.com SLNews company. All rights reserved.

12
Report