This article example describes how Python implements fast sorting. Shared for your reference, as follows:
When it comes to Python implementations of fast sorting, let's first talk about the idea of, well, fast sorting:
1, take a reference value and put it in the middle of the list, after the initial sorting, so that all the values on the left side are smaller than him, and all the values on the right side, are larger than him.
2, respectively, on the left side and the right side of the part of the recursive step 1 of the operation
Realization Ideas:
- The two pointers left, right point to the first element and the last element of the list, respectively, and then take a reference value, which defaults to the first element of the first list, list[0], called K
- Then the value pointed to by left is first compared with the reference value K. If list[left] is less than or equal to the value of K, left moves all the way to the right, left+1, until it moves to a place where it is greater than the value of K and stops
- The value pointed to by right is compared with the reference value K. If list[right] is greater than the value of K, right moves all the way to the left, right-1, until it moves to a place that is less than the value of K and stops
- At this point, if left and right have not yet met, i.e., left is still smaller than right, then the two point to the value of the swap
- If they have met then, the first sort is complete, swap the values of list[right] and list[0] for the subsequent recursion
Programming Realization:
The main function of #FastRank, passed in as a list with subscripts at the left and right ends
def QuickSort(list,low,high):
if high > low:
# Pass in the parameters, through the Partitions function, to get the k subscript value
k = Partitions(list,low,high)
# recursively sort the list to the left of the subscript k
QuickSort(list,low,k-1)
# recursively sorted list to the right of subscript k
QuickSort(list,k+1,high)
def Partitions(list,low,high):
left = low
right = high
# Assign the leftmost value to the reference value k
k = list[low]
# When the left subscript, less than the right subscript, this time to determine whether the two move to intersect, if not intersected, then has been the cycle of
while left < right :
# When the value corresponding to left is less than the k reference value, it moves all the way to the right
while list[left] <= k:
left += 1
# When the value corresponding to right is greater than the k reference value, it moves all the way to the left
while list[right] > k:
right = right - 1
# If the two do not meet after the move, exchange the values corresponding to the subscripts.
if left < right:
list[left],list[right] = list[right],list[left]
# If the move is complete and have met, exchange the value corresponding to right and the reference value
list[low] = list[right]
list[right] = k
# Returns the value of k
return right
list_demo = [6,1,2,7,9,3,4,5,10,8]
print(list_demo)
QuickSort(list_demo,0,9)
print(list_demo)
Run results:
[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
PS: Here is another demo tool on sorting for your reference:
Online animated demonstration of insertion/selection/bubbling/merging/hill/fast sort algorithm process tool:
http://tools./aideddesign/paixu_ys
Readers interested in more Python related content can check out this site's topic: thePython Data Structures and Algorithms Tutorial》、《Python list (list) manipulation techniques summarized》、《Summary of Python coding manipulation techniques》、《Summary of Python function usage tips》、《Summary of Python string manipulation techniquesand thePython introductory and advanced classic tutorials》
I hope that what I have said in this article will help you in Python programming.