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

This article mainly explains "what are the classic sorting algorithms of Python data structure". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn what classic sorting algorithms of Python data structure.

Catalogue

1. Bubble sorting

Algorithm demonstration

Algorithm step

Algorithm realization

2. Select sort

Algorithm demonstration

Algorithm step

Algorithm realization

3. Simple insertion sort

Algorithm demonstration

Algorithm step

Algorithm realization

4. Hill sorting

Algorithm demonstration

Algorithm step

Algorithm realization

5. Merge and sort

Algorithm demonstration

Algorithm step

Algorithm realization

6. Quick sort

Algorithm demonstration

Algorithm step

Algorithm realization

7. Heap sort

Algorithm demonstration

Algorithm step

Algorithm realization

8. Counting and sorting

Algorithm demonstration

Algorithm step

Algorithm realization

9. Bucket sorting

Algorithm demonstration

Algorithm step

Algorithm realization

10. Cardinality sort

Algorithm demonstration

Algorithm step

Algorithm realization

1. Bubble sorting

The smaller the element will slowly "float" to the top of the sequence by swapping.

Algorithm demonstration

Algorithm step

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

Do the same for each pair of adjacent elements, from the first pair to the last pair, so that the last element should be the largest number.

Repeat the above steps for all elements except the last one

Repeat steps 1-3 until the sorting is complete.

Algorithm implementation of 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, selective sorting

The youngest comes out first, and the second youngest comes out second.

Algorithm demonstration

Algorithm step

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.

Algorithm implementation 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、简单插入排序 --通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 算法演示 算法步骤 从第一个元素开始，该元素可以认为已经被排序； 取出下一个元素，在已经排序的元素序列中从后向前扫描； 如果该元素（已排序）大于新元素，将该元素移到下一位置； 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置； 将新元素插入到该位置后；重复步骤2~5。 算法实现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.

Algorithm demonstration

Algorithm step

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.

Algorithm implementation of 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

An effective sorting algorithm based on merge operations. This algorithm is a very typical application of divide-and-conquer (Divide and Conquer).

Algorithm demonstration

Algorithm step

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.

Algorithm to achieve 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.

Algorithm demonstration

Algorithm step

Set a quantitative array as an empty bucket

Traverse the input data and put the data in the corresponding bucket one by one

Sort each bucket that is not empty

Never put the sorted data together in a bucket that is not empty.

The algorithm implements function bucketSort (arr, bucketSize) {if (arr.length = 0) {return arr;} var i; var minValue = arr [0]; var maxValue = arr [0]; for (I = 1; I)

< arr.length; i++) { if (arr[i] < minValue) { minValue = arr[i]; // 输入数据的最小值 } else if (arr[i] >

MaxValue) {maxValue = arr [I]; / the maximum value of input data}} / / initialization var DEFAULT_BUCKET_SIZE of buckets = 5; / / set the default number of buckets to 5 bucketSize = bucketSize | | DEFAULT_BUCKET_SIZE; var bucketCount = Math.floor ((maxValue-minValue) / bucketSize) + 1; var buckets = new Array (bucketCount) For (I = 0; I < buckets.length; iTunes +) {buckets [I] = [];} / / use the mapping function to distribute data to each bucket for (I = 0; I < arr.length; ibasket +) {buckets [Math.floor ((arr [I]-minValue) / bucketSize)] .push (arr [I]);} arr.length = 0; for (I = 0; I < buckets.length) Var +) {insertionSort (buckets [I]); / / sort each bucket, here use insert sort for (Buckets j = 0; j < buckets [I] .length; jacks +) {arr.push (buckets [I] [j]);}} return arr;} 10, cardinality sort

The cardinality sort is sorted first by the low order, then collected, then sorted by the high order, then collected again, and so on, until the highest bit. Sometimes some attributes are in order of priority, sorted first by low priority and then by high priority. The last order is the high priority, the high priority, the same low priority, the high priority.

Algorithm demonstration

Algorithm step

Get the maximum number in the array and get the number of digits

Arr is the original array. Each bit is taken from the lowest bit to form the radix array.

Count sort the radix (using the feature that count sort is suitable for a small range of numbers)

The algorithm implements var counter = []; function radixSort (arr, maxDigit) {var mod = 10; var dev = 1; for (var I = 0; I < maxDigit; iTunes, dev * = 10, mod * = 10) {for (var j = 0; j < arr.length; jacks +) {var bucket = parseInt ((arr [j]% mod) / dev) If [bucket] = null) {counter [bucket] = [];} counter[ bucket] .push (arr [j]);} var pos = 0; for (var j = 0; j < counter.length; jacks +) {var value = null If! = null) {while ((value = counter[ j]. Shift ())! = null) {arr [pos++] = value;}} return arr } Thank you for your reading, the above is the content of "what are the classic sorting algorithms of Python data structures". After the study of this article, I believe you have a deeper understanding of what classic sorting algorithms of Python data structures have, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.