给定关键字序列{50,12,31,100,81,40,63,18,72,4,28,120,66,38},写出采用快速排序时第一趟排序过程中的数据移动情况。
时间: 2023-09-17 08:11:06 浏览: 67
以第一个元素50为基准,进行一趟快速排序的过程如下:
1. 从右往左扫描序列,找到第一个小于50的元素,将其与50交换位置,序列变为{28,12,31,4,81,40,63,18,72,100,50,120,66,38};
2. 从左往右扫描序列,找到第一个大于50的元素,将其与50交换位置,序列变为{28,12,31,4,38,40,63,18,72,100,81,120,66,50};
3. 继续从右往左扫描序列,找到第一个小于50的元素,将其与50交换位置,序列变为{28,12,31,4,38,40,18,63,72,100,81,120,66,50};
4. 继续从左往右扫描序列,找到第一个大于50的元素,将其与50交换位置,序列变为{28,12,31,4,38,40,18,50,72,100,81,120,66,63}。
经过这一趟快速排序后,50被放在了序列的中间位置,比50小的元素都在50左边,比50大的元素都在50右边。
阅读全文