Python's quick sort method

This article mainly introduces the quick sort algorithm implemented in Python, and analyzes the principles, implementation methods and related operating techniques of Python quick sort in the form of examples. Friends in need can refer to the following

The examples in this article describe Quick sort algorithm implemented in Python. Share it with everyone for your reference, the details are as follows:

The basic idea of ​​quick sort is to divide the data to be sorted into two independent parts through one sorting, and all the data in one part is higher than all the data in the other part. should be small, and then use this method to quickly sort the two parts of the data respectively. The entire sorting process can be performed recursively, so that the entire data becomes an ordered sequence.

For example, in the sequence [6, 8, 1, 4, 3, 9], select 6 as the base number. Scan from right to left, looking for a number smaller than the base number 3, swap the positions of 6 and 3, [3, 8, 1, 4, 6, 9], then scan from left to right, looking for a number larger than the base number The number is 8, swap the positions of 6 and 8, [3, 6, 1, 4, 8, 9]. Repeat the above process until the numbers to the left of the base number are smaller and the numbers to the right are larger. Then perform the above method recursively on the sequences to the left and right of the reference number respectively.

The implementation code is as follows:

def parttion(v, left, right):
  key = v[left]
  low = left
  high = right
  while low < high:
    while (low < high) and (v[high] >= key):
      high -= 1
    v[low] = v[high]
    while (low < high) and (v[low] <= key):
      low += 1
    v[high] = v[low]
    v[low] = key
  return low
def quicksort(v, left, right):
  if left < right:
    p = parttion(v, left, right)
    quicksort(v, left, p-1)
    quicksort(v, p+1, right)
  return v
s = [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
print("before sort:",s)
s1 = quicksort(s, left = 0, right = len(s) - 1)
print("after sort:",s1)

Running result:

before sort: [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
after sort: [1, 2, 2, 3, 4, 4, 5, 6, 6, 8, 9, 11, 15]

The above is the detailed content of Python's quick sort method. For more information, please follow other related articles on the PHP Chinese website!