【算法】Python实现快速排序--荷兰国旗问题及奇偶数快速划分

骑猪看日落 2022-04-15 05:59 402阅读 0赞

### 文章目录 ###

*   *   *   *   *  一、序言
                 *  二、”荷兰国旗难题“问题描述
                 *  三、问题分析
                 *  四、荷兰国旗问题Python代码实现
                 *  五、奇偶数快速划分

##### 一、序言 #####

在使用**partition-exchange**排序算法时，如快速排序算法(即使选择了一个好的关键元素pivot values)，我们往往面临一个很尴尬的境地:

当排序对象中有很多重复的元素，**partition-exchange**排序算法表现很不尽如人意。

当所有元素都相等时，这就特别容易理解了。在每次递归中，左边部分是空的(没有元素比关键元素小)，而右边部分只能一个一个递减移动。结果导致耗费了二次方时间来排序相等元素。为了解决这个问题(有时叫做荷兰国旗问题)，我们详细介绍下解决这个问题的方法。

##### 二、”荷兰国旗难题“问题描述 #####

”荷兰国旗难题“是计算机科学中的一个程序难题，它是由Edsger Dijkstra提出的。荷兰国旗是由红、白、蓝三色组成的。  
![img][]

现在有若干个红、白、蓝三种颜色的球随机排列成一条直线。现在我们的任务是把这些球按照红、白、蓝排序。

##### 三、问题分析 #####

将这个问题视为一个数组排序问题，这个数组分为前部，中部和后部三个部分，每一个元素（红白蓝分别对应0、1、2）必属于其中之一。由于红、白、蓝三色小球数量并不一定相同，所以这个三个区域不一定是等分的，也就是说如果我们将整个区域放在\[0,1\]的区域里，由于三色小球之间数量的比不同（此处假设1:2:2），可能前部为\[0,0.2)，中部为\[0.2,0.6)，后部为\[0.6,1\]。我们的思路如下：将前部和后部各排在数组的前边和后边，中部自然就排好了。具体的：  
设置两个标志位begin和end分别指向这个数组的开始和末尾，然后用一个标志位current从头开始进行遍历：

*  1）**若遍历到的位置为0**，则说明它一定属于前部，于是就和begin位置进行交换，然后current向前进，begin也向前进（表示前边的已经都排好了）。
 *  2）**若遍历到的位置为1**，则说明它一定属于中部，根据总思路，中部的我们都不动，然后current向前进。
 *  3）**若遍历到的位置为2**，则说明它一定属于后部，于是就和end位置进行交换，由于交换完毕后current指向的可能是属于前部的，若此时current前进则会导致该位置不能被交换到前部，所以此时current不前进。而同1），end向后退1。

##### 四、荷兰国旗问题Python代码实现 #####

# coding = utf-8
    
    
    def partition(list1, num, left, right):
        """ 荷兰国旗问题 在[left, right]对list1 按照num进行划分 """
        # 初始值
        cur = left  # 初始位置
        less = left - 1
        more = right + 1
    
        while cur < more:
            if list1[cur] < num:
                less += 1
                swap(list1, cur, less)
                cur += 1
            elif list1[cur] > num:
                more -= 1
                swap(list1, cur, more)
            else:
                cur += 1
        return less, more
    
    
    def swap(list1, x, y):
        """ 交换列表中两个元素的位置 """
        list1[x], list1[y] = list1[y], list1[x]
    
    
    if __name__ == '__main__':
        list1 = [9, 2, 1, 4, 1, 3, 7, 8]
        ret = partition(list1, 3, 0, len(list1) - 1)
        print(list1)
        print(ret)

##### 五、奇偶数快速划分 #####

题目：将奇数放在列表左边， 偶数放在列表右边。

# coding = utf-8
    # 奇偶数快速划分
    
    def partition(list1, left, right):
        """ 在[left, right]对list1 进行奇数、偶数划分 """
        # 初始值
        cur = left
        less = left - 1
        more = right + 1
    
        while cur < more:
            if list1[cur] & 1 == 1:  # 判断奇数if list1[cur] % 2 == 1
                less += 1
                swap(list1, cur, less)
                cur += 1
            else:
                cur += 1
        return less + 1, more - 1
    
    
    def swap(list1, x, y):
        """ 交换列表中两个元素的位置 """
        list1[x], list1[y] = list1[y], list1[x]
    
    
    if __name__ == '__main__':
        list1 = [9, 2, 1, 4, 1, 3, 7, 8]
        ret = partition(list1, 0, len(list1) - 1)
        print(list1)
        print(ret)

[img]: /images/20220415/1813a12b361b40c08e767d8dacdac993.png