题目

用快速分类算法给出数据（49,38,65,97,76,13,27,49）的第一趟排序过程

提问时间：2021-02-28

答案

设置两个指针low和high,分别指向第一个和最后一个记录,设枢轴记录的关键字为pivotkey,初始值为第一个记录,即49,则首先从high所指向的位置起向前搜索找到第一个小于pivotkey的记录,即找到小于49的记录,即倒数第二个记录27,然后将27与pivotkey所指的记录即49交换,得到27,38,65,97,76,13,49,49这个序列,然后从low所指的位置起向后搜索,找到第一个大于pivotkey所指的记录,然后交换,得到27 38 49 97 76 13 65 49,注意,每向后搜索一次,low加1,每向前搜索一次high减1,每一次排序的结束条件是high==low,每次交换的次序都是一次向前,一次向后,交叉进行,且每一次都是从high和low所指的位置向前或向后进行查找,交换,现在high所指的的位置为倒数第二个,即65,向前查找比49小的记录,为13,然后将13和49(pivotkey所指的49)进行交换,得到 27 38 13 97 76 49 65 49,然后从low所指的位置向后查找比pivotkey所指的49大的记录,找到97,进行交换,得到 27 38 13 49 76 97 65 49由于现在high指向倒数第三个记录(97),向前查找,由于76>49,仍然向前,到达pivotkey所指的49的位置,可是low已经指向这个49,此时high==low,第一次排序结束,得到27 38 13 49 76 97 65 49这个序列.
不知道这样说是否满意?