Implement eight sorting algorithms in Python

This article uses Python to implement insertion sort, Hill sort, bubble sort, quick sort, direct selection sort, heap sort, merge sort, radix sort.

describe

The basic operation of insertion sort is to insert a data into the ordered data already sorted, so as to obtain a new, number plus one ordered data. The algorithm is suitable for sorting a small amount of data, and the time complexity is O(n^2). It’s a stable sorting method. The insertion algorithm divides the array to be sorted into two parts: the first part contains all the elements of the array but excludes the last element (the array has one more space to insert), and the second part contains only that element (the element to be inserted). After the first part is sorted, insert the last element into the sorted first part.

Code implementation

describe

Shell Sort is a type of insertion Sort. Also known as reduced incremental sort, it is a more efficient and improved version of the direct insert sort algorithm. Hill sort is an unstable sort algorithm. This method gets its name from the fact that DL. Shell proposed it in 1959. Hill sort is to group the records by a certain increment of the index and sort each group by direct insertion sort algorithm. As the increments decrease, each group contains more and more keywords, and when the increments decrease to 1, the entire file is exactly grouped and the algorithm terminates.

Code implementation

describe

It repeatedly walks through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The task of visiting an array is repeated until no more exchanges are needed, that is, the array has been sorted.

Code implementation

describe

By sorting the sorted data into two independent parts, one part of all the data is smaller than the other part of all the data, and then according to this method to the two parts of the data respectively for quick sorting, the whole sorting process can be carried out recursively, in order to achieve the entire data into an ordered sequence.

Code implementation

describe

Basic idea: in the first run, select the smallest record from the records r1 ~ R [n] to be sorted and exchange it with R1; In the second run, the smallest record is selected from the records r2 ~ R [n] to be sorted and exchanged with R2. And so on, the ith track is the record r to be sorted
Select the smallest record in ~ r[n], and compare it with rSwap, so that the ordered sequence continues to grow until all sorted.

describe

Heapsort refers to a sorting algorithm designed by using the heaptree (heap) data structure, which is a kind of selective sorting. You can take advantage of the nature of arrays to quickly locate elements of a given index. The heap is divided into large root heap and small root heap, which is a complete binary tree. A large root heap requires that the value of each node be no greater than that of its PARENT, A[PARENT
] >= A. In non-descending sorting of arrays, the large root heap is used because the largest value must be at the top of the heap.

describe

Merge sort is an effective sorting algorithm based on merge operation. It is a typical application of Divide and Conquer. The ordered subsequences are combined to obtain a fully ordered sequence. That is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are merged into one ordered table, it is called binary merge.

The merging process is as follows: Compare A
And the magnitude of a[j] if a≤a[J], then the element A in the first ordered tableCopy to r[k] and add 1 to I and k; Otherwise copy the element a[j] from the second ordered table into r[k], add j and k to 1 respectively, and so on until one of the ordered tables is finished, and then copy the remaining elements from the other ordered table into the element from subscripts k to t in R. The algorithm of merge sort is usually achieved by recursion. First, the interval [S,t] to be sorted is divided by the midpoint, then the left sub-interval is sorted, and then the right sub-interval is sorted, and finally the left and right intervals are merged into the ordered interval [s,t] by a merge operation.

describe

Radix sort belongs to “distribution sort”, also called “bucket sort” or “bin sort”, as its name implies, it allocates the sorted elements to some “buckets” through partial information of key values. Radix sort is a stable sort, whose time complexity is O (nlog(r)m), where R is the radix taken and M is the number of heaps. In some cases, radix sort is more efficient than other stability sort.

Code implementation