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

This article will explain in detail how to use Python to achieve sorting algorithm, the editor thinks it is very practical, so share it for you to do a reference, I hope you can get something after reading this article.

Preface

Eight sorting, three major search is the "data structure" in the very basic knowledge points, here in order to review the eight common sorting algorithms.

There are eight common sorting algorithms, and the relationship between them is as follows:

Their performance comparison:

Next, use Python to implement them respectively.

Directly insert sort

Algorithm idea:

The core idea of direct insertion sorting is to compare all the elements in the array with the previously arranged elements, and if the selected element is smaller than the sorted element, swap until all elements have been compared.

Therefore, from the above description, we can see that direct insertion sorting can be done with two loops:

* layer loop: traverses all array elements to be compared

The second layer loop: compare the elements selected in this round (selected) with the elements already sorted (ordered). If: selected > ordered, swap the two

Code implementation

Hill ranking

Algorithm idea:

Hill sorting algorithm idea: the array to be sorted is grouped according to the step size gap, and then the elements of each group are sorted by the method of direct insertion sorting; each time the gap is reduced by half to cycle the above operations; when gap=1, the use of direct insertion to complete sorting.

The same: from the above description, we can see that the overall implementation of Hill ordering should be done by three loops:

* layer loop: halve the gap in turn and group the sequences until gap=1

The second and third-tier loops: that is, the two loops needed to insert the sort directly. For a specific description, see above.

Code implementation:

Simple selection sort

Algorithm thought

The basic idea of simple selection sorting: compare + exchange.

Find the element with the lowest keyword from the sequence to be sorted

If the smallest element is not * elements of the sequence to be sorted, swap it with * elements

From the remaining N-1 elements, find the element with the lowest keyword, and repeat steps (1) and (2) until the sorting is over.

So we can find that simple selection sorting is also achieved through a two-layer loop.

* layer loop: iterate through each element in the sequence in turn

The second layer loop: the traversal of the current element is compared with the remaining elements in turn, in line with the conditions of the smallest element, then swap.

Code implementation

Heap sort

The concept of heap

Heap: essentially an array object. A particularly important property: any leaf node is less than (or greater than) all of its parent nodes. In this regard, it is divided into the big top pile and the small top heap, the big top pile requires that the elements of the node are larger than their children, and the small top pile requires that the node elements are smaller than their left and right children, and the two do not make any requirements on the size relationship between the left and right children.

Using heap sorting is a sorting method based on large or small top heap. Next, we do this through the big top pile.

Basic ideas:

Heap sorting can be done by following these steps:

First of all, the sequence construction is called the big top heap.

(this satisfies the property of the large top heap: the element at the root node must be the * value of the current sequence)

Take out the root node of the current large top heap and exchange it with the elements at the end of the sequence

(at this point: the elements at the end of the sequence are sorted * values; because the elements are exchanged, the heap currently at the root node does not necessarily satisfy the properties of a large top heap)

One sequence element after exchange is adjusted to meet the properties of the large top stack.

Repeat step 2.3 until there is only 1 element in the heap

Code implementation:

Bubbling sort

Basic thought

The idea of bubble sorting is relatively simple:

Compare the left and right elements in the sequence in turn to ensure that the elements on the right are always larger than those on the left.

(after the * round ends, the sequence * an element must be the * value of the current sequence;)

Execute step 1 again for the remaining nmi 1 element in the sequence.

For sequences of length n, a total of 1 round of nmure comparisons need to be performed

(using while loops can reduce the number of execution times)

* Code implementation

Quick sort

Algorithm idea:

The basic idea of quick sorting: digging and filling numbers + divide and conquer method

Select a base number from the sequence (pivot)

Here we choose the most benchmark number in the sequence.

Traverse all the numbers in the sequence in turn, and those larger than the datum are on the right, and those smaller than the datum are on the left.

Repeat step 1.2 until there is only one element in all subsets.

Describe it in pseudo code as follows:

1.I = L; j = R; dig out the datum to form a pit a [I].

2.j-find a number smaller than it from back to front, dig it out and fill in the previous pit a [I].

3. Find a number larger than it from front to back, and dig out this number to fill in the previous pit a [j] after finding it.

4. Repeat the second step 2 and 3 until the datum is filled in a [I]

Code implementation:

Merge and sort

Algorithm idea:

Merge sorting is an effective sorting algorithm based on merge operation, which is a typical application of divide-and-conquer method. Its basic operation is to merge the existing subsequences to achieve a completely ordered sequence, that is, to make each subsequence ordered first, and then to make the subsequence segments ordered.

Merge sorting actually does two things:

Decompose-split the sequence in half each time

Merge-merge the divided sequence segments in pairwise sort

Therefore, merge sorting is actually two operations, split + merge

How to merge?

L [first... Mid] is a * paragraph, L [mid+1 … Last] is the second segment, and the two ends are in order. Now we need to synthesize the two ends to L [first... Last] and also orderly.

First, compare the elements from the * * paragraph with the second paragraph, and assign the smaller elements to the temp []

Repeat the previous step. When one assignment ends, the remaining elements of another section are assigned to temp []

At this point, copy the elements in temp [] to L [], and the resulting L [first... Last] ordered

How to decompose it?

Here, we use the recursive method to first divide the sequence to be arranged into two groups of An and B, and then repeat the An and B sequences.

Grouping; until there is only one element in the group, and then we think that all the elements in the group are in order, then the grouping ends.

Code implementation

Cardinality sort

Algorithm thought

Cardinal sorting: through the values of each element in the sequence, the sorted N elements are sorted through several rounds of "allocation" and "collection".

Allocation: we take out the elements in L [I], first determine the number on each bit, and assign it to the bucket with the same serial number according to that number.

Collection: when all the elements in the sequence are assigned to the corresponding bucket, the elements in the bucket are collected sequentially to form a new sequence L []

Repeat the allocation and collection of ten and a hundred digits of the newly formed sequence L []. The sort ends until the * bits in the sequence are allocated.

According to the above display of "cardinality sorting", we can clearly see the whole process of implementation.

Code implementation

Postscript

After writing, run a time comparison:

1W data:

10w data:

From the point of view of the running results, heap sorting, merge sorting and cardinality sorting are really fast.

For the problem that the iterative depth of quick sorting exceeds, you can consider implementing quick sorting in a non-recursive way.

On "how to use Python to achieve sorting algorithm" this article is shared here, I hope the above content can be of some help to you, so that you can learn more knowledge, if you think the article is good, please share it out for more people to see.

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.