partition算法举例
时间: 2023-10-22 18:22:14 浏览: 36
下面是一个简单的例子,演示如何使用partition算法将一个数组分成两个部分,其中一个部分包含所有的偶数,另一个部分包含所有的奇数。
假设我们有以下数组:
```
arr = [5, 8, 3, 6, 1, 4, 9, 7, 2]
```
我们希望将这个数组分成两个部分,一个部分包含所有的偶数,另一个部分包含所有的奇数。
首先,我们选择一个基准值(pivot),通常是数组中的中间元素。在这个例子中,我们选择4作为基准值。
接下来,我们遍历数组,并将所有小于或等于基准值的元素放到数组的左侧,所有大于基准值的元素放到数组的右侧。这个过程可以使用两个指针,一个指向数组的左侧,另一个指向数组的右侧,交换指针所指向的元素,直到指针相遇为止。
在这个例子中,我们可以使用以下代码实现partition算法:
```
def partition(arr, low, high):
pivot = arr[(low + high) // 2]
i = low - 1
j = high + 1
while True:
i += 1
while arr[i] < pivot:
i += 1
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
arr = [5, 8, 3, 6, 1, 4, 9, 7, 2]
partition(arr, 0, len(arr) - 1)
```
这个代码的输出应该是4,这意味着在arr[4]处,数组被分成了两个部分,左侧部分包含所有的奇数,右侧部分包含所有的偶数。