<h1 id="一算法介绍">一、算法介绍

快速排序：快速排序的基本思想是通过一次排序将等待的记录分成两个独立的部分，其中一部分记录的关键字小于另一部分的关键字。C部分的快速排序一直持续到整个序列被排序。

任取一个元素 (如第一个) 为中心
提出所有小于它的元素，并将大于它的元素放回，形成左右两个子表。
为每个子表重新选择中心元素，并根据此规则进行调整，直到每个子表只剩下一个元素

①每次行程的子表是由两端到中间的交替近似形成的。

②由于每个子表的操作在每次行程中都是相似的，所以可以使用递归算法。

设置两个指针i，j，首先在序列中选择一个.temp，并将数字J点与temp进行比较。如果它大于温度，它将减少1。如果它小于TEMP，则应该取高于当前位置J的值。

最好：划分后，左侧右侧子序列的长度相同,

最坏：从小至大，递归树变成一棵树。每个分区只能得到一个对象的子序列小于前一个。它必须通过n-1次来定位所有对象，第二次需要通过n-i键代码比较来找到第二个对象的位置。

?

如果所有可能的置换的概率相同，则优选最佳情况和最坏情况平均值。

时间效率：O(nlog2n) —每趟确定的元素呈指数增加
空间效率：O（log2n）—递归要用到栈空间
稳 定 性： 不稳定 —可选任一元素为支点

从上面的描述中可以看出，快速排序是通过枢轴点来回交换的，因此快速排序的分类次数与初始序列有关。
因此，选择快速分选的关键点非常重要，因为它关系到分选的效率。

取前或后法：序列中的第一个或最后一个元素用作基准，如果输入序列（上面的数组）是随机的，则处理时间是可接受的。如果数组已经被排序，那么分区就是一个非常糟糕的分区。由于每个分区只能减少要排序的序列，所以这是最坏的情况，并且时间复杂度为_(n^2)。此外，输入数据排序或部分排序是很常见的。因此，使用第一个元素作为中心元素是非常糟糕的。

随机选取基准：
这是一个相对安全的策略。因为枢轴的位置是随机的，所以得到的分割不会总是产生不好的分割。当整个阵列相同时，仍然是最坏的情况，并且时间复杂度为O（n2）。因此，对于大多数输入数据，随机快速排序可以达到O（nlogn）的预期时间复杂度。

三数取中法：在快速排队过程中，每次我们以一个元素作为支点值，用该数将序列分成两部分。本文采用三位数法，即以左、中、右三位数作为关键值，然后进行排序。显然，三位数的中值分割方法消除了预排序输入的不良情况，并将快速队列的比较次数减少了大约14%。

1、最优情况

在最佳情况下，分区平均每次分区。如果对n个关键字进行排序，则递归树的深度为[log2n]+1([x]表示不大于x的最大整数)。也就是说，只需要2次递归日志，所需的时间是t（n）。第一个分区应该扫描整个阵列一次。n次比较。然后，获得的枢轴将阵列分成两部分，因此每个部分需要T(n/2)时间(注意，最佳情况是，所以分成两半)。结果，作为连续划分的结果，作出了以下不等式推断：
这表明，在最佳情况下，快速排序算法的时间复杂度为O（nLogn）。

2.最坏情况

然后看看快速调度的最坏情况，当要排序的序列是正序或反序时，并且每个分区只产生比前一个分区少一个记录子序列，注意另一个是空的。如果绘制递归树，则它是倾斜树。此时需要执行n

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!