Backend Development
Python Tutorial
Introduction to the method of merging sort using python programming
Introduction to the method of merging sort using python programming
This article mainly introduces pythonProgramming to everyone in detail. The specific code to implement merge sorting has certain reference value. Interested friends can refer to it
Because of a question on leetcode last week (Median of Two Sorted Arrays), I wanted to take a closer look at the implementation of merge sort.
Let’s first explain the sorting idea:
First of all, merge sorting uses the dichotomy method. In the final analysis, the idea is to divide and conquer. Get a long array, divide it into the left and right parts continuously, and then divide it recursively. Then merge them into two ordered arrays. It may be difficult to understand in this way, so I will give you a picture I drew.
This shows the first step of merge sorting, recursively split the array according to middle, and finally divide it into the smallest details. It sorts two sorted arrays using the same method as sorting them.
Two sortedThe method of sorting arrays is very simple. Compare the first positions of the two arrays at the same time, put the smaller one into an empty array, and then put it The pointer of the position in the empty array is moved back by one, and then continues to be compared with the previous position of the other array, and so on. When the last array is popped off the stack first, all the elements in the other array will be appended to the new array.
Since the time complexity of recursive splitting is logN, however, the complexity of the method of sorting two ordered arrays is N. The time complexity of this algorithm is N*logN, so it is NlogN.
According to this wave of analysis, we can look at a behavior of the above picture.
When the leftmost one is divided into the smallest details, it can no longer be divided into the left and right parts and then starts to merge.
The first combination completes the merging of [4, 7]
The second combination completes the merging of [4, 7, 8]
The third combination completes[ The merging of 3, 5]
The fourth combination is completed The merging of [3, 5, 9]
The fifth combination is completed [3, 4, 5, 7, 8, 9] The merge ends sorting.
Put the python code below
def merge(a, b): c = [] h = j = 0 while j < len(a) and h < len(b): if a[j] < b[h]: c.append(a[j]) j += 1 else: c.append(b[h]) h += 1 if j == len(a): for i in b[h:]: c.append(i) else: for i in a[j:]: c.append(i) return c def merge_sort(lists): if len(lists) <= 1: return lists middle = len(lists)/2 left = merge_sort(lists[:middle]) right = merge_sort(lists[middle:]) return merge(left, right) if name == 'main': a = [4, 7, 8, 3, 5, 9] print merge_sort(a)
The above is the detailed content of Introduction to the method of merging sort using python programming. For more information, please follow other related articles on the PHP Chinese website!
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
1665
14
1424
52
1322
25
1270
29
1250
24
PHP and Python: Different Paradigms Explained
Apr 18, 2025 am 12:26 AM
PHP is mainly procedural programming, but also supports object-oriented programming (OOP); Python supports a variety of paradigms, including OOP, functional and procedural programming. PHP is suitable for web development, and Python is suitable for a variety of applications such as data analysis and machine learning.
Choosing Between PHP and Python: A Guide
Apr 18, 2025 am 12:24 AM
PHP is suitable for web development and rapid prototyping, and Python is suitable for data science and machine learning. 1.PHP is used for dynamic web development, with simple syntax and suitable for rapid development. 2. Python has concise syntax, is suitable for multiple fields, and has a strong library ecosystem.
How to run sublime code python
Apr 16, 2025 am 08:48 AM
To run Python code in Sublime Text, you need to install the Python plug-in first, then create a .py file and write the code, and finally press Ctrl B to run the code, and the output will be displayed in the console.
Python vs. JavaScript: The Learning Curve and Ease of Use
Apr 16, 2025 am 12:12 AM
Python is more suitable for beginners, with a smooth learning curve and concise syntax; JavaScript is suitable for front-end development, with a steep learning curve and flexible syntax. 1. Python syntax is intuitive and suitable for data science and back-end development. 2. JavaScript is flexible and widely used in front-end and server-side programming.
PHP and Python: A Deep Dive into Their History
Apr 18, 2025 am 12:25 AM
PHP originated in 1994 and was developed by RasmusLerdorf. It was originally used to track website visitors and gradually evolved into a server-side scripting language and was widely used in web development. Python was developed by Guidovan Rossum in the late 1980s and was first released in 1991. It emphasizes code readability and simplicity, and is suitable for scientific computing, data analysis and other fields.
Golang vs. Python: Performance and Scalability
Apr 19, 2025 am 12:18 AM
Golang is better than Python in terms of performance and scalability. 1) Golang's compilation-type characteristics and efficient concurrency model make it perform well in high concurrency scenarios. 2) Python, as an interpreted language, executes slowly, but can optimize performance through tools such as Cython.
Where to write code in vscode
Apr 15, 2025 pm 09:54 PM
Writing code in Visual Studio Code (VSCode) is simple and easy to use. Just install VSCode, create a project, select a language, create a file, write code, save and run it. The advantages of VSCode include cross-platform, free and open source, powerful features, rich extensions, and lightweight and fast.
How to run python with notepad
Apr 16, 2025 pm 07:33 PM
Running Python code in Notepad requires the Python executable and NppExec plug-in to be installed. After installing Python and adding PATH to it, configure the command "python" and the parameter "{CURRENT_DIRECTORY}{FILE_NAME}" in the NppExec plug-in to run Python code in Notepad through the shortcut key "F6".
