Sorting algorithm is a basic algorithm in computer science, and it is widely used at the same time. python functions also have built-in sorting interfaces, such as the sorted function. In actual production, the sorting algorithm we use in different scenarios will be slightly different. The selection of sorting algorithm mainly considers the following factors:
Algorithm execution efficiency
Stability of sorting
Number of sorting elements
Overhead of recursive calls
Diagram of sorting algorithm:
Next, nine common sorting algorithms and python implementation are introduced.
Basic idea: compare from left to right. If the left element is larger than the right, exchange the positions of the two elements. In each round of sorting, the largest element in the sequence floats to the far right. In other words, at least one element is in the correct position in each round of sorting. In this way, the next cycle does not need to consider the ordered elements, and the number of inner cycles will be reduced by one each time.
def bubble_sort(a): n, swap_size = len(a), 1 while swap_size > 0: swap_size = 0 for i in range(n-1): if a[i] > a[i+1]: a[i],a[i+1] = a[i+1],a[i] swap_size += 1 n-=1 return a
Basic idea: an improvement of bubble sorting. The data to be sorted is divided into two independent parts by one sorting, and all the data in one part is smaller than that in the other part. Then quickly sort some of the data according to this method, which is a recursive call. Then quickly sort another part of the data according to this method, which is also a recursive call.
Quick sorting evaluation: the worst time complexity is O(n^2), which is a degraded situation. In most cases, as long as the appropriate partition element is selected, the time complexity is nlog(n). Quick sorting is usually faster than other O(nlogn) algorithms, which belongs to a fast unstable sorting algorithm.
def quick_sort(a, left=None, right=None): left = 0 if not isinstance(left,(int, float)) else left right = len(a)-1 if not isinstance(right,(int, float)) else right if left < right: part_index = part(a, left, right) quick_sort(a, left, part_index-1) quick_sort(a, part_index+1, right) return a def part(a, left, right): pivot = left index = pivot+1 i = index while i <= right: if a[i] < a[pivot]: a[i],a[index] = a[index],a[i] index+=1 i+=1 a[pivot],a[index-1] = a[index-1],a[pivot] return index-1
Simple insert sort
Basic idea: take out the first element from the unordered table every time and insert it into the appropriate position of the ordered table to make the ordered table still orderly until all elements in the unordered table are inserted. The worst time complexity is O(n^2), which belongs to stable sorting algorithm and is efficient for processing small batch data.
def insertion_sort(a): for i in range(len(a)): pre_index = i-1 current = a[i] while pre_index >= 0 and a[pre_index] > current: a[pre_index+1] = a[pre_index] pre_index-=1 a[pre_index+1] = current return a
Basic idea: first take a positive integer d1 and group it at intervals of d1. First, use the insertion sort operation for the elements in each group, and repeat the above grouping and direct insertion sort operation; Until di = 1, that is, all records are sorted in one group.
import math def shell_sort(a): gl=1 while (gl < len(a)/3): gl = gl*3+1 while gl > 0: for i in range(gl,len(a)): temp = a[i] j = i-gl while j >=0 and a[j] > temp: a[j+gl]=a[j] j-=gl a[j+gl] = temp gl = math.floor(gl/3) return a
Simple selection sort
Basic idea: it is a process of directly selecting the most value from the unordered sequence to the sorted sequence. Each time, the smallest (largest) element is selected from the data elements to be sorted, and the order is placed at the top of the sequence to be sorted until all the data elements to be sorted are finished.
def selection_sort(a): for i in range(len(a) - 1): min_index = i for j in range(i + 1, len(a)): if a[j] < a[min_index]: min_index = j if i != min_index: a[i], a[min_index] = a[min_index], a[i] return a
Basic idea: a sort algorithm designed by using binary tree (heap) data structure is an improved algorithm for direct selection sort. The logical structure is based on the binary tree storage structure, which optimizes the performance of selective sorting. In physical storage, it is a continuous array storage, which uses the characteristics of the array to quickly locate the elements of the specified index.
import math def heap_sort(a): al = len(a) def heapify(a, i): left = 2 * i + 1 right = 2 * i + 2 largest = i if left < al and a[left] > a[largest]: largest = left if right < al and a[right] > a[largest]: largest = right if largest != i: a[i], a[largest] = a[largest], a[i] heapify(a, largest) # Build pile for i in range(math.floor(len(a) / 2), -1, -1): heapify(a, i) # Constantly adjust the heap: root and last element for i in range(len(a) - 1, 0, -1): a, a[i] = a[i], a al -= 1 heapify(a, 0) return a
Basic idea: it is an effective sorting algorithm based on merging operation. The algorithm adopts a very typical application of Divide and Conquer. Merge the ordered subsequences to obtain a completely ordered sequence; That is, each subsequence is ordered first, and then the subsequence segments are ordered.
import math def merge_sort(a): if(len(a)<2): return a middle = math.floor(len(a)/2) left, right = a[0:middle], a[middle:] return merge(merge_sort(left), merge_sort(right)) def merge(left,right): result =  while left and right: if left <= right: result.append(left.pop(0)); else: result.append(right.pop(0)); while left: result.append(left.pop(0)); while right: result.append(right.pop(0)); return result
Basic idea: cut the integer into different numbers according to the number of digits, and then compare them according to each number of digits. It can only be expressed in integer or floating-point format, for example, it can only be expressed in integer or floating-point format.
import math def radix_sort(a): i = 0 # The record is currently taking one position, and the lowest position is 1 max_num = max(a) # Maximum value j = len(str(max_num)) # Number of digits to record the maximum value while i < j: bucket_list =[ for _ in range(10)] #Initialize bucket array for x in a: bucket_list[int(x / (10**i)) % 10].append(x) # Find the position and put it into the bucket array a.clear() for x in bucket_list: # Put back the original sequence for y in x: a.append(y) i += 1 return a
Basic idea: in order to save space and time, we need to specify the value of the smallest and largest number in the data to be sorted. Divide the array into a limited number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or continue to use bucket sorting recursively).
def bucket_sort(a): all_list = [0 for i in range(100)] # Array set to all 0 last_list =  for v in a: all_list[v] = 1 if all_list[v]==0 else all_list[v]+1 for i,t_v in enumerate(all_list): if t_v != 0: for j in range(t_v): last_list.append(i) return last_list
Finally, call the above methods in sequence:
sort_funs = [bubble_sort,quick_sort,insertion_sort,shell_sort,selection_sort,heap_sort,merge_sort,radix_sort,bucket_sort] a = [10, 7, 11, 7, 18, 17, 9, 17, 0, 7, 3, 20, 20, 15] for fun in sort_funs: a_sorted = fun(a) print(a_sorted)
The output results are consistent (non descending sequence):
[0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20] [0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20] [0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20] [0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20] [0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20] [0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20] [0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20] [0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20] [0, 3, 7, 7, 7, 9, 10, 11, 15, 17, 17, 18, 20, 20]