使用Java与Python实现十大排序算法之快速排序

1. 算法思想 选取一个基准值，将待排序数据分为左（小于基准值）右（大于基准值）两个区间，然后对两个分区的数据进行同样的循环操作，最后便可得到一组有序数据。 2. 算法步骤 选取待排序数据的第一个数值作为分区标准。 遍历数组，将小于标准数的数据移到左边，将大于标准数的数据移到右边，则中间为标准数。 对标准数左右两个子序列分别进行（1）和（2）步的操作。 当左右子序列的长度均小于或等于1时，排序完成。 3. 算法分析 如果选取的标准数为待排序数组的中位数，即每次划分后的左右子序列长度基本一致，则时间复杂度为 $O(nlog_2n)$，为最好的情况。 如果待排序数组是逆序，第一趟选取的标准数为待排序数组的最大值，经过 n-1 次比较和移动后，得到一个n-1个元素的左子序列;第二趟选取的标准数依旧是待排序子序列的最大值，经过n-2次比较和移动后，得到一个n-2个元素的左子序列。以此类推，则总操作次数为： $$C_{max}=\sum_{i = 1}^{n-1}{(n-i)}=\frac{n(n-1)}{2}\approx n^2$$ 这是最坏的情况。因此快速排序的平均时间复杂度为$O(n^