分治策略 快速排序伪代码
时间: 2024-05-15 07:11:48 浏览: 8
分治策略是一种算法设计方法,它将问题划分为多个子问题,逐个解决这些子问题,最后将子问题的解合并成原问题的解。快速排序就是一种采用分治策略的排序算法。
快速排序的伪代码如下:
```
function quickSort(arr, left, right)
if left < right then
pivot := partition(arr, left, right)
quickSort(arr, left, pivot-1)
quickSort(arr, pivot+1, right)
function partition(arr, left, right)
pivot := arr[left]
i := left + 1
j := right
while i <= j do
while i <= j and arr[i] <= pivot do
i := i + 1
while i <= j and arr[j] >= pivot do
j := j - 1
if i < j then
swap(arr[i], arr[j])
swap(arr[left], arr[j])
return j
```
其中,`quickSort`函数是快速排序的主函数,`partition`函数是将数组划分为两个部分的函数。具体实现过程是:首先选定一个基准数(通常是数组的第一个数),然后从左到右扫描整个数组,将小于等于基准数的数放到左边,大于基准数的数放到右边。最后将基准数与最后一个小于等于它的数交换位置,这样基准数左边的数都小于等于它,右边的数都大于等于它。然后再将左右两部分分别进行递归调用。