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

Most people do not understand the knowledge points of this article "Python how to achieve the Ten Classic sorting algorithms", so the editor summarizes the following contents, detailed content, clear steps, and has a certain reference value. I hope you can get something after reading this article. Let's take a look at this "how to achieve the Ten Classical sorting algorithms in Python" article.

Sorting algorithm is one of the most basic algorithms in "data structure and algorithm", and it is also a necessary question in the interview. In order to facilitate technical exchange, a technical exchange group is established at the end of this paper.

The sorting algorithm can be divided into internal sorting and external sorting. The internal sorting is that the data records are sorted in memory, while the external sorting is because the sorted data is so large that it can not accommodate all the sorted records at one time. Access to external memory is needed in the sorting process. Common internal sorting algorithms are: insert sort, Hill sort, select sort, bubble sort, merge sort, quick sort, heap sort, cardinality sort and so on. Summarize it with a picture:

About time complexity

Square order (O (N2)) sort all kinds of simple sort: direct insertion, direct selection and bubbling sort.

Linear logarithmic order (O (nlog2n)) sort Quick sort, heap sort, and merge sort

O (N1 + §), which is a constant between 0 and 1. Hill ranking

Linear order (O (n)) sort cardinal sort, in addition, there are bucket and box sorting.

About stability

The order of the two equal keys after sorting is the same as that before sorting.

Stable sorting algorithms: bubble sort, insert sort, merge sort and cardinality sort.

Is not a stable sorting algorithm: select sort, quick sort, Hill sort, heap sort.

Noun interpretation

N: data scale

K: number of buckets

In-place: occupies constant memory, not extra memory

Out-place: takes up extra memory

1. Bubble sorting

Bubble sorting (Bubble Sort) is also a simple and intuitive sorting algorithm. It repeatedly visits the sequence to be sorted, compares two elements at a time, and swaps them if they are in the wrong order. The work of visiting the sequence is repeated until there is no need for swapping, that is, the sequence has been sorted. The algorithm gets its name because smaller elements slowly "float" to the top of the sequence by swapping.

As one of the simplest sorting algorithms, Bubble sorting makes me feel like Abandon in a word book, always at the top of the first page, so I'm most familiar with it. Another optimization algorithm for bubble sorting is to set up a flag. When elements are not exchanged in a sequence traversal, it is proved that the sequence has been ordered. But this improvement does not do much to improve performance.

(1) algorithm steps

Compare adjacent elements. If the first is bigger than the second, exchange the two of them.

Do the same for each pair of adjacent elements, from the first pair to the last pair. After this step is done, the last element will be the maximum number.

Repeat the above steps for all elements except the last one.

Continue to repeat the above steps for fewer and fewer elements each time until there are no pairs of numbers to compare.

(2) moving picture demonstration

(3) Python code def bubbleSort (arr): for i in range (1, len (arr)): for j in range (0, len (arr)-I): if arr [j] > arr [juni1]: arr [j], arr [juni1] = arr [juni1], arr [j] return arr2, select sort

Selective sorting is a simple and intuitive sorting algorithm, no matter what data is entered, it is O (n ²) time complexity. So when using it, the smaller the data, the better. The only benefit may be that it doesn't take up extra memory space.

(1) algorithm steps

First, find the smallest (largest) element in the unsorted sequence and store it at the beginning of the sorted sequence.

Continue to look for the smallest (largest) element from the remaining unsorted elements, and then put it at the end of the sorted sequence.

Repeat the second step until all the elements are sorted.

(2) moving picture demonstration

(3) Python code def selectionSort (arr): for i in range (len (arr)-1): # Index of record minimum minIndex = i for j in range (I + 1, len (arr)): if arr [j]

< arr[minIndex]: minIndex = j # i 不是最小数时，将 i 和最小数进行交换 if i != minIndex: arr[i], arr[minIndex] = arr[minIndex], arr[i] return arr3、插入排序 插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。 （1）算法步骤 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。） （2）动图演示 （3）Python 代码def insertionSort(arr): for i in range(len(arr)): preIndex = i-1 current = arr[i] while preIndex >

= 0 and arr [preIndex] > current: arr [preIndex+1] = arr [preIndex] preIndex-=1 arr [preIndex+1] = current return arr4, Hill sort

Hill sorting, also known as decreasing incremental sorting algorithm, is a more efficient and improved version of insert sorting. But Hill sorting is an unstable sorting algorithm.

Hill sorting is an improved method based on the following two properties of insertion sorting:

Insertion sorting is efficient when operating on almost sorted data, that is, it can achieve the efficiency of linear sorting.

But insert sorting is generally inefficient because it can only move data one bit at a time.

The basic idea of Hill sorting is that the whole sequence of records to be sorted is divided into several sub-sequences for direct insertion and sorting, and then all the records are directly inserted and sorted when the records in the whole sequence are "basically ordered".

(1) algorithm steps

Select an incremental sequence T1 and T2,. , tk, where ti > tj, tk = 1

Sort the sequence k times according to the number of incremental sequences k

In each sorting, according to the corresponding incremental ti, the sequence to be arranged is divided into several subsequences of length m, and each subtable is sorted directly. Only when the increment factor is 1, the whole sequence is treated as a table, and the table length is the length of the whole sequence.

(2) Python code def shellSort (arr): import math gap=1 while (gap)

< len(arr)/3): gap = gap*3+1 while gap >

0: for i in range (gap,len (arr)): temp = arr [I] j = i-gap while j > = 0 and arr [j] > temp: arr [j+gap] = ARR [j] j-=gap arr [j+gap] = temp gap = math.floor (gap/3) return arr5, merge sort

Merge sorting (Merge sort) is an effective sorting algorithm based on merge operation. This algorithm is a very typical application of divide-and-conquer (Divide and Conquer).

As a typical algorithm application of divide-and-conquer idea, merge sorting is realized by two methods:

Top-down recursion (all recursive methods can be iteratively rewritten, so there is a second method)

Bottom-up iteration

Like selective sorting, the performance of merge sorting is not affected by the input data, but it performs much better than selective sorting, because it is always O (nlogn) time complexity. The cost is that extra memory space is required.

(1) algorithm steps

Apply for space so that it is the sum of two sorted sequences, which is used to store the merged sequence

Set two pointers, initially at the start of the two sorted sequences

Compare the elements pointed to by the two pointers, select the relatively small elements to put into the merge space, and move the pointer to the next location

Repeat step 3 until a pointer reaches the end of the sequence

Copy all the remaining elements of another sequence directly to the end of the merge sequence.

(2) moving picture demonstration

(3) Python code def mergeSort (arr): import math if (len (arr) 0: arr [sortedIndex] = j sortedIndex+=1 bucket [j]-= 1 return arr9, bucket sort

Bucket sort is an updated version of count sort. It makes use of the mapping relationship of the function, and whether it is efficient or not lies in the determination of the mapping function. To make bucket sorting more efficient, we need to do these two things:

Increase the number of buckets as much as possible when the extra space is sufficient.

The mapping function used can evenly distribute the N input data to K buckets.

At the same time, for the sorting of elements in the bucket, the choice of comparison sorting algorithm is very important to the performance.

When is the fastest time?

When the input data can be evenly distributed to each bucket.

When is the slowest?

When the input data is assigned to the same bucket.

Python code def bucket_sort (s): "" bucket sort "" min_num = min (s) max_num = max (s) # barrel size bucket_range = (max_num-min_num) / len (s) # barrel array count_list = [[] for i in range (len (s) + 1)] # fill the bucket array with for i in s: Count_list [int ((i-min_num) / / bucket_range)] .append (I) s.clear () # backfill Here the sorting inside the bucket directly calls sorted for i in count_list: for j in sorted (I): s.append (j) if _ _ name__ = = _ _ main__: a = [3.2 print 6, 8, 4, 2, 7, 3] bucket_sort (a) print (a) # [2, 3, 3.2, 4, 6, 6, 7, 8] 10, cardinal sort

Cardinal sorting is a non-comparative integer sorting algorithm, its principle is to cut integers into different digits, and then compare them according to each digit. Because integers can also represent strings (such as names or dates) and floating-point numbers in a specific format, cardinality sorting is not limited to integers.

Cardinal sort vs count sort vs bucket sort

There are two ways to sort cardinality:

All three sorting algorithms make use of the concept of bucket, but there are significant differences in the use of buckets:

Cardinality sort: assign buckets according to each number of key values

Count sort: only a single key value is stored in each bucket

Bucket sorting: each bucket stores a certain range of values

Moving picture demonstration

Python code def RadixSort (list): I = 0 # initially sort for individual bits n = 1 # the minimum number of digits is set to 1 (including 0) max_num = max (list) # to get the maximum number while max_num > 10 in the sorted array Several digits n + = 1 while I < n: bucket = {} # build bucket for x in range (10): bucket.setdefault (x) with dictionary []) # empty each bucket for x in list: # sort each bit radix = int ((x / (10 radii))% 10) # to get each cardinality bucket[ radix] .append (x) # add the corresponding array elements to the bucket corresponding to the # cardinality j = 0 for k in range (10): If len (Bucket [k])! = 0: # if the bucket is not empty for y in bucket [k]: # put each element in the bucket list [j] = y # back into the array j + = 1i + = 1return list is the content of the article "how to implement the Ten Classical sorting algorithms in Python" I believe we all have a certain understanding. I hope the content shared by the editor will be helpful to you. If you want to know more about the relevant knowledge, please pay attention to the industry information channel.

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.