swust oj431quick sort
时间: 2023-11-11 07:15:05 浏览: 46
Sure! The QuickSort algorithm is a common sorting algorithm used to sort arrays or lists efficiently. It follows the divide-and-conquer approach and has an average time complexity of O(n log n).
Here is a simple implementation of the QuickSort algorithm in Python:
```python
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Example usage:
arr = [5, 2, 9, 1, 7, 6, 3]
sorted_arr = quicksort(arr)
print(sorted_arr)
```
This implementation selects a pivot element (in this case, the middle element), partitions the array into three sub-arrays (less than, equal to, and greater than the pivot), and recursively sorts each sub-array. Finally, it concatenates the sorted sub-arrays to obtain the sorted array.
Note that there are different variations of the QuickSort algorithm, such as choosing a random pivot or using a different partitioning scheme. This implementation represents a basic version.