• 快速排序一般要比其他排序算法快得多；

原理

• 首先，随机选择一个分切元素（中间点）（一般是 数组/子数组的第一个元素 sample[low]）；
• 交换分切元素两边的元素，使得分切元素左边的元素都比它小，右边元素都比它大（这样就相当于排序了一个元素 -- 分切元素）；
• 把分切元素左右两边当成两个子数组，递归执行以上过程，递归结束，数组排序完成

代码

快速排序的代码分为两部分：切分函数 和 递归（调用切分函数的）函数

切分函数

目标

就是要使切分元素，左边的元素都小于切分元素，右边的元素都大于切分元素

切分函数

实现过程

• 切分元素：切分元素选择数组（或子数组）的第一个元素
• 交换：交换需要用到两个指针
  • 左指针初始时为数组的第二个元素（第一个元素是切分元素），向右移动 ，直到找到一个值大于切分元素时停下。
  • 右指针初始为数组的最后一个元素，不断向左移动，直到遇到一个比切分元素小或等于（）的，停下
  • 等于切分元素按小于处理
• 此时会有两种情况：
  • 两个指针还未相遇：交换左右指针所指元素，并继续前进
  • 两个指针已经相遇（左指针的索引 i >= 右指针的索引 j）：属于已经有序的正常情况，退出指针移动操作
• 为了避免所有元素都小于（或大于）切分元素的情况，应限制指针的索引 -- i, j 避免无限移动，导致越界
• 最后，将 切分元素与索引 j 的元素交换（因为两指针相遇后，j 已经在中间点的左边，该元素比切分元素小）

partition 切分函数

#!/usr/bin/python3

class QuickSort:
    def exch(self, sample, i, j):
        t = sample[i]
        sample[i] = sample[j]
        sample[j] = t

    def partition(self, sample, low, high):
        # 切分元素: v
        # 左指针索引：i
        # 右指针索引：j

        v = sample[low]
        i = low + 1
        j = high

        while True:
            while sample[i] <= v:
                i += 1
                if i > high: break

            while sample[j] > v:
                j -= 1
                if j < (low + 1): break

            if i >= j:
                break
            else:
                self.exch(sample, i, j)
        self.exch(sample, low, j)
        return j

递归（调用切分函数的）函数

两个子数组

递归调用函数的作用是不断的地将根据切分元素的位置，将大数组分成两个小数组，这个切分元素的位置最后是和右指针的索引 j 交换，所以我们可以通过切分函数获得

值得注意的是：并不是新建一个子数组并传给切分函数，而是在本来的大数组上逻辑（通过索引 low , j, high）地划分子数组

代码

    def sort(self, sample, low, high):
        # j 为切分元素的位置

        if low >= high:
            return

        j = self.partition(sample, low, high)
        self.sort(sample, low, j - 1)
        self.sort(sample, j + 1, high)

---

测试

if __name__ == '__main__':
    import random

    def show(target, prompt=''):
        print(prompt, end='')
        for  elem in target:
            print(elem, end=' ')
        print()

    sample = input().split()
    show(sample, 'Origin: ')
    sort = QuickSort()
    random.shuffle(sample) # 为了保证切分元素（我们选数组的第一个元素作为切分元素）是随机的，我们先将数组打乱，
    sort.sort(sample, 0, len(sample) - 1)
    show(sample, 'Result: ')

---

/mnt/f/python $ ./quickSort.py < data.txt
Origin: D G A B E C F
Result: A B C D E F G
/mnt/f/python $
/mnt/f/python $ ./quickSort.py < bigData.txt
Origin: H M F N A P N G M G Q Y Q V P T Z Z F Z Z U Q W C D Z E X H M Z K D C B K P L E X F O I O A N F X M X U T V I M T W W A P L O L H W Y W J W H C M P K U I D P B O G R K E V G L F W N U C P T J R M Y H
Result: A A A B B C C C C D D D E E E F F F F F G G G G H H H H H I I I J J K K K K L L L L M M M M M M M N N N N O O O O P P P P P P P Q Q Q R R T T T T U U U U V V V W W W W W W W X X X X Y Y Y Z Z Z Z Z Z
/mnt/f/python $

Python 随机生成字母

In [1]: import string, random

In [2]: for i in range(5):
   ...:     print(random.choice(string.ascii_uppercase), end=' ')
   ...: else:
   ...:     print()
   ...:
L R X G W

In [3]: string.ascii_letters
Out[3]: 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'

In [4]: string.ascii_uppercase
Out[4]: 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

In [5]: string.ascii_lowercase
Out[5]: 'abcdefghijklmnopqrstuvwxyz'

In [6]:

Github 完整代码 -- QuickSort.py