这是一个某年的研究生入学考试数据结构算法题。
需求：把一个数组（列表）中的所有奇数放在所有偶数的前面，要求时间复杂度为O(n)，不申请额外的数据空间。
请暂停，思考后再继续...
3
2
1
大脑在思考：
要求时间复杂度为O(n)，所以应该考虑使用一次遍历的方法。处理的过程基本是“奇数往前走，偶数向后移”。
要求不开辟新的存储空间，那么考虑在原数组上交换数值来实现功能。
假设我们有两个侦探，一个叫left大侦探，一个叫right大侦探，让他们两分别从数组的头部和尾部开始巡视。
left侦探负责从头部逐一清点奇数，如果遇到一个偶数，就让他跟right侦探商量，交换一个奇数过来，如果right临时没有遇到奇数，left就等待；
right侦探负责从尾部逐一清点偶数，如果遇到一个奇数，就让他跟left侦探商量，交换一个偶数过来，如果left临时没有遇到偶数，right就等待。
当他俩相遇的时候[❤]，就是OK的时候了。
Python实现：
def sort_by_odd_even(num_list): left_index = 0 right_index = len(num_list)-1 while left_index < right_index: # 判断左指针指向的数是否是奇数 if num_list[left_index] % 2 == 1: # 是奇数，无需交换，left_index指针右移 left_index += 1 left_need_swap = False else: # 不是奇数时，需要交换到右边 left_need_swap = True # 判断右指针指向的数是否是偶数 if num_list[right_index] % 2 == 0: # 是偶数，无需交换，right_index指针左移 right_index -= 1 right_need_swap = False else: # 不是偶数时，需要交换到左边 right_need_swap = True # 当两个索引指向的数都需要交换时，交换两个数，两个指针自动指向下一个数 if left_need_swap and right_need_swap: num_list[left_index], num_list[right_index] = num_list[right_index], num_list[left_index] left_index += 1 right_index -= 1 if __name__ == "__main__": l = [8, 6, 11, 4, 5, 6, 7, 1, 3, 9, 0] sort_by_odd_even(l) print(l) # [9, 3, 11, 1, 5, 7, 6, 4, 6, 8, 0]
