Explain:
This article mainly uses Python to achieve common sorting and search algorithms:Bubble sort、Selection sorting、Insertion sort、Shell Sort、Fast sorting、Merging sortingas well asTwo point lookupWait.
The basic idea of the algorithm is briefly explained, so long as the basic idea is understood, it has nothing to do with language realization.
This article mainly refers to the internet article, for learning only.
Development environment: Python3.5
Bubble sort
Bubble Sort is a relatively common sorting algorithm. It iterates over the sequence to be sorted and compares two adjacent elements at a time. If the sequence is wrong, the positions are exchanged with each other, and the sequence is sorted until no more exchange is needed. The name of this algorithm is:The smaller elements (ascending order) float slowly through the exchange to the top of the sequence.
1、The basic idea of bubble sort (operation principle):
· Comparing the adjacent elements, if the first is larger than the second (ascending order), then swap them for two.
· Do the same thing for each pair of adjacent elements, starting with the first pair and ending with the last pair. After this step, the last element is the largest number.
· Repeat the above steps for all elements except for the last one (the penultimate second is compared with the one already).
· Repeat the steps above for fewer and fewer elements continuously until no pair of numbers need to be compared.
Schematic diagram of exchange process (first time) (from network):
2、pythonImplementation process:
Here are two implementation processes, and the second implementation process is shown in the schematic diagram above.
1 # coding=utf-8 2 3 4 def bubble_sort(ls): 5 """Bubble sort""" 6 print("before: ", ls) 7 for i in range(0, len(ls) - 1): 8 # i = [0, 1, ...., len(ls) - 2]，The subscript of the first number of each comparison. 9 # j = [i + 1, i + 2, ..., len(ls) - 1]，The subscript of second numbers for each comparison. 10 for j in range(i + 1, len(ls)): 11 if ls[i] > ls[j]: 12 ls[i], ls[j] = ls[j], ls[i] 13 print(ls) 14 print("after: ", ls) 15 16 17 def bubble_sort2(ls): 18 """Bubble sort""" 19 print("before：", ls) 20 for j in range(len(ls) - 1, 0, -1): 21 # j = [len(ls) - 1, len(ls) - 2, ..., 1], The number of times needed to be compared each time 22 # i = [0, 1, 2, ..., j - 1]，Subscript requiring comparison 23 for i in range(j): 24 if ls[i] > ls[i + 1]: 25 ls[i], ls[i + 1] = ls[i + 1], ls[i] 26 print(ls) 27 print("after：", ls) 28 29 30 if __name__ == "__main__": 31 ls1 = [54, 26, 93, 17, 77, 31, 44, 55, 20] 32 ls2 = [54, 26, 93, 17, 77, 31, 44, 55, 20] 33 34 bubble_sort(ls1) 35 print("-"*50) 36 bubble_sort2(ls2)
The result of execution (the split line is the result of the execution of bubble_sort1 (), and the split line is the result of the execution of bubble_sort2 ():
3、Time complexity:
Optimal time complexity: O (n) (indicating that a traversal finds that no exchangeable element is sorted out, the inner loop can make an identification judgment, and jumps out if there is no exchange for the first loop)
The worst complexity is O (n).2)
Stability: stability
Two, select sort
Selection Sort is a simple and intuitive sorting algorithm.First, find the smallest (largest) element in the unordered, store it at the beginning of the sorted sequence, then continue to find the smallest (largest) element from the remaining unordered elements, then put it at the end of the sorted, and then analogize until all the elements are sorted.。
The main advantage of sorting is related to data movement. If an element is located at the correct final location, it will not be moved. Select Sort to swap a pair of elements each time, at least one of them moves to its final position, so sort the table of n elements together up to n-1Exchange. Of all the sorting methods that complete by swapping to move elements, selective sorting is a very good one.
1、The sorting process is illustrated in the graph source network.
Assume that the right side is sorted, then select a maximum value from the left unsorted and put it to the right.
2、pythonImplementation process:
The idea of the code here is to assume that the left side is sorted and the right one to be sorted.
1 # coding=utf-8 2 3 4 def selection_sort(ls): 5 """Selection sorting""" 6 # Assume that the left side is sorted, and the right is unsorted. 7 8 print("before：", ls) 9 for i in range(0, len(ls) - 1): 10 # i = [0, 1, 2,,, len(ls) - 2] 11 # j = [i + 1, i + 2,,, len(ls) - 1] 12 min_index = i 13 for j in range(i + 1, len(ls)): 14 if ls[j] < ls[min_index]: 15 min_index = j 16 17 if min_index != i: 18 ls[min_index], ls[i] = ls[i], ls[min_index] 19 print(ls) 20 print("after：", ls) 21 22 23 if __name__ == "__main__": 24 ls = [54, 26, 93, 17, 77, 31, 44, 55, 20] 25 26 selection_sort(ls)
3、Time complexity:
The optimal time complexity is O (n).2)
The worst time complexity is O (n).2)
Stability: instability (considering ascending order, choosing the largest case each time).
Three. Insertion sort
Insert ion Sort works by constructing ordered sequences that scan backwards and forwards from unordered data to locate and insert. In the implementation of insertion sorting, the sorted elements need to be moved back and forth repeatedly during the forward scanning process.Provide insertion space for the latest elements.
1、The sorting process is illustrated by pictures (pictures from the network):
2、pythonImplementation process:
From 1 to 0, compare and exchange.
1 # coding=utf-8 2 3 4 def insert_sort(ls): 5 """Insertion sort""" 6 # Assuming that the left is sorted and the right is unsorted, take a number from the right at a time, traverse the sorted subsequence until you find the position of the number. 7 print("before: ", ls) 8 for j in range(1, len(ls)): 9 for i in range(j, 0, - 1): 10 if ls[i] < ls[i - 1]: 11 ls[i], ls[i - 1] = ls[i - 1], ls[i] 12 print(ls) 13 print("after: ", ls) 14 15 16 if __name__ == "__main__": 17 ls = [54, 26, 93, 17, 77, 31, 44, 55, 20] 18 19 insert_sort(ls)
Implementation results:
3、Time complexity:
Optimal time complexity: O (n) (ascending sequence, sequence is in ascending state).
The worst time complexity is O (n).2)
Stability: stability
Four, Hill sorting
Hill sorting (Shell Sort) is a sort of insertion sort. Also known as incremental sort, is a more efficient version of the direct insertion sort algorithm. Hill sorting is the grouping of records by a certain increment of the subscript, sorting each group using a direct insertion sorting algorithm; as the increment decreases, each groupMore and more keywords are included. When the increment is reduced to 1, the whole sequence is divided into a group and the algorithm terminates.
1、Hill sorting process:
The basic idea: repeat the process by listing arrays in a table and inserting columns, but each time with longer columns (longer steps, fewer columns). Finally, there is only one list. In order to better understand this algorithm, the algorithm itself uses array.Sort.
For example, suppose that there is such a set of numbers [13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10], if we start with a step size of 5, we can do so by placing this list in a table with five columnsWell, describe the algorithm so that they should look like this (the vertical element is a step size):
Finally, it is sorted by 1 steps (this is a simple insertion sort).
2、pythonImplementation process:
The implementation process is basically similar to insert sort, except that the insert sort step is fixed to 1 and the Hill sort step changes to 1.
1 # coding=utf-8 2 3 4 def shell_sort(ls): 5 """Shell Sort""" 6 print("before: ", ls) 7 8 step = len(ls) // 2 # Initial step size 9 10 while step > 0: 11 # Insertion sort 12 for j in range(step, len(ls)): 13 for i in range(j, 0, - step): 14 if ls[i] < ls[i - step]: 15 ls[i], ls[i - step] = ls[i - step], ls[i] 16 step //= 2 17 print(ls) 18 print("shell_sort ：", ls) 19 20 21 if __name__ == "__main__": 22 ls = [54, 26, 93, 17, 77, 31, 44, 55, 20] 23 24 shell_sort(ls)
Implementation results:
3、Time complexity:
The optimal time complexity is different according to the sequence of step size.
The worst time complexity is O (n).2)。
Stability: instability.
Five. Quick sort
Quick Sort, also known as Partition-exchange Sort, splits the sorted data into two separate parts by a single sort, in which all the data in one part laughs more than all the data in the other part.Then, the two parts of the data are sorted separately by this method, and the whole sorting process can be recursively carried out, so that the whole data becomes an ordered sequence.
1、Quick sort process:
① An element is selected from a sequence of numbers, called pivot.
② Rearrange the sequence, all elements smaller than the base value placed in front of the benchmark, all elements larger than the benchmark placed behind the benchmark (the same number, can be placed on any side). After the partition ends, the datum is in the middle of the series. This is called partition (partition) operation..
③ Recursion (recursive) sorts the sub sequence less than the base Moto Soko sequence and the element greater than the reference value.
The bottom case of recursion is that the size of the sequence is zero or one, which is always sorted.
2、pythonImplementation process:
Here are two quick sorting methods, the basic idea is the same, the first is to operate on the original list (by cursor), the second is to create a new left and right sub-list for storage.
1 # coding=utf-8 2 3 4 def quick_sort1(ls, start, end): 5 """ 6 Quick sort -1 7 low And high point to the head and tail of the sequence, respectively. 8 low += 1， high -= 1 9 In the process of low self increment until the subscript is larger than mid_val.10 In the process of increasing or decreasing high, until we find a small label smaller than mid_val.11 Then the two values are exchanged.12 """ 13 14 # Recursive exit condition 15 if start >= end: 16 return 17 18 low = start 19 high = end 20 mid_val = ls[low] 21 22 while low < high: 23 while low < high and ls[high] > mid_val: 24 high -= 1 25 ls[low] = ls[high] 26 27 while low < high and ls[low] < mid_val: 28 low += 1 29 ls[high] = ls[low] 30 31 ls[low] = mid_val 32 33 print("mid:", mid_val, ls) 34 35 quick_sort1(ls, start, low - 1) # Subsequence on the left 36 quick_sort1(ls, low + 1, end) # Subsequence on the right 37 38 return ls 39 40 41 def quick_sort2(ls): 42 """Quick sort -2""" 43 44 # Recursive exit condition 45 if len(ls) <= 1: 46 return ls 47 48 left_ls, right_ls = [],[] 49 mid_val = ls[0] 50 for i in range(1, len(ls)): 51 if ls[i] < mid_val: 52 left_ls.append(ls[i]) 53 else: 54 right_ls.append(ls[i]) 55 56 print(left_ls, mid_val, right_ls) 57 58 # Recursive calls, left and right sublists 59 left_res = quick_sort2(left_ls) 60 right_res = quick_sort2(right_ls) 61 62 return left_res + [mid_val] + right_res 63 64 65 66 if __name__ == "__main__": 67 ls1 = [54, 26, 93, 17, 77, 31, 44, 55, 20] 68 ls2 = [54, 26, 93, 17, 77, 31, 44, 55, 20] 69 70 print("before：", ls1) 71 res1 = quick_sort1(ls1, 0, len(ls1) - 1) 72 print("quick sort1: ", res1) 73 74 print("-"*50) 75 print("before: ", ls2) 76 res2 = quick_sort2(ls2) 77 print("quick sort2：", res2)
Implementation results:
3、Time complexity:
Optimal time complexity: O (nlogn)
The worst time complexity is O (n).2)
Stability: instability
Six. Merge sort
Merge sort is a typical application of divide and conquer method. The idea of merging sort isFirst decompose the array recursively, then merge the array.。
After the array is decomposed to the smallest, two ordered arrays are merged. The basic idea is to compare the first number of two arrays, who is small first, then move the corresponding pointer backwards. Then compare until one array is empty and then copy the rest of the other array.
1、Merge and sort process.
2、pythonImplementation process:
First split the sequence into left_ls and right_ls, then merge into one res.
1 # coding=utf-8 2 3 4 def merge_sort(ls): 5 """Merging sorting""" 6 n = len(ls) 7 8 # Recursive exit condition 9 if n <= 1: 10 return ls 11 12 mid = n // 2 13 14 # 1、Molecular sequence 15 left_ls = merge_sort(ls[:mid]) 16 right_ls = merge_sort(ls[mid:]) 17 18 # 2、Merging subsequences: left_ls and right_ls 19 left_point, right_point = 0, 0 20 res = [] 21 22 # When left_ls or right_ls ends, it exits while, and the other may not end, requiring res + = 23 while left_point < len(left_ls) and right_point < len(right_ls): 24 # Compare two subsequences, and small ones first to res[]. 25 if left_ls[left_point] < right_ls[right_point]: 26 res.append(left_ls[left_point]) 27 left_point += 1 28 else: 29 res.append(right_ls[right_point]) 30 right_point += 1 31 print("res:", res) 32 33 res += left_ls[left_point:] 34 res += right_ls[right_point:] 35 36 return res 37 38 39 if __name__ == "__main__": 40 ls = [54, 26, 93, 17, 77, 31, 44, 55, 20] 41 42 print("before: ", ls) 43 res = merge_sort(ls) 44 print("merge sort: ", res)
Implementation results:
3、Time complexity:
Optimal time complexity: O (nlogn)
Worst time complexity: O (nlogn)
Stability: stability
Seven and two points lookup
Binary search, also known as folded and half search, has the advantages of fewer comparisons, fast search speed, and good average performance. Its disadvantages are that the table to be looked up is required to be ordered, and it is difficult to insert and delete. Therefore, the binary search method is applicable to frequent ordered lists without frequent changes.
Basic idea: Assume that the elements in the table are sorted in ascending order, and compare the keyword of the middle position record with the search keyword. If the two are equal, the search is successful. Otherwise, the middle position record is divided into two sub-tables. If the keyword of the middle position record is larger than the search keyword, the first sub-table is further searched.Table, otherwise, further look up a sub table. Repeat the above process until you find a record that meets the criteria, or until the subtable does not exist, the search is unsuccessful.
1、The two point search process is illustrated in the picture source network.
2、pythonImplementation process:
There are two main implementations, one recursive and the other non recursive.
1 # coding=utf-8 2 3 4 def binary_search_recursion(ls, item): 5 """Two points lookup -- recursion""" 6 n = len(ls) 7 if n < 1: 8 return False 9 10 mid = n // 2 11 12 # Comparison with intermediate values 13 if item == ls[mid]: 14 return True 15 16 # Go to the left child sequence to look up. 17 elif item < ls[mid]: 18 return binary_search_recursion(ls[:mid], item) 19 20 # Go to the right subsequence lookup. 21 else: 22 return binary_search_recursion(ls[mid + 1:], item) 23 24 25 def binary_search(ls, item): 26 """Two point lookup -- non recursive""" 27 n = len(ls) 28 start = 0 29 end = n - 1 30 31 while start <= end: 32 mid = (start + end) // 2 33 34 if item == ls[mid]: 35 return True 36 elif item < ls[mid]: 37 end = mid - 1 38 else: 39 start = mid + 1 40 return False 41 42 43 if __name__ == "__main__": 44 ls = [17, 20, 26, 31, 44, 54, 55, 77, 93] 45 46 num = int(input("Please enter an integer:")) 47 res = binary_search(ls, num) 48 print("Search results:", res)
Eight. Complete code
1 # coding=utf-8 2 3 4 def bubble_sort(ls): 5 """Bubble sort""" 6 print("before: ", ls) 7 for i in range(0, len(ls) - 1): 8 # i = [0, 1, ...., len(ls) - 2]，The subscript of the first number of each comparison. 9 # j = [i + 1, i + 2, ..., len(ls) - 1]，The subscript of second numbers for each comparison. 10 for j in range(i + 1, len(ls)): 11 if ls[i] > ls[j]: 12 ls[i], ls[j] = ls[j], ls[i] 13 print(ls) 14 print("after: ", ls) 15 16 17 def bubble_sort2(ls): 18 """Bubble sort""" 19 print("before：", ls) 20 for j in range(len(ls) - 1, 0, -1): 21 # j = [len(ls) - 1, len(ls) - 2, ..., 1], The number of times needed to be compared each time 22 # i = [0, 1, 2, ..., j - 1]，Subscript requiring comparison 23 for i in range(j): 24 if ls[i] > ls[i + 1]: 25 ls[i], ls[i + 1] = ls[i + 1], ls[i] 26 print(ls) 27 print("after：", ls) 28 29 30 def selection_sort(ls): 31 """Selection sorting""" 32 # Assume that the left side is sorted, and the right is unsorted. 33 34 print("before：", ls) 35 for i in range(0, len(ls) - 1): 36 # i = [0, 1, 2,,, len(ls) - 2] 37 # j = [i + 1, i + 2,,, len(ls) - 1] 38 min_index = i 39 for j in range(i + 1, len(ls)): 40 if ls[j] < ls[min_index]: 41 min_index = j 42 43 if min_index != i: 44 ls[min_index], ls[i] = ls[i], ls[min_index] 45 print(ls) 46 print("after：", ls) 47 48 49 def insert_sort(ls): 50 """Insertion sort""" 51 # Assuming that the left is sorted and the right is unsorted, take a number from the right at a time, traverse the sorted subsequence until you find the position of the number. 52 print("before: ", ls) 53 for j in range(1, len(ls)): 54 for i in range(j, 0, - 1): 55 if ls[i] < ls[i - 1]: 56 ls[i], ls[i - 1] = ls[i - 1], ls[i] 57 print(ls) 58 print("after: ", ls) 59 60 61 def shell_sort(ls): 62 """Shell Sort""" 63 print("before: ", ls) 64 65 step = len(ls) // 2 # Initial step size 66 67 while step > 0: 68 # Insertion sort 69 for j in range(step, len(ls)): 70 for i in range(j, 0, - step): 71 if ls[i] < ls[i - step]: 72 ls[i], ls[i - step] = ls[i - step], ls[i] 73 step //= 2 74 print(ls) 75 print("shell_sort ：", ls) 76 77 78 def quick_sort1(ls, start, end): 79 """ 80 Quick sort -1 81 low And high point to the head and tail of the sequence, respectively. 82 low += 1， high -= 1 83 In the process of low self increment until the subscript is larger than mid_val. 84 In the process of increasing or decreasing high, until we find a small label smaller than mid_val. 85 Then the two values are exchanged. 86 """ 87 88 # Recursive exit condition 89 if start >= end: 90 return 91 92 low = start 93 high = end 94 mid_val = ls[low] 95 96 while low < high: 97 while low < high and ls[high] > mid_val: 98 high -= 1 99 ls[low] = ls[high] 100 101 while low < high and ls[low] < mid_val: 102 low += 1 103 ls[high] = ls[low] 104 105 ls[low] = mid_val 106 107 print("mid:", mid_val, ls) 108 109 quick_sort1(ls, start, low - 1) # Subsequence on the left 110 quick_sort1(ls, low + 1, end) # Subsequence on the right 111 112 return ls 113 114 115 def quick_sort2(ls): 116 """Quick sort -2""" 117 118 # Recursive exit condition 119 if len(ls) <= 1: 120 return ls 121 122 left_ls, right_ls = [],[] 123 mid_val = ls[0] 124 for i in range(1, len(ls)): 125 if ls[i] < mid_val: 126 left_ls.append(ls[i]) 127 else: 128 right_ls.append(ls[i]) 129 130 print(left_ls, mid_val, right_ls) 131 132 # Recursive calls, left and right sublists 133 left_res = quick_sort2(left_ls) 134 right_res = quick_sort2(right_ls) 135 136 return left_res + [mid_val] + right_res 137 138 139 def merge_sort(ls): 140 """Merging sorting""" 141 n = len(ls) 142 143 # Recursive exit condition 144 if n <= 1: 145 return ls 146 147 mid = n // 2 148 149 # 1、Molecular sequence 150 left_ls = merge_sort(ls[:mid]) 151 right_ls = merge_sort(ls[mid:]) 152 153 # 2、Merging subsequences: left_ls and right_ls 154 left_point, right_point = 0, 0 155 res = [] 156 157 # When left_ls or right_ls ends, it exits while, and the other may not end, requiring res + = 158 while left_point < len(left_ls) and right_point < len(right_ls): 159 # Compare two subsequences, and small ones first to res[]. 160 if left_ls[left_point] < right_ls[right_point]: 161 res.append(left_ls[left_point]) 162 left_point += 1 163 else: 164 res.append(right_ls[right_point]) 165 right_point += 1 166 print("res:", res) 167 168 res += left_ls[left_point:] 169 res += right_ls[right_point:] 170 171 return res 172 173 174 def binary_search_recursion(ls, item): 175 """Two points lookup -- recursion""" 176 n = len(ls) 177 if n < 1: 178 return False 179 180 mid = n // 2 181 182 # Comparison with intermediate values 183 if item == ls[mid]: 184 return True 185 186 # Go to the left child sequence to look up. 187 elif item < ls[mid]: 188 return binary_search_recursion(ls[:mid], item) 189 190 # Go to the right subsequence lookup. 191 else: 192 return binary_search_recursion(ls[mid + 1:], item) 193 194 195 def binary_search(ls, item): 196 """Two point lookup -- non recursive""" 197 n = len(ls) 198 start = 0 199 end = n - 1 200 201 while start <= end: 202 mid = (start + end) // 2 203 204 if item == ls[mid]: 205 return True 206 elif item < ls[mid]: 207 end = mid - 1 208 else: 209 start = mid + 1 210 return False
Sorting and lookup algorithm.Py