快速排序算法

基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

代码实现

Python实现

class QuickSort:

    @staticmethod
    def sort(array):
        # 递归
        return QuickSort.__sort(array, 0, len(array) - 1)

    @staticmethod
    def __sort(array, start, end):
        print("start:%s, end:%s->%s" % (start, end, array))
        # i,j用于遍历
        i, j = start, end
        # 标杆
        pivot = array[start]
        while i < j:
            # 先从j开始（右边）
            while i < j and array[j] > pivot:
                j = j - 1
            # 后从i开始（左边）
            while i < j and array[i] < pivot:
                i = i + 1
            # 如果相等并且小于
            if array[i] == array[j] and i < j:
                i = i + 1
            else:
                # 置换
                array[i], array[j] = array[j], array[i]

        # 递归处理
        if i - 1 > start:
            array = QuickSort.__sort(array, start, i - 1)
        if j + 1 < end:
            array = QuickSort.__sort(array, j + 1, end)

        return array


def main():
    array = [5, 3, 2, 1, 9, 8, 4, 0]
    result = QuickSort.sort(array)


if __name__ == '__main__':
    main()

输出结果

start:0, end:7->[5, 3, 2, 1, 9, 8, 4, 0]
start:0, end:4->[0, 3, 2, 1, 4, 5, 8, 9]
start:1, end:4->[0, 3, 2, 1, 4, 5, 8, 9]
start:1, end:2->[0, 1, 2, 3, 4, 5, 8, 9]
start:6, end:7->[0, 1, 2, 3, 4, 5, 8, 9]

附录

快排的时间复杂度有几种情况

平均情况	最好的情况	最坏的情况
$O(nlog_2n)$	$O(nlog_2n)$	$O(n^2)$

快排的空间复杂性为$O(log_2n)$

博文

理解快速排序算法