算法原理
快速排序是对冒泡排序的改进,采用的是分治思想,即在一个无序的序列中选取一个任意的基准元素pivot,利用pivot将待排序的序列分成两部分,前面部分元素均小于或等于基准元素,后面部分均大于或等于基准元素,然后采用递归的方法分别对前后两部分重复上述操作,直到序列不可再分,最终得到一个有序的序列。
单指针实现
def partition(arr, low, high):
i = low
pivot = arr[high]
for j in range(low, high):
print(data[low:high])
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i = i + 1
arr[i], arr[high] = arr[high], arr[i]
return i
def quickSort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quickSort(arr, low, pi - 1)
quickSort(arr, pi + 1, high)
return arr
双指针实现
def quick_sort(arr,left,right):
if left < right:
temp = arr[left]
i,j = left,right
while i < j:
while arr[j] >= temp and i < j:
j -= 1
while arr[i] <= temp and i < j:
i += 1
if i < j:
arr[i],arr[j] = arr[j],arr[i]
arr[i],arr[left] = arr[left],arr[i]
print(arr)
quick_sort(arr,left,i-1)
quick_sort(arr,i+1,right)
return arr
```