Quick sort
时间: 2023-07-05 12:06:13 浏览: 61
Quick sort is a popular sorting algorithm that works by partitioning an array into two sub-arrays, and then recursively sorting each sub-array. It is a divide-and-conquer algorithm that has an average time complexity of O(n log n), making it one of the fastest sorting algorithms.
The basic idea behind quick sort is to select a pivot element, partition the array around the pivot element, and then recursively apply the same process to each of the sub-arrays. The partitioning process involves selecting a pivot element, rearranging the array so that all elements less than the pivot are on one side and all elements greater than the pivot are on the other side, and then returning the index of the pivot element. This pivot index is then used to divide the array into two sub-arrays, which are recursively sorted.
Here's an example implementation of quick sort in Python:
```
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
left = []
right = []
for i in range(1, len(arr)):
if arr[i] < pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quick_sort(left) + [pivot] + quick_sort(right)
```
This implementation selects the first element of the array as the pivot, and then uses list comprehensions to create the left and right sub-arrays. The left sub-array contains all elements less than the pivot, while the right sub-array contains all elements greater than or equal to the pivot. The function then recursively sorts the left and right sub-arrays and combines them with the pivot element to produce the final sorted array.