|
希尔排序，相同增量的数为一组进行简单插入排序。步长为4也就是相隔的增量为4.第一组为QQR，剩余的为ADH，CFM，SXY。组内排序可以得出答案。快速排序，相信大家都很熟悉了，只是以一个key为基准这里选中了第一个元素，key左边的元素都不大于key,右边的都大于key。从后往前找第一个不大于key的元素，找到后从前往后找第一个大于key的，知道两个指针相遇。结果也很好得出。 三、其他方向简答题(共2题，每题20分)，选作题，不计入总分) 2 A，B两个整数集合，设计一个算法求他们的交集，尽可能的高效。 我的想法感觉比较笨，第一种：先对其中的一个进行排序，然后从一个未排序的集合中取出一个元素用折半查找的方法查找集合中有没有这个元素。相应的时间复杂度为：排序n*logn，查找的时间复杂度也为n*logn，整体上也是n*logn。这个时间复杂有待商榷的地方在于，排序的时间复杂度，若选取堆排序则平均复杂度为n*logn，如果选用其他的排序方法最坏的情况下不一定是这个复杂度。 第二种方法：利用Hash表，先将A构造成一个Hash表，然后将B看做是待查找元素从Hash表里查找。Hash表的查找的时间复杂最坏为O(C)C为平均查找长度，构造Hash表的时间复杂度也是常数级别的，平均为O(C)。 （责任编辑：职场达人） |
