Question

在数据结构中,给出一组关键字:66,30,78,53,6,18,10,11,20,49,当要求用快速排序法按升序排序.

第一趟排序结果为多少？？取第一个记录哦

Answer 1

简略说一下一趟快速排序思想：
1）从右边right指针处找一个比要比较数（通常是第一个数）小的，找到后放入left指针，left右移一格。

2）从左边left指针找一个比要比较数（通常是第一个数）大的，找到后放入right指针处，right左移一格。
3）当left小于right时，重复1,2步骤。

原序 66, 30, 78, 53,6, 18, 10, 11, 20, 49
第一趟排序为：49, 30, 20, 53, 6, 18, 10, 11, 66, 78
详解：
（1）先把数组第一个数66用变量暂存，从右边开始，49小于66，把49放入第一个位置，left自加一后指30.
（2）从左边left处开始找，找到78大于66，把78放入right指向处（原本49的位置），right自减一后指向20处。
（3）右边20小于66，放入原本78那个位置。
（4）左边53，6,18,10,11均小于66，直到left与right相等，处于原本20所在位置，把66放入。

追问

这个是个答卷题。。。这样怎么能得分啊》？？

追答

直接写第一趟排序答案，49, 30, 20, 53, 6, 18, 10, 11, 66, 78

追问

在数据结构中，一个有序列表 12、34、45、56、68、76、83、99、100，现在要在该表中查找值为key=45元素，要求用半折查找法，用指针low,high,mid表示出查找的过程？这个您会做么？拜托，拜托

追答

1）low=0,high=8,mid=(low+high)/2=4,找到68，比45大，high=mid-1=3.
2) low=0,high=3,mid=(low+high)/2=1,找到34,比45小，low=mid+1=2.
3) low=2,high=3,mid=(low+high)/2=2,找到45.