How to implement quick sort algorithm in Python?

How to implement quick sort algorithm in Python?

Quick sort is a common and efficient sorting algorithm that can sort a list of n elements with a time complexity of O(n log n) on average. This article will introduce how to use Python to write a code example of the quick sort algorithm.

The basic idea of ​​quick sort is to select an element as the benchmark (usually the first element of the list), split the list into two subsequences, so that all elements of the left subsequence are smaller than the benchmark, and the elements of the right subsequence are smaller than the benchmark. All elements are larger than the baseline. Then the left and right subsequences are quickly sorted recursively until the length of the subsequence is 1 or 0 and the sorting is completed.

The following is a code example for implementing the quick sort algorithm in Python:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]  # 选择第一个元素作为基准
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

The above code defines a function called quicksort, which accepts a list arr as input and returns the sorted list. First, if the length of the input list is less than or equal to 1, the list is returned directly, because a list with a length of 0 or 1 is already ordered.

Then, select the first element of the list as the base pivot, and add other elements of the list to the two newly created lists, less and greater, so that the elements in less are less than or equal to pivot and greater. The elements are all larger than pivot.

Finally, the quicksort function is called recursively to quickly sort less and greater, and the sorted less, pivot and greater are spliced ​​together to obtain the final sorting result.

The following is an example of testing quick sort:

arr = [4, 2, 8, 5, 1, 6, 7, 3]
sorted_arr = quicksort(arr)
print(sorted_arr)  # 输出：[1, 2, 3, 4, 5, 6, 7, 8]

In the above example, the input list arr contains 8 integers, and the sort result obtained after quick sort is [1, 2 , 3, 4, 5, 6, 7, 8].

Summary:
Through the above code examples, we can see that it is relatively simple to implement the quick sort algorithm in Python. By selecting the reference element, the list is divided into two subsequences, and then the subsequences are sorted recursively, and finally an ordered list is obtained. Quick sort is an efficient sorting algorithm that is widely used in practical applications.

The above is the detailed content of How to implement quick sort algorithm in Python?. For more information, please follow other related articles on the PHP Chinese website!