劍指offer-奇偶穩(wěn)定排序

輸入一個整數(shù)數(shù)組，實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對位置不變。

思路分析：

• 排序算法穩(wěn)定
• 時間和控件復雜度盡可能低

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Created by LJ on 2018/9/11

def reOrderArray(arr):
    m = len(arr)
    k = 0 # 記錄當前已經(jīng)排序好的奇數(shù)個數(shù)
    for i in range(m):
        if arr[i] % 2 == 1:
            j = i
            while j > k:  # 將奇數(shù)移到最前面
                temp = arr[j]
                arr[j] = arr[j-1]
                arr[j-1] = temp
                j -= 1
            k += 1 
    print(arr)
if __name__ == '__main__':
    arr = [1,2,5,4,7,6,12]
    reOrderArray(arr)

排序中間結(jié)果：

[1,2,5,4,7,6,12]
[1,5,2,4,7,6,12]
[1,5,7,2,4,6,12]