若一组记录的关键字为146,79,56,38,40,84),利用快速排序的方法,以第一个记录为基准得到的第一次划分结果为
时间: 2024-03-12 13:50:26 浏览: 137
快速排序方法
初始状态下,以第一个记录 146 为基准,左右指针分别指向数列的首尾:
```
146, 79, 56, 38, 40, 84
^ ^
left right
```
首先右指针从右向左扫描,寻找第一个小于基准数的数,找到数值为 84 的记录,右指针停止移动。接着左指针从左向右扫描,寻找第一个大于基准数的数,找到数值为 79 的记录,左指针停止移动。此时交换左右指针所指的记录:
```
146, 79, 56, 38, 40, 84
^ ^
left right
```
接着右指针继续向左移动,寻找下一个小于基准数的数,找到数值为 40 的记录,右指针停止移动。左指针继续向右移动,寻找下一个大于基准数的数,找到数值为 56 的记录,左指针停止移动。再次交换左右指针所指的记录:
```
146, 56, 40, 38, 79, 84
^ ^
left right
```
右指针继续向左移动,寻找下一个小于基准数的数,找到数值为 38 的记录,右指针停止移动。左指针继续向右移动,寻找下一个大于基准数的数,此时左指针已经扫描到了右指针的位置,扫描结束。
最后交换基准数和左指针所指的记录:
```
38, 56, 40, 146, 79, 84
^
left
```
第一次划分的结果为基准数 146 左侧的数均比 146 小,右侧的数均比 146 大:
```
38, 56, 40, 146, 79, 84
|
基准数 146
```
阅读全文