• Reference data: https://www.bilibili.com/video/BV1mp4y1D7UP
  • This GIF demo source: https://visualgo.net/
    • *

Sorting algorithm classification

  • Internal sort: refers to the sort in which all the elements are stored in memory during the sort period. Common internal sort algorithms include bubble sort, selection sort, insertion sort, hill sort, merge sort, quicksort, heap sort, radix sort and so on.
  • External sort: refers to the sort in which elements cannot be stored in memory completely at the same time during sorting, and must be constantly moved between internal and external storage according to requirements during sorting;
  • Comparison class sorting: The relative order of elements is determined by comparison. Because its time complexity cannot exceed O(nlogn), it is also called nonlinear time comparison class sorting.
  • Non-comparison sort: It does not use comparison to determine the relative order of elements. It can break the lower time limit based on comparison sort and run in linear time. Therefore, it is also called linear time non-comparison sort. Common non – comparison sort algorithms are: radix sort, counting sort, bucket sort and so on

In general, the internal sorting algorithm will carry out two operations during the execution: comparison and movement. Determine the context of the corresponding elements by comparing the sizes of two keywords, and then move the elements around to achieve order. However, not all internal sorting algorithms need to be based on comparison operations.

Each sorting algorithm has its own advantages and disadvantages, suitable for use in different environments, in terms of its overall performance, it is difficult to come up with a single algorithm that is considered to be the best. Generally, sorting algorithms can be divided into five categories: insertion sort, swap sort, selection sort, merge sort and radix sort. The performance of internal sorting algorithms depends on the time complexity and space complexity of the algorithm, and the time complexity is generally determined by The Times of comparison and movement.

Sorting algorithm Time complexity (average) Time complexity (best) Time complexity (worst) Spatial complexity The stability of
Bubble sort $$ O(n^2) $$ $$ O(n) $$ $$ O(n^2) $$ $$ O(1) $$ stable
Selection sort $$ O(n^2) $$ $$ O(n^2) $$ $$ O(n^2) $$ $$ O(1) $$ unstable
Insertion sort $$ O(n^2) $$ $$ O(n) $$ $$ O(n^2) $$ $$ O(1) $$ stable
Hill sorting $$ O(nlogn) $$ $$ O(nlog^2n) $$ $$ O(nlog^2n) $$ $$ O(1) $$ unstable
Merge sort $$ O(nlogn) $$ $$ O(nlogn) $$ $$ O(nlogn) $$ $$ O(n) $$ stable
Quick sort $$ O(nlogn) $$ $$ O(nlogn) $$ $$ O(n^2) $$ $$ O(logn) $$ unstable
Heap sort $$ O(nlogn) $$ $$ O(nlogn) $$ $$ O(nlogn) $$ $$ O(1) $$ unstable
Count sorting $$ O(n+k) $$ $$ O(n+k) $$ $$ O(n+k) $$ $$ O(k) $$ stable
Bucket sort $$ O(n+k) $$ $$ O(n+k) $$ $$ O(n^2) $$ $$ O(n+k) $$ stable
Radix sort $$ O(n\*k) $$ $$ O(n\*k) $$ $$ O(n\*k) $$ $$ O(n+k) $$ stable

Stability: the order of the two equal keys after sorting and whether they are in the same order before sorting. Example: If A was originally in front of B, and A = B, then A is still in front of B after sorting, then it is stable.

Common time complexity size comparison:

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<… <O(2n)<O(n!) O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) <… < O(2^n)<O (n!) O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<… <O(2n)<O(n!)

1. Bubble Sort

1, the principle of

Repeatedly go through the elements to be sorted, comparing two adjacent elements one by one, and swapping them if the order (e.g., from large to small) is wrong. The task of visiting elements is repeated until no adjacent elements need to be swapped, which means that the element column has been sorted. And what it means by bubbling is that each time it bubbles the largest element will move to the right by constantly comparing and swapping neighboring elements.

Let’s say there are 10 children standing in a row from left to right, of different heights. The teacher wanted them to stand up according to their height, so he began to shout slogans. Every call, from the beginning of the first child, the adjacent two children if the height is not positive sequence would change, so the height of the highest ranked in the first round at the far right (bubble to the right), the second round so in turn to, from the first two children exchange, so 2 children is the penultimate position. And so on.

2, steps,

  • ① Compare adjacent elements. If the first one is bigger than the second, you swap them both;
  • ② Do the same for each pair of adjacent elements, starting from the first pair to the last pair at the end, so that the last element should be the largest number;
  • ③ Repeat steps ① ~ ② for all elements except the last element until the sorting is complete.

3. Animation demonstration

4. Code implementation

Def bubbleSort(arr): for j in range(len(arr)-i-1): for j in range(len(arr)-i-1): for j in range(len(arr)-i-1): Arr [j], arr[j+1] = arr[j+1], arr[j] return arr

Bubble Sort has another optimization algorithm, which is to set a flag. When there is no exchange of elements in a sequence traversal, it is proved that the sequence has been ordered, and subsequent sorting will not be carried out. The animation demo is the improved algorithm, the improved code is as follows:

Def bubbleSort(arr): for I in range(len(arr)-1): Arr [j], arr[j+1] = arr[j+1], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j] flag = True if not: return return arr

Bubble Sort is the fastest case: when the input data is positive order; Slowest case: when the input data is in reverse order.

5. Specific examples

Unimproved version:

Def bubble_sort(arr): for j in range(len(arr)-i-1): for j in range(len(arr)-i-1): for j in range(len(arr)-i-1): Arr [j], arr[j+1] = arr[j+1], arr[j] print(arr = [3, 44, 38, 5, 47, 15, 36) print(arr = [3, 44, 38, 5, 47, 15, 36) 26, 27, 2, 46, 4, 19, 50, 48] bubble_sort(arr) `````` [3, 38, 5, 44, 15, 36, 26, 27, 2, 46, 4, 19, 47, 48, 50] [3, 5, 38, 15, 36, 26, 27, 2, 44, 4, 19, 46, 47, 48, 50 [3, 5, 15, 26, 2, 27, 4, 19, 36, 38, 44, 46, 47, 48, 50] 3, 5, 2, 15, 4, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] [4, 5, 15, 19, 26] [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] 36, 38, 44, 46, 47, 48, 50]

Improved version:

Def bubble_sort(arr): for j in range(len(arr)-1): Arr [j], arr[j+1] = arr[j+1], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j], arr[j] flag = True if not: Return print(arr) # arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48] bubble_sort(arr) `````` [3, 38, 5, 44, 15, 36, 26, 27, 2, 46, 4, 19, 47, 48, 50] [3, 5, 38, 15, 36, 26, 27, 2, 44, 3, 5, 15, 26, 27, 2, 38, 4, 19, 44, 46, 47, 48, 50 [3, 5, 15, 2, 26, 4, 46, 47, 48, 50] [3, 5, 15, 2, 26, 4, 19, 27, 36, 38, 44] 3, 2, 5, 4, 15, 19, 38, 44, 46, 47, 48, 50 [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

(1) Selection Sort

1, the principle of

For the first time, select the smallest (or largest) element from the data elements to be sorted, store it at the beginning of the sequence, and then find the smallest (or largest) element from the remaining unsorted elements, and then put it at the end of the sorted sequence. And so on, until the total number of data elements to be sorted is zero. Think of it as an iteration from 0 to n-1, looking back each time to select the smallest element. Selection sort is an unstable sort method.

Let’s say there are 10 children standing in a row from left to right, of different heights. The teacher wants them to stand from the lowest to the highest, so we start from the first one, find the smallest child from the beginning to the end, and then switch it with the first child. Then follow the same strategy from the second child, and the circle will be orderly.

2, steps,

  • ① First, find the smallest (largest) element in the unsorted sequence and store it in the starting position of the sorted sequence;
  • (2) Then continue to find the smallest (largest) element from the remaining unsorted elements, and then put it at the end of the sorted sequence;
  • ③ Repeat step ② until all elements are sorted.

3. Animation demonstration

4. Code implementation

Python code:

Def selection_sort(arr): for j in range(I +1, len(arr)-1): If arr[j] < arr[min_index]: # If this number is less than the minimum recorded number, Min_index = j arr[I], arr[I] = arr[min_index], arr[I] = arr[min_index

5. Specific examples

Def selection_sort(arr): for j in range(I +1, len(arr)-1): If arr[j] < arr[min_index]: # If this number is less than the minimum recorded number, Min_index = j arr[I], arr[min_index] = arr[min_index], Print (arr) # arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19 50, 48] selection_sort(arr) `````` [2, 44, 38, 5, 47, 15, 36, 26, 27, 3, 46, 4, 19, 50, 48] [2, 3, 38, 5, 47, 15, 36, 2, 3, 4, 5, 47, 15, 36, 26, 27, 44, 46, 38, 19, 50, 48 2, 3, 4, 5, 15, 47, 36, 26, 27, 44, 46, 38, 19, 50, 48 [2, 3, 4, 5, 15, 19, 26, 36, 27, 46, 38, 47, 50, 48] [3, 4, 5, 15, 19, 26, 27, 36, 44] [2, 3, 4, 5, 15, 19, 26, 27, 36, 44, 46, 38, 47, 50, 48] [2, 3, 4, 5, 15, 38, 44, 46, 50, 48] [3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 2, 3, 4, 5, 15, 19, 38, 44, 46, 47, 50, 48 48, 50]

Insertion Sort

1, the principle of

Insertion sort is also commonly referred to as direct insertion sort. It is an efficient algorithm for sorting a small number of elements. The basic idea is to form a new ordered table by inserting a record into an already ordered table. In its implementation process, the outer loop traverses all elements except the first element, and the inner loop searches the ordered table in front of the current element to be inserted and moves it.

Insertion sort works like many people sort a hand of cards. To start with, our left hand is empty and the cards on the table face down. Then, we take one card at a time from the table and insert it into the correct position in our left hand. To find the correct position of a card, we compare it from right to left with each card that is already in our hand. The cards held in the left hand are always sorted, which turns out to be the cards at the top of the pile on the table.

2, steps,

  • ① Start with the first element, which can be considered to have been sorted;
  • ② Take out the next element and scan from back to front in the sorted element sequence;
  • ③ If the sorted element is greater than the new element, move the element to the next position to the right and repeat the process until the sorted element is found to be less than or equal to the new element.
  • ④ Insert the new element after the position found in step ③;
  • ⑤ Repeat steps ② ~ ④.

3. Animation demonstration

4. Code implementation

def insertion_sort(arr): for i in range(1, len(arr)): While j >= 0 and arr[j] >= 0 and arr[j] > TMP = arr[I] Arr [j+1] = Arr [j] # Move the card in your hand one position to the right (Assigns the card in your hand to the next position) j -= 1 # Decrease the subscript of the card in your hand by 1, Arr [j+1] = TMP # insert the card into j+1 return arr

5. Specific examples

def insertion_sort(arr): for i in range(1, len(arr)): While j >= 0 and arr[j] >= 0 and arr[j] > TMP = arr[I] Arr [j+1] = Arr [j] # Move the card in your hand one position to the right (Assigns the card in your hand to the next position) j -= 1 # Decrease the subscript of the card in your hand by 1, Print (arr) # print(arr) # print(arr) # print(arr) # print(arr) = [0, 9, 8, 7, 1, 2, 3, 4, 5 Insertion_sort (arr) `````` [0, 9, 8, 7, 1, 2, 3, 4, 5, 6] # insertion_sort(arr) `````` [0, 9, 8, 7, 1, 2, 3, 4, 5, 6] # insertion_sort(arr) `````` [0, 8, 9, 7, 1, 2, 3, 4, 5, 6] # The hand is 0, 9, touch 8, now I =2, j=1, 9 is greater than 8, move 9 one place to the right, j-1=0, Put the 8 j + 1 = 1 in [0, 7, 8, 9, 1, 2, 3, 4, 5, 6] [0, 1, 7, 8, 9, 2, 3, 4, 5, 6] [0, 1, 2, 7, 8, 9, 3, 4, 5, 6] [0, 1, 2, 3, 7, 8, 9, 4, 5, 6] [0, 1, 2, 3, 4, 7, 8, 9, 5, 6] [0, 1, 2, 3, 4, 5, 7, 8, 9, 6] [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

4. Shell Sort

1, the principle of

Hill Sort is a more efficient and improved version of insertion Sort. It is a group insertion Sort algorithm, also known as Diminishing Increment Sort. Hill Sort is an unstable sorting algorithm. The method got its name from D.L. Hell’s suggestion in 1959.

Hill Sort proposed an improved method based on the following two properties of insertion sort:

  • Insertion sort has high efficiency when it operates on data that has been almost sorted, that is, it can achieve the efficiency of linear sort.
  • But insertion sort is generally inefficient because it can only move data one bit at a time;

The basic idea of Hill Sort is: first divide the entire record sequence to be sorted into several sub-sequences and conduct direct insertion sort respectively; when the records in the whole sequence are “basically ordered”, then conduct direct insertion sort for all records successively.

2, steps,

  • ① n is the length of the array. First, take an integer d1=n/2, divide the elements into d1 groups, and the distance between adjacent elements in each group is d1-1. Direct insertion sort is carried out in each group;
  • ② Take the second integer d2=d1/2, and repeat step ① grouping sort process until di=1, that is, all elements in the same group are directly inserted sort.

PS: Hill sorting does not make some elements in order each time, but makes the overall data closer and closer to order; The last sort makes all the data in order.

3. Animation demonstration

4. Code implementation

Def insertion_sort_gap(arr, gap): # for I in range(gap, len(arr)): While j >= 0 and arr[j] > TMP = arr[I] while j >= 0 Arr [j+gap] = arr[j] # Move the card to the right j -= gap # Decrease the index of the card in your hand, Arr [j+gap] = TMP def shell_sort(arr): d = Len (arr) // 2 Insertion_sort_gap (arr, d) insertion_sort_gap(arr, d

Instead of using two functions, we can write them together:

Def shell_sort(arr): d = len(arr) // 1 For I in range(d, len(arr)): While j >= 0 and arr[j] > TMP = arr[I] while j >= 0 and arr[j] > TMP: Arr [j + d] = Arr [j] # Move the card in your hand one position to the right (assign the card in your hand to the next position) j -= D # Decrease the subscript of the card in your hand, Arr [j +d] = TMP # Inserts the card into j+d # Arr [j +d] = TMP # Inserts the card into j+d #

5. Specific examples

Def insertion_sort_gap(arr, gap): # for I in range(gap, len(arr)): While j >= 0 and arr[j] > TMP = arr[I] while j >= 0 Arr [j+gap] = arr[j] # Move the card to the right j -= gap # Decrease the index of the card in your hand, Arr [j+gap] = TMP def shell_sort(arr): d = Len (arr) // 2 Insertion_sort_gap (arr, d) print(arr, d) print(arr, d) print(arr, d) 8] shell_sort(arr) `````` [3, 1, 2, 6, 5, 7, 4, 9, 8] [2, 1, 3, 6, 4, 7, 5, 9, 8] [1, 2, 3, 4, 5, 6, 7, 8, 9] `````` def shell_sort(arr): d = Len (arr) // 2 # while d >= 1: For I in range(d, len(arr)): While j >= 0 and arr[j] > TMP = arr[I] while j >= 0 and arr[j] > TMP: Arr [j + d] = Arr [j] # Move the card in your hand one position to the right (assign the card in your hand to the next position) j -= D # Decrease the subscript of the card in your hand, Print (arr) # print(arr) # print(arr) # print(arr) # print(arr) # print(arr) # print(arr) # 2, 9, 8] shell_sort(arr) `````` [3, 1, 2, 6, 5, 7, 4, 9, 8] [2, 1, 3, 6, 4, 7, 5, 9, 8] [1, 2, 3, 4, 5, 6, 7, 8, 9]

Merge Sort Merge Sort Merge Sort

1, the principle of

The concept of merge: Suppose a list is divided into two segments, each of which is an ordered list. Now merge the two segments into an ordered list. This operation is called a merge.

Merge Sort is an effective and stable sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. A completely ordered sequence is obtained by combining the ordered subsequences. That is, first order each subsequence, and then order between subsequence segments. If two ordered tables are merged into one, it is called two-way merge.

2, steps,

The basic steps of merge:

  • (1) Apply for a space whose size is the sum of two sorted sequences, and the space is used to store the combined sequence;
  • (2) Set two Pointers, the initial position of which is the starting position of two sorted sequences;
  • (3) Compare the elements pointed by two Pointers, select the relatively small element into the merge space, and move the pointer to the next position;
  • ④ Repeat steps ③ until a pointer reaches the end of the sequence;
  • ⑤ Copies all remaining elements of another sequence directly to the end of the merged sequence.

The steps for merge sort:

  • ① Decomposition: the list is divided into smaller and smaller, until it is divided into an element, the termination condition: an element is ordered.
  • Merge: keep merging the two ordered lists, the list is bigger and bigger, until all the sequences are merged.

3. Animation demonstration

4. Code implementation

def merge(arr, low, mid, high): # low and high are the first and last position indexes of the entire array, mid is the middle position index # I and j are Pointers, I = low j = mid+1 LTMP = [] while I <= mid and j <= high: If arr[I] < arr[j]: if arr[I] < arr[j]: if arr[I] < arr[j]: LTMP. LTMP. (arr[j]) LTMP. (arr[j]) LTMP. LTMP I += 1 while j <= high: LTMP I += 1 LTMP j += 1 arr[low:high+1] = LTMP def merge_sort(arr, arr) If low < high, index the first and last position of the entire array: Merge_sort (arr, mid+1, high) merge_sort(arr, mid+1, high) merge_sort(arr, mid+1, high) Low, mid, high) # do merge

5. Specific examples

def merge(arr, low, mid, high): # low and high are the first and last position indexes of the entire array, mid is the middle position index # I and j are Pointers, I = low j = mid+1 LTMP = [] while I <= mid and j <= high: If arr[I] < arr[j]: if arr[I] < arr[j]: if arr[I] < arr[j]: LTMP. LTMP. (arr[j]) LTMP. (arr[j]) LTMP. LTMP I += 1 while j <= high: LTMP I += 1 LTMP j += 1 arr[low:high+1] = LTMP def merge_sort(arr, arr) If low < high, index the first and last position of the entire array: Merge_sort (arr, mid+1, high) merge_sort(arr, mid+1, high) merge_sort(arr, mid+1, high) Print (arr = [7, 1, 3, 2, 6, 9, 4] merge_sort(arr, 0, len(arr)-1) `````` [1, 7, 0, len(arr)-1) 3, 2, 6, 9, 4] [1, 7, 2, 3, 6, 9, 4] [1, 2, 3, 7, 6, 9, 4] [1, 2, 3, 7, 6, 9, 4] [1, 2, 3, 7, 4, 6, 9] [1, 2, 3, 4, 6, 7, 9]
Here is an anti-crawler text, please ignore the reader. This article was originally published on CSDN by TRHX• Bob. Blog homepage: https://itrhx.blog.csdn.net/ this link: https://itrhx.blog.csdn.net/article/details/109251836 unauthorized, prohibited reproduced! Maliciously reproduced, the consequences! Respect the original, away from plagiarism!

6. Quick Sort

1, the principle of

Quicksort is an improvement on Bubble Sort. As the name suggests, quicksort is fast and efficient! It’s one of the fastest sorting algorithms to deal with big data. Its basic idea is: by a trip to sort to sort data split into separate two parts, one part of all the data are smaller than the other part of all data, and then of the two parts data respectively according to the method of quick sort, the entire sorting process can be recursive, to achieve the whole data into an orderly sequence.

2, steps,

  • ① pick out an element from the sequence, called the “reference value”;
  • (2) Reorder the sequence. All elements smaller than the base value are placed to the left of the base value, and elements larger than the base value are placed to the right of the base value (the same number can go to either side). After the partition exits, the base value is in the middle of the sequence. This is called partition operation, or a homing operation. The process of homing operation is shown in the following GIF.
  • ③ Recursively sort the subsequences of elements that are less than the base value and those that are greater than the base value according to step ① ②.

3. Animation demonstration

4. Code implementation

Def partition(arr, left, right): TMP = arr[left] while left < right: while left < right and arr[right] >= tmp: # select a number from the right that is less than TMP, if it is greater than TMP, Arr [left] = arr[right] # while left < right and arr[left] <= TMP: # find the number greater than TMP from the left, if less than TMP, Arr [right] = arr[left] # Arr [left] = TMP # Arr [left] = TMP # Arr [left] = TMP # Def quick_sort(arr, left, right): # quicksort if left < right: Mid = partition(arr, left, right) Return arr (right) # return arr

5. Specific examples

Def partition(arr, left, right): TMP = arr[left] while left < right: while left < right and arr[right] >= tmp: # select a number from the right that is less than TMP, if it is greater than TMP, Arr [left] = arr[right] # while left < right and arr[left] <= TMP: # find the number greater than TMP from the left, if less than TMP, Arr [right] = arr[left] # Arr [left] = TMP # Arr [left] = TMP # Arr [left] = TMP # Def quick_sort(arr, left, right): if left < right: Mid = partition(arr, left, right) print(arr, left, mid) print(arr, left, mid) Mid + 1, right) # to place right half operating arr = [5, 7, 4, 6, 3, 1, 2, 9, 8] quick_sort (arr. Zero, len (arr) - 1) ` ` ` ` ` ` [2, 1, 4, 3, 5, 6, 7, 9, 8] [1, 2, 4, 3, 5, 6, 7, 9, 8] [1, 2, 3, 4, 5, 6, 7, 9, 8] [1, 2, 3, 4, 5, 6, 7, 9, 8] [1, 2, 3, 4, 5, 6, 7, 9, [1, 2, 3, 4, 5, 6, 7, 8, 9]

7. Heap Sort

1, the principle of

Heap sort is a kind of sorting algorithm based on the data structure of heap. The heap is an almost complete binary tree structure, and simultaneously satisfies the property of the heap: that is, the key or index of a child node is always smaller than (or greater than) its parent node.

  • Heap: A special kind of complete binary tree structure
  • Large root heap: A complete binary tree in which any node is larger than its children
  • Small root heap: A complete binary tree in which any node is smaller than its children

2, steps,

  • ① Build the heap: build the sorted sequence into a heap H[0…… n-1], start from the last non-leaf node, adjust from left to right, from bottom to top. Select large top heap or small top heap according to ascending or descending requirements;
  • ② In this case, the top element of the heap is the largest or smallest element;
  • (3) Interchange the top and tail elements of the heap, adjust the heap, and reorder the heap;
  • (4) The top element of the heap is the second largest element.
  • ⑤ Repeat the above steps until the heap is empty.

3. Animation demonstration

After the heap is built, push sort:

4. Code implementation

Def sift(arr, low, high): """ :param li: list :param low: root node location of heap :param high: "" I = low # I = root j = 2 * I + 1 # j = left child TMP = arr[low] # j <= high If j+1 <= high and arr[j+1] > arr[j]: if j+1 <= high and arr[j+1] > arr[j]: if j+1 <= high and arr[j+1] > arr[j]: Arr = arr [I] [j] I = j # to look down a layer of j I + 1 = 2 * else: # TMP is bigger, the TMP on the location of the I arr [I] = # TMP put TMP on a certain level of leadership position break the else: Def heap_sort(arr): n = len(arr) for I in range((n-2)//2, -1, -1): Sift (arr, I, n-1) for I in range(n-1, -1, -1): Sift (arr, I, I -1) # I -1 is the new high return arr (I, I, I)

5. Specific examples

Def sift(arr, low, high): """ :param li: list :param low: root node location of heap :param high: "" I = low # I = root j = 2 * I + 1 # j = left child TMP = arr[low] # j <= high If j+1 <= high and arr[j+1] > arr[j]: if j+1 <= high and arr[j+1] > arr[j]: if j+1 <= high and arr[j+1] > arr[j]: Arr = arr [I] [j] I = j # to look down a layer of j I + 1 = 2 * else: # TMP is bigger, the TMP on the location of the I arr [I] = # TMP put TMP on a certain level of leadership position break the else: Def heap_sort(arr): n = len(arr) print(' arr ') print(arr) for I in range((n-2)//2, -1, -1): Print (arr) print(arr) print(arr) print(arr) print(arr) for I in range(n-1, -1, -1): Arr [I] = arr[I], arr[0] sift(arr, 0, I -1) 17, 1, 90, 3, 36] heap_sort(arr) `````` Heap_sort (arr) [2, 7, 26, 25, 19, 17, 1, 90, 3, 36] [2, 7, 26, 25, 36, 17, 1, 90, 3, 19], [2, 7, 26, 90, 36, 17, 1, 25, 3, 19], [2, 7, [2, 90, 26, 25, 36, 17, 1, 7, 3] Heap sort process: [90, 36, 26, 25, 19, 7, 17, 1, 2, 3, 90] [25, 25, 26, 7, 19, 1, 2, 36, 90] 19, 17, 7, 2, 3, 1, 26, 36, 90], [17, 19, 7, 1, 2, 3, 25, 26, 36, 90] [17, 7, 3, 1, 2, 19, 25, 26, 36, 90], [7, 2, 3, 1, [1, 2, 3, 7, 17, 19, 25, 26, 36, 90] [2, 2, 3, 7, 26, 36, 90] 25, 26, 36, 90 [1, 2, 3, 7, 17, 19, 25, 26, 36, 90]

8. Counting Sort

1, the principle of

Counting sort is a non-comparison based sorting algorithm. Its advantage is that it has a complexity of Ο(n+k) when sorting integers in a range, where k is the range of integers, which is faster than any comparison sorting algorithm. Counting sort is an exercise in sacrificing space for time. The core of counting sort is to convert input data values into keys and store them in additional array space. As a sort of linear time complexity, counting sort requires that the input data must be integers with a definite range.

2, steps,

  • ① Find the maximum value k in the list to be sorted, and open up a count list of length k+1. The count list values are all 0.
  • (2) If the value of the element traversal is I, then the value of the index I in the counting list is increased by 1.
  • (3) Traversal the complete list to be sorted, count the value j of I in the list means the number of I is j, count the number of each value in the list to be sorted.
  • (4) Create a new list (or empty the original list, add in the original list), traversal counting list, add j I in turn in the new list, the new list is sorted after the list, the whole process does not compare the data size of the list to be sorted.

3. Animation demonstration

4. Code implementation

def count_sort(arr): if len(arr) < 2: Return arr max_num = Max (arr) count = [0 for _ in range(max_num+1)] Count [val] += 1 arr. Clear () # For ind, val in count: arr.append(ind) return arr

5. Specific examples

def count_sort(arr): if len(arr) < 2: Return arr max_num = Max (arr) count = [0 for _ in range(max_num+1)] Count [val] += 1 arr. Clear () # For ind, val in count: arr.append(ind) return arr arr = [2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2] sorted_arr = count_sort(arr) print(sorted_arr) `````` [1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]

Bucket Sort

1, the principle of

Bucket sort, also known as box sort, works by dividing an array into a finite number of buckets. Each bucket is sorted individually (it is possible to use a different sorting algorithm or to recursively continue to use bucket sorting). Barrel sort is an inductive result of pigeon nest sort.

Bucket sort is also an updated version of count sort. It makes use of the mapping relation of functions, and the key to its efficiency 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 where additional space is available;
  • The mapping function used can distribute the input N data evenly among K buckets.

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

  • Fastest case: when the input data can be evenly distributed in each bucket;
  • Slowest case: when the input data is allocated to the same bucket.

2, steps,

  • ① create a quantitative array as an empty bucket;
  • (2) go through the sequence, put the elements one by one into the corresponding bucket;
  • ③ Sorting each bucket that is not empty;
  • ④ put elements back into the original sequence from a bucket that was never empty.

3. Animation demonstration

(GIF is from @five-minute learning algorithm, encroachment delete)

4. Code implementation

Def bucket_sort(arr): max_num = Max (arr) n = len(arr) buckets = [[] for _ in range(n)] i = min(var // (max_num // n), For j in range(len(buckets[I])-1, 0, -1): j in range(len(buckets[I])-1, 0, -1): if buckets[i][j] < buckets[i][j-1]: buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j] else: break sorted_arr = [] for buc in buckets: sorted_arr.extend(buc) return sorted_arr

5. Specific examples

Def bucket_sort(arr): max_num = Max (arr) n = len(arr) buckets = [[] for _ in range(n)] i = min(var // (max_num // n), For j in range(len(buckets[I])-1, 0, -1): j in range(len(buckets[I])-1, 0, -1): if buckets[i][j] < buckets[i][j-1]: buckets[i][j], buckets[i][j-1] = buckets[i][j-1], buckets[i][j] else: break sorted_arr = [] for buc in buckets: sorted_arr.extend(buc) return sorted_arr arr = [7, 12, 56, 23, 19, 33, 35, 42, 42, 2, 8, 22, 39, 26, 17] sorted_arr = bucket_sort(arr) print(sorted_arr) `````` [2, 7, 8, 12, 17, 19, 22, 23, 26, 33, 35, 39, 42, 42, 56]

10. Radix Sort

1, the principle of

Radix sort belongs to distributive sort, which is a kind of non-comparative integer sorting algorithm. Its principle is to cut the integer into different numbers according to the number, and then compare them respectively according to each number. Since integers can also represent strings (such as names or dates) and floating-point numbers in a specific format, radix sort is not restricted to integers.

The three sorting algorithms, radix sort, count sort and bucket sort, all use the concept of bucket, but there are obvious differences in the use of bucket:

  • Radix sort: Assigns buckets according to each number of key values;
  • Counting sort: Each bucket stores only a single key value;
  • Bucket sort: Each bucket stores a range of values.

2, steps,

  • ① take the largest number in the array, and get the number of bits;
  • (2) Starting from the lowest order, the sorting is performed successively;
  • ③ The sequence becomes an ordered sequence from the lowest bit sorting to the highest bit sorting.

3. Animation demonstration

4. Code implementation

Def radix_sort(li): max_num = Max (li) # max_num = Max (li) # max_num = Max (li) # max_num = Max (li) # max_num = Max (li) # max_num = 0 while 10 ** it <= max_num: buckets = [[] for _ in range(10)] for var in li: # var=987, it=1, 987//10->98, 98%10->8; it=2, 987//100->9, 9% 10 = 9 digit = (/ var / 10 * * it) % 10 #, in turn, take a digit buckets [digit]. Append (var) # points barrels to complete li. The clear () for buc in buckets: Li.extend (buc) it += 1 # Write back to li return arr

5. Specific examples

Def radix_sort(li): max_num = Max (li) # max_num = Max (li) # max_num = Max (li) # max_num = Max (li) # max_num = Max (li) # max_num = 0 while 10 ** it <= max_num: buckets = [[] for _ in range(10)] for var in li: # var=987, it=1, 987//10->98, 98%10->8; it=2, 987//100->9, 9% 10 = 9 digit = (/ var / 10 * * it) % 10 #, in turn, take a digit buckets [digit]. Append (var) # points barrels to complete li. The clear () for buc in buckets: Arr = [3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127] sorted_arr = radix_sort(arr) print(sorted_arr) `````` [1, 7, 10, 82, 577, 743, 2030, 2599, 3138, 3221, 4127, 4793, 5622, 9420, 9680]