快速排序（快速排序算法）

本文目录一览：

• 1、快速排序
• 2、快速排序法
• 3、快速排序的详细过程

快速排序

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

快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。

(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理

(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

下面通过一个例子介绍快速排序算法的思想，假设要对数组a[10]={6，1，2，7，9，3，4，5，10，8}进行排序，首先要在数组中选择一个数作为基准值，这个数可以随意选择，在这里，我们选择数组的第一个元素a[0]=6作为基准值，接下来，我们需要把数组中小于6的数放在左边，大于6的数放在右边，怎么实现呢？

我们设置两个“哨兵”，记为“哨兵i”和“哨兵j”，他们分别指向数组的第一个元素和最后一个元素，即i=0，j=9。首先哨兵j开始出动，哨兵j一步一步地向左挪动（即j–），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。

最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。此时就需要交换i和j指向的元素的值。

交换之后的数组变为a[10]={6，1，2，5，9，3，4，7，10，8}：

第一次交换至此结束。接下来，由于哨兵i和哨兵j还没有相遇，于是哨兵j继续向前，发现比6小的4之后停下；哨兵i继续向前，发现比6大的9之后停下，两者再进行交换。交换之后的数滑伏陵组变为a[10]={6，1，2，5，4，3，9，7，10，8}。

第二次交换至此结束。接下来，哨兵j继续向前，发小比6小的3停下来；哨兵i继续向前，发现i==j了！！！信戚于是，这一轮的探测就要结束了，此时交换a[i]与基准的值，数组a就以6为分界线，分成了小于6和大于6的左右两部分：a[10]={3，1，2，5，4，6，9，7，10，8}。

至此，第一轮快速排序完全结束，接下来，对于6左边的半部分3，1，2，5，4，执行以上过程；对于6右边的半部分9，7，10，8，执行以上过程，直到不可拆分出新的子序列为止。最终将会得到这样的序列：1 2 3 4 5 6 7 8 9 10，到此，排序完全结束。

快速排序的一次划分算法从两头交替搜索，直到low和hight重合，因此其时间复杂度是O(n)；而整个快速排序算法的时间复杂度与划分的趟数有关。

理想的情况是，每次划分所选择的中间数恰好将当前序列几乎等分，经过log 2 n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog 2 n)。

最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n 2 )。

为改善最坏情况下的时间性能，可采用其他方法选取中间数。通常采用“三者值取中”方法，即比较H-r[low].key、H-r[high].key与H-r[(low+high)/2].key，取三者中关键字为中值的元素为中间数。

可以证明，快速排序的平均时间复杂度也是O(nlog 2 n)。因此，该排序方法被认为是目前最好的一种内部排序方法

快速排序法

常见的快速排序方法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。这些排序方法的原理和实现方式各不相同，但其核心思想都是通过比较和交换数据的位置来达到排序的目的。

冒泡排序是一种简单的排序方法，它的主要思想是通过不断交换相邻元素的位置来将较大的元素逐步“浮”到数列的末端，从而实现排序。选择排橡旁缓序则是通过不断选择数列中的最小值，并将其放到数列的起始位置，再对剩余的未排序部分进行同样的操作，从而实现排序。

插入排序则是通过将未排序元素逐个插入到已排序序列中的适当梁模位置，从而实现排序。快速排序是一种高效的排序方法，它的核心思想是通过分治策略将待排启困序序列分成两个子序列，然后对子序列分别排序，最终合并成有序序列。归并排序也是一种常用的排序方法，其思想是将待排序序列分成若干个子序列，分别排序，再将已排序的子序列合并成一个有序序列。

除了上述几种排序方法外，还有一些其他的排序方法，例如希尔排序、堆排序、基数排序等。这些排序方法各具特点，适用于不同的排序场景。在实际编程中，我们需要根据具体的需求选择合适的排序方法来实现排序操作。

快速排序的详细过程

快速排序的详细过程如下：

快速排序是指寻找一个参考数值，将小于参考掘袭数值的数放橘散昌在数组的左边，将大于参考数值的数放在数组的右边。具体的实现方法：

1、随机选取数组中的一个index，其数值作为参考数值。将参考数值保存，并与数组的第一个位置的数值进行交换；从数组的左边和右边分别开始判断。

2、当右边的数值满足大于圆扒参考数值后退一位；当右边的数值不满足大于参考数值，将当前在数值放入左边当前指向的位置，左边前进一位；紧接着判断左边的数值满足小于参考数值往后进一位，左边的数值不满足小于参考数值，将当前数值放入右边当前指向位置，右边前进一位。

3、直到左右指向的位置重合，结束上述判断，将参考数值放入重合点，返回 重合点的index。

4、以重合点出为分界线，分为两个子数组。子数组重复进行上述判断。

5、直到传入函数的数组大小为1，退出递归调用。

快速排序是指通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。

快速排序的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于快速排序算法、快速排序的信息别忘了在云尚网络www.ysfad.net进行查找喔。