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

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

思路分析：

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

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

def reOrderArray(arr):
    m = len(arr)
    k = 0 # 記錄當前已經排序好的奇數個數
    for i in range(m):
        if arr[i] % 2 == 1:
            j = i
            while j > k:  # 將奇數移到最前面
                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)

排序中間結果：

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