Python Quick Sort

Document 对象参考手册Python3 Examples

Quick sort uses the divide and conquer strategy to divide a sequence (list) into two smaller and larger subsequences, then recursively sort the two subsequences.

The steps are:

  • Pick a pivot value: pick an element from the sequence, called the "pivot";
  • Partitioning: reorder the sequence, all elements smaller than the pivot are placed before the pivot, all elements larger than the pivot are placed after the pivot (numbers equal to the pivot can go on either side). After this partitioning is done, the pivot is already in its final sorted position;
  • Recursively sort subsequences: recursively sort the subsequence of elements smaller than the pivot and the subsequence of elements larger than the pivot.

The base case for recursion is when the size of the sequence is zero or one, at which point the sequence is obviously already sorted.

There are several specific methods for choosing the pivot. This selection method has a decisive impact on the time performance of the sort.

Example

def partition(arr,low,high): i = ( low-1 ) # Minimum element index pivot = arr[high] for j in range(low , high): # Current element is less than or equal to pivot if arr[j] <= pivot: i = i+1 arr[i],arr[j] = arr[j],arr[i] arr[i+1],arr[high] = arr[high],arr[i+1] return ( i+1 ) # arr[] --> Sorted array # low --> Starting index # high --> Ending index # Quick sort function def quickSort(arr,low,high): if low < high: pi = partition(arr,low,high) quickSort(arr, low, pi-1) quickSort(arr, pi+1, high) arr = [10, 7, 8, 9, 1, 5] n = len(arr) quickSort(arr,0,n-1) print ("Sorted array:") for i in range(n): print ("%d" %arr[i]),

The output of executing the above code is:

排序后的数组:
1
5
7
8
9
10

Document 对象参考手册Python3 Examples

Other extensions