快速排序算法

快速排序算法是一个典型的荷兰国旗问题。那什么是荷兰国旗问题呢，就是有三种旗子红，白，黑。 三种旗子在数组中乱序的，现在的问题是要把相同颜色国旗放到一起应该怎么做。

比如说 0 -表示红色， 1 -表示白色， 2-表示黑色。

有国旗的排列如下： 1， 0， 2， 1， 2， 0。

期望把相同颜色的国旗放到一起： 0， 0， 1， 1， 2， 2

那就设定两个指针，一个指向头 i， 一个指向尾 j。 然后 i向后移动，j 向前移动。 遇到红色的旗子放到前面，遇到黑色的旗子放到后面。

快速排序就是按这种思路来，指定一个元素为白色的旗，小于该元素的值认为是红色，大于该元素的值认为是黑色。

快速排序关键点：

1. 指定一个数，然后把数据分成两部分，小于该数的放到该数的前面，大于该数的放到该数的后面。
2. 前半部分的数据和后半部分的数据，按同样的方法分成两部分。

举个例子来说明一下过程， 数组：6,7,4,3,8来举例看一下一趟快速排序的过程。

开始的时候指定 pivot = 0， i = 0， j = 4

1. 从后面开始比较 6,7,4,3,8，6 和8进行比较， 6 小于8， 不需要进行调换，j = j - 1
2. 此时6,7,4,3,8， 6 和3进行比较， 3 小于6， 3和6换一个位置： 3,7,4,6,8
3. 此时i = i + 1， 有3,7,4,6,8， 7 和6 进行比较， 7 大于6, 6和7换一个位置：3,6,4,7,8
4. 此时j = j - 1，有3,6,4,7,8， 6 和4进行比较，6大于4, 6和4 换一个位置：3,4,6,7,8
5. 此时i = i + 1， 此时有3,4,6,7,8
6. 这个时候i， j都来到了同一个位置， 此时数据被分成了3,4 和 7，8两部分。

剩下的部分重复上面的过程直到单个只有单个元素。

看一下用python是如何实现的

def quick_sort(elments, low, high):
    if low < high:
        pivot = low
        i = low
        j = high
        while i < j:
            while i < j and elments[pivot] < elments[j]:
                j = j - 1
            elments[pivot], elments[j] = elments[j], elments[pivot]

            while i < j and elments[pivot] > elments[i]:
                i = i + 1
            elments[pivot], elments[i] = elments[i], elments[pivot]

        quick_sort(elments, low, i - 1)
        quick_sort(elments, i + 1, high)

if __name__ == '__main__':
    arr = [6,7,4,3,8]
    quick_sort(arr, 0, len(arr) - 1)
    print(arr)

运行后输出结果：

[3, 4, 6, 7, 8]

更多内容可以关注公众号： IT技术漫漫谈