转载: 算法基础:五大排序算法

标题
A tour of the top 5 sorting algorithms with Pythoncode
算法基础:五大排序算法Python实战教程
01

Sorting algorithms complexities’
Sorting is a skill that every software engineer and developer needs some knowledge of. Not only to pass coding interviews but as a general understanding of programming itself. The different sorting algorithms are a perfect showcase of how algorithm design can have such a strong effect on program complexity, speed, and efficiency.
Let’s take a tour of the top 6 sorting algorithms and see how we can implement them in Python!

Bubble Sort

Bubble sort is the one usually taught in introductory CS classes since it clearly demonstrates how sort works while being simple and easy to understand. Bubble sort steps through the list and compares adjacent pairs of elements. The elements are swapped if they are in the wrong order. The pass through the unsorted portion of the list is repeated until the list is sorted. Because Bubble sort repeatedly passes through the unsorted part of the list, it has a worst case complexity of O(n²).

Unknown media: image/gif


排序算法的复杂度
排序是每个软件工程师和开发人员都需要掌握的技能。不仅要通过编程面试,还要对程序本身有一个全面的理解。不同的排序算法很好地展示了算法设计上如何强烈的影响程序的复杂度、运行速度和效率。

让我们看一下前6种排序算法,看看如何在Python中实现它们!

冒泡排序
冒泡排序通常是在CS入门课程中教的,因为它清楚地演示了排序是如何工作的,同时又简单易懂。冒泡排序步骤遍历列表并比较相邻的元素对。如果元素顺序错误,则交换它们。重复遍历列表未排序部分的元素,直到完成列表排序。因为冒泡排序重复地通过列表的未排序部分,所以它具有最坏的情况复杂度O(n^2)。
Unknown media: image/gif

02

Selection Sort

Selection sort is also quite simple but frequently outperforms bubble sort. If you are choosing between the two, it’s best to just default right to selection sort. With Selection sort, we divide our input list / array into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted that make up the rest of the list. We first find the smallest element in theunsorted sublistand place it at the end of thesorted sublist.Thus,we are continuously grabbing the smallest unsorted element and placing it in sorted orderin thesorted sublist.This process continues iteratively until the list is fully sorted.
Unknown media: image/gif

Insertion Sort

Insertion sort is both faster and well-arguably more simplistic than both bubble sort and selection sort. Funny enough, it’s how many people sort their cards when playing a card game! On each loop iteration, insertion sort removes one element from the array. It then finds the location where that element belongs within anothersortedarray and inserts it there. It repeats this process until no input elements remain.、
Unknown media: image/gif

选择排序
选择排序也很简单,但常常优于冒泡排序。如果您在这两者之间进行选择,最好默认选择排序。通过选择排序,我们将输入列表/数组分为两部分:已经排序的子列表和剩余要排序的子列表,它们构成了列表的其余部分。我们首先在未排序的子列表中找到最小的元素,并将其放置在排序的子列表的末尾。因此,我们不断地获取最小的未排序元素,并将其按排序顺序放置在排序的子列表中。此过程将重复进行,直到列表完全排序。

Unknown media: image/gif

插入排序
插入排序比冒泡排序和选择排序既快又简单。有趣的是,有多少人在玩纸牌游戏时会整理自己的牌!在每个循环迭代中,插入排序从数组中删除一个元素。然后,它在另一个排序数组中找到该元素所属的位置,并将其插入其中。它重复这个过程,直到没有输入元素。

Unknown media: image/gif

03

Merge Sort

Merge sort is a perfectly elegant example of a Divide and Conquer algorithm. It simple uses the 2 main steps of such an algorithm:
(1) Continuouslydividethe unsorted list until you haveNsublists, where each sublist has 1 element that is “unsorted” andNis the number of elements in the original array.
(2) Repeatedlymergei.econquerthe sublists together 2 at a time to produce new sorted sublists until all elements have been fully merged into a single sorted array.

Unknown media: image/gif

Quick Sort

Quick sort is also a divide and conquer algorithm like merge sort. Although it’s a bit more complicated, in most standard implementations it performs significantly faster than merge sort and rarely reaches its worst case complexity of O(n²). It has 3 main steps:
(1) We first select an element which we will call thepivotfrom the array.
(2)Move all elements that are smaller than the pivot to the left of the pivot; move all elements that are larger than the pivot to the right of the pivot. This is called the partition operation.
(3) Recursively apply the above 2 steps separately to each of the sub-arrays of elements with smaller and bigger values than the last pivot.
Unknown media: image/gif

Like tolearn?
Follow me ontwitterwhere I post all about the latest and greatest AI, Technology, and Science!


归并排序

归并排序是分而治之算法的完美例子。它简单地使用了这种算法的两个主要步骤:
(1)连续划分未排序列表,直到有N个子列表,其中每个子列表有1个“未排序”元素,N是原始数组中的元素数。
(2)重复合并,即一次将两个子列表合并在一起,生成新的排序子列表,直到所有元素完全合并到一个排序数组中。


Unknown media: image/gif

快速排序

快速排序也是一种分而治之的算法,如归并排序。虽然它有点复杂,但在大多数标准实现中,它的执行速度明显快于归并排序,并且很少达到最坏情况下的复杂度O(n²)。它有三个主要步骤:
(1)我们首先选择一个元素,称为数组的基准元素(pivot)。
(2)将所有小于基准元素的元素移动到基准元素的左侧;将所有大于基准元素的元素移动到基准元素的右侧。这称为分区操作。
(3)递归地将上述两个步骤分别应用于比上一个基准元素值更小和更大的元素的每个子数组。

Unknown media: image/gif

喜欢吗?

Twitter上关注我,在那里我发布了最新最伟大的人工智能、技术和科学!



作者:

标签:

创建时间: 2019-01-05 09:54 最后更新时间:2019-01-14 17:43

苏ICP备15039362号 © 2015 纸喵软件 EverNote