已知关键字序列{68,39,65,83,74,32,47,56},如果采用快速排序法,选取68为基准元素,则第一趟排序结果为:
时间: 2023-06-12 12:04:31 浏览: 205
在快速排序中,我们选取一个基准元素,将序列分成两个子序列,一个子序列中的元素都小于基准元素,另一个子序列中的元素都大于基准元素,然后对两个子序列分别递归进行快速排序。
在这个问题中,我们选取68作为基准元素。我们从序列的左端开始,找到第一个大于等于基准元素的元素,从序列的右端开始,找到第一个小于基准元素的元素,然后交换这两个元素。在这个过程中,左指针向右移动,右指针向左移动,直到两个指针相遇。然后将基准元素与两个指针相遇的位置交换。这样,序列就被分成了两个子序列,一个子序列中的元素都小于基准元素,另一个子序列中的元素都大于基准元素。
根据这个方法,第一趟排序的结果为:
{56, 39, 65, 47, 74, 32, 83, 68}
首先,左指针指向39,右指针指向56,交换它们,得到{56, 39, 65, 47, 74, 32, 83, 68}。然后,左指针指向65,右指针指向32,交换它们,得到{56, 39, 32, 47, 74, 65, 83, 68}。左指针指向47,右指针指向65,没有交换。左指针指向74,右指针指向68,交换它们,得到{56, 39, 32, 47, 68, 65, 83, 74}。左指针指向83,右指针指向65,没有交换。左指针和右指针相遇,将基准元素68与左指针所指的元素47交换,得到{56, 39, 32, 47, 68, 65, 83, 74}。
现在,序列被分成了两个子序列,左边的子序列{56, 39, 32, 47}中的元素都小于基准元素68,右边的子序列{65, 83, 74}中的元素都大于基准元素68。接下来,我们对这两个子序列分别递归进行快速排序,直到所有子序列的长度都为1。
阅读全文