整数数组的奇偶数分开(小米笔试题)

奇偶数分开


1、 题目要求

 

在一个N个整数数组里面,有多个奇数和偶数,设计一个排序算法,令所有的奇数都在左边。请完成 sort 的代码实现


 

2、题目解析

 

题目只是要求将所有奇数和偶数分开,奇数在左边,偶数在右边,并没有要求奇数有序,偶数也有序,因此,题目并不难

设置两个哨兵,分别从两头向中间巡视,左边的哨兵发现的偶数去和右边哨兵发现的奇数做交换,交换以后继续巡视

需要特别注意的是,每一次做交换前,都要判断两个哨兵的位置是否合理


 

3、示例代码

 

# coding=utf-8
lst = [2, 1, 5, 6, 7, 9, 12, 34, 13]


def sort(lst):
    start = 0
    end = len(lst) - 1
    while start < end:
        if lst[start] % 2 == 0:
            while lst[end]%2 == 0:
                end -= 1

            # 这一步的判断一定不能少
            if start < end:
                tmp = lst[start]
                lst[start] = lst[end]
                lst[end] = tmp

        start += 1

sort(lst)
print lst