QuickSort is an improvement on bubble sort:
Basic idea:
The data to be sorted is split into two independent parts by one trip sort, where all the data in one part is smaller than all the data in the other part, and then the two parts are quickly sorted separately by this method, and the entire sorting
The process can be performed recursively as a way to achieve the entire data into an ordered sequence.
The algorithm for a trip of fast sorting is:
1) Set two variables i, j. The sorting starts with: i=0, j=N-1;
2) Take the first array element as the key data and assign it to key, i.e. key=A[0];
3) Start searching forward from j, i.e., start searching forward from back to back (j--), find the first value A[j] that is less than key, and swap A[j] and A[i];
4) Start searching backward from i, i.e., start searching backward from the front (i++), find the first A[i] that is greater than key, and swap A[i] and A[j];
(5) Repeat steps 3 and 4 until i=j; (3,4 steps, did not find the value that meets the conditions, i.e., A[j] in 3 is not less than the key, 4 A[i] is not greater than the key when changing the value of j, i, so that j = j-1, i = i + 1, until found. Find the value that matches the condition.
The i and j pointers remain unchanged when the swap is performed. (In addition, the process i==j must coincide with the completion of i+ or j-, which ends the loop).
The quick sort code quick_sort.py implemented using python is as follows:
def sub_sort(array,low,high):
pivotkey=array[low]
while low<high :
while low<high and array[high]>=pivotkey:
high -= 1
array[low]=array[high]
while low<high and array[low]<=pivotkey:
low += 1
array[high]=array[low]
array[low]=pivotkey
return low
def quick_sort(array,low,high):
if low < high :
pivoloc=sub_sort(array,low,high)
quick_sort(array,low,pivoloc-1)
quick_sort(array,pivoloc+1,high)
if __name__=="__main__":
array=[49,38,65,97,76,13,27]
print array
quick_sort(array,0,len(array)-1)
print array
A quick sort on an array array=[49, 38, 65, 97, 76, 13, 27] yields the following result:
=============== RESTART: I:\python_DataStructure\quick_sort.py =============== [49, 38, 65, 97, 76, 13, 27] [13, 27, 38, 49, 65, 76, 97] >>>
This is the entire content of this article.