【Python】合并两个有序数组为一个有序的大数组（时间复杂度最低）
思路
思路一： 先把两个数组放到一个新的数组中，再排序。 但是这样的没体现任何算法，这里考的不是快速排序等排序算法。关键应该是如何利用有序这个已知条件。 思路二： 按位循环比较两个数组，较小元素的放入新数组，下标加一（注意，较大元素对应的下标不加一），直到某一个下标超过数组长度时退出循环 假设两个源数组的长度不一样，那么假设其中短的数组用完了，即全部放入到新数组中去了，那么长数组中剩下的那一段就可以直接拿来放入到新数组中去了。
代码
def merge_sorted_lists(aList, bList):
result = []
length_of_aList = len(aList)
length_of_bList = len(bList)
i =
0
j =
0
while i < length_of_aList
and j < length_of_bList:
if aList[i] <= bList[j]:
result.append(aList[i])
i +=
1
else:
result.append(bList[j])
j +=
1
if i < length_of_aList:
result.extend(aList[i:])
if j < length_of_bList:
result.extend(bList[j:])
return result
a = [
1,
3,
6,
10]
b = [
0,
4,
5,
7,
10,
11,
14,
100]
print merge_sorted_lists(a, b)
结果
[0, 1, 3, 4, 5, 6, 7, 10, 10, 11, 14, 100]
