@ the Author: Runsen
The essence of programming comes from algorithm, and the essence of algorithm comes from mathematics, programming is just to code mathematical problems. —- Runsen
About sort, in fact, there are many, such as the common hill sort, bucket sort, count sort and radix sort, today in one breath the rest of the ten sort all solve.
Before that, you need to memorize the spatial and temporal complexity diagram of ten sorting algorithms that have been circulating on the Internet for thousands of years.
Hill sorting
Hill sort is a sort algorithm proposed by Donald Shell in 1959. Hill sort is also an insertion sort, which is a more efficient version of simple insertion sort, also known as reduced incremental sort, and was one of the first algorithms to break through O(n2)O(n^2)O(n2).
The idea of Hill sort is to divide the sequence to be sorted into several groups, insert sort in each group to make the whole sequence basically orderly, and then insert the whole sequence.
Looking back at the code for insert sort, if the inserted element is larger than the current element, the element to be inserted is inserted one bit after the current element. , moves the current element back one bit until one is found that is smaller than the inserted element.
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 arr
if __name__ == '__main__':
nums = [54.26.93.17.77.31.44.55.20]
insert_sort(nums)
print(nums) # [17, 20, 26, 31, 44, 54, 55, 77, 93]
Copy the codeThe basic idea of Hill sort is to group records by step size gap (gap is generally the middle number of array length), and sort each group of records by direct insertion sort method.
As the step size gradually decreases (divide by two), the group contains more and more records. When the step size value decreases to 1, the whole data is combined into a group to form a group of ordered records, and then the sorting is completed.
def shell_sort(nums) :
size = len(nums)
gap = size >> 1 # corresponds to size//2
while gap > 0:
The code is the same as insertion sort
for i in range(gap, size):
j = i
while j >= gap and nums[j - gap] > nums[j]:
nums[j - gap], nums[j] = nums[j], nums[j - gap]
I'm not subtracting one here, I'm subtracting gap
j -= gap
gap = gap >> 1
if __name__ == '__main__':
nums = [54.26.93.17.77.31.44.55.20]
shell_sort(nums)
print(nums) # [17, 20, 26, 31, 44, 54, 55, 77, 93]
Copy the codeHill sort For insertion sort, when the interval is large, the number of moves is smaller, and when the interval is small, the distance moved is shorter. Therefore, the efficiency of Hill sort is significantly higher than that of insertion sort.
But Hill sort is an unstable sorting algorithm. For sorting algorithms, instability means that the same elements are moved during sorting. A single insertion sort is stable and does not change the relative order of the same elements. However, in the process of different insertion sorts, the same elements may move in their own insertion sorts, and finally its stability will be disturbed. Therefore, Hill sort is an unstable sorting algorithm.
Count sorting
Counting sort is a high-minded sort that uses a small range of elements in the sequence to be sorted, and can sometimes be faster than quicksort.
So counting sort uses an auxiliary array counting list, also called, so it’s not O(1)O(1)O(1), it’s a sort algorithm that sacrifices space for time.
The core idea of count sort is to walk through the data to be sorted, looking for the maximum value K, and then open up a count list of length K +1 with all values of 0. If the value of the visited element is I, the value of index I in the count list is incremented by 1.
Visit the whole list to be sorted, count the value j of index I in the list, which means the number of I is j, and count the number of each value in the list to be sorted.
The value of the data to be sorted is the index of the secondary array, and the corresponding position of the secondary array index holds the number of occurrences of the data to be sorted. Finally, extract the data to be sorted from the auxiliary array and put it into the sorted array.
Finally, create a new list, iterate over the count list, and add data to the new list.
I don’t understand it. Don’t worry. I’ll figure it out in the next picture
So, you know that if a number is very large, say, 1000, then the auxiliary array becomes very large, so counting sort is only good for sorts that have a small range of elements in the sequence to be sorted.
def count_sort(s) :
""" Counting sort """
# find Max and min values
min_num = min(s)
max_num = max(s)
# count list
count_list = [0]*(max_num-min_num+1)
# count
for i in s:
count_list[i-min_num] += 1
s.clear()
# fill in back
for ind,i in enumerate(count_list):
whilei ! =0:
s.append(ind+min_num)
i -= 1
if __name__ == '__main__':
a = [3.6.8.4.2.6.7.3]
count_sort(a)
print(a)
Copy the codeBucket sort
Individuals think of bucket sort is actually a partition algorithm thought, I thought of bucket sorting, is associated with the college entrance examination scores rank, guangdong college entrance examination more than seventy candidates, we only need to different areas, such as in the 700 to 750 the number of this stage to sort, actually divided the operation for different areas, is divided into different barrel. Different buckets are sorted individually, so it’s called bucket sort.
Bucket sorting code, in fact, simple and simple, said difficult is also very difficult.
Now, I’m going to divide the buckets by the interval of 10. The sort inside the bucket selects quicksort, so also need to use a recursive write a quicksort algorithm, the specific code is as follows.
def quicksort(array) :
if len(array) < 2:
In the basic case, arrays with 0 or 1 elements are already "sorted"
return array
else:
# recursive case
pivot = array[0]
A subarray of all elements less than the reference value
less = [i for i in array[1:] if i <= pivot]
A subarray of all elements greater than the reference value
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
def bucket_sort(arr) :
maximum, minimum = max(arr), min(arr)
bucketArr = [[] for i in range((maximum - minimum)//10+1)] Set the number of buckets.
for i in arr: Put the elements of each array into the corresponding bucket.
index = (i - minimum)//10
bucketArr[index].append(i)
arr.clear()
for j in bucketArr:
ls = quicksort(j) Use another sort method to sort each bucket, use quicksort here.
arr.extend(ls) Move each bucket element into the array.
return arr
if __name__ == '__main__':
res = [34.23.74.35.98.34.18.88.47.51.65.75.44.89]
sort_res = bucket_sort(res)
print(sort_res) #[18, 23, 34, 34, 35, 44, 47, 51, 65, 74, 75, 88, 89, 98]
Copy the codeRadix sort
There’s a magic Sort, Radix Sort, which is essentially bucket Sort, and I think Radix Sort is a special case of bucket Sort, where who would want to use the ones place, the tens place,… Sort.
Radix sort is dividing ten buckets, zero to nine, these ten numbers.
The first bucket 0, you can put 10,20,30,100,
For example, to sort integers, use the ones, tens… To sort (LSD low priority); Or order from highest to lowest (MSD highest priority).
However, LSD low-level priority is easy to understand, such as 135, 242, 192, 93, 345, 11, 24, 19, collecting bits becomes 11, 242, 192, 93, 24, 135, 345, 19. Collecting the tens place becomes 11, 19, 24, 135, 242, 345, 192, 93. If you collect hundreds, you get 11, 19, 24, 93, 135, 192, 242, 345.
The specific implementation code is as follows.
def radix_sort(ls) :
i = 0 # Record which row is currently in. The lowest value is 1
max_num = max(ls) A maximum #
j = len(str(max_num)) # Record the maximum number of bits
while i < j:
bucket_list =[[] for q in range(10)] Initialize the bucket array
for x in ls:
bucket_list[int(x / (10**i)) % 10].append(x) Find the location to place in the bucket array
ls.clear()
for x in bucket_list: Return to the original sequence
for y in x:
ls.append(y)
i += 1
return ls
if __name__ == '__main__':
list1 = [135.242.192.93.345.11.24.19]
sort_list = radix_sort(list1)
print(sort_list) # [11, 19, 24, 93, 135, 192, 242, 345]
Copy the codeThe hill sort, bucket sort, count sort and radix sort are all introduced, followed by the introduction of directed graph, the last dynamic programming DP algorithm.
GitHub, portal ~, GitHub, portal ~, GitHub, Portal ~