快速排序的分治方法

㈠ 快排是什么

快速排序

快速排序是一种高效的排序算法，基于分治法的思想。它将待排序的数组或列表分割成若干个子序列，对每个子序列进行排序，最终合并为有序的序列。

以下是关于快速排序的详细解释：

1. 基本思想：快速排序的核心是分治策略。它选择一个基准元素，将数组分为两部分，使得比基准元素小的元素位于其左侧，比基准元素大的元素位于其右侧。然后，对这两部分递归地进行快速排序，最终完成整个数组的排序。

2. 操作过程：在快速排序中，通常选择数组的第一个元素作为基准值。然后，通过一趟排序将数组划分为两部分。在这之后，递归地对两部分进行快速排序，直到划分的部分只包含一个元素或为空为止。递归结束的条件是整个数组已经被完全排好序。

3. 特点：快速排序是一种不稳定的排序算法，但在实际应用中表现良好。它的平均时间复杂度为O，其中n是待排序数组的元素个数。在最好的情况下，快速排序的性能可以接近O。但在最坏的情况下，性能可能较差。尽管如此，由于其高效性和实现的简单性，快速排序在许多场合仍然是一种首选的排序算法。

通过上述解释，我们可以了解到快速排序是一种基于分治思想的排序算法，通过将待排序序列不断分割并递归地排序子序列来实现整体的排序。

㈡ 按键精灵快速排序（比冒泡更快更有效率的算法）是怎么样的

冒泡排序为O(N^2)，在排序过程中其实是效率较低的。在扫拍卖或者其他需要比拼速度的时候，时间就是金钱~越快越能抢占先机。
今天我们介绍另一种更快更有效率的排序——快速排序，时间复杂度为O(n*logn)。

快速排序的算法思想
快速排序采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。（不要被这个名词吓到了，就是一个用来参照的数，待会你就知道它用来做啥的了）。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3 . 再对左右区间重复第二步，直到各区间只有一个数。

白话讲解算法：

假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边。
方法其实很简单：分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即=10），指向数字。

2014-8-29 13:45 上传
下载附件 (9.51 KB)

首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。

2014-8-29 13:45 上传
下载附件 (9.74 KB)

2014-8-29 13:45 上传
下载附件 (8.13 KB)

现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：
6 1 2 5 9 3 4 7 10 8

2014-8-29 13:45 上传
下载附件 (9.74 KB)

2014-8-29 13:45 上传
下载附件 (8.37 KB)

到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：
6 1 2 5 4 3 9 7 10 8

第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下：
3 1 2 5 4 6 9 7 10 8

2014-8-29 13:45 上传
下载附件 (8.28 KB)

2014-8-29 13:45 上传
下载附件 (10.45 KB)

2014-8-29 13:45 上传
下载附件 (8.48 KB)

到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。

OK，解释完毕。现在基准数6已经归位，它正好处在序列的第6位。

3

1

2

5

4

6

9

7

10

8

此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。
左边的序列是“3 1 2 5 4”。请将这个序列以3为基准数进行调整，使得3左边的数都小于等于3，3右边的数都大于等于3。

3

1

2

5

4

第一次交换完：以3为分界点，拆分了两个序列。左边都比3小，右边都比3大。

2

1

3

5

4

再分别处理3左右的两个序列“2 1”和“5 4”

1

2

3

4

5

这样，最初我们划分的6左侧的序列都已经处理好了~~我们再来处理6右侧的序列

9

7

10

8

以9为基准数，第一次交换完：

9

7

8

10

第二次交换：

8

7

9

10

再交换一次：

7

8

9

10

这样，我们整个序列就排序完毕了

1

2

3

4

5

6

7

8

9

10

快排算法代码实现：

su = "6|1|2|7|9|3|4|5|10|8"
su=Split(su, "|")
L = UBound(su)
Call ks(0, L)
Function ks(L, B)
If L > B Then
Exit Function
End If //判断数组上标下标是否超出范围
i = L
j = B
key =int( su(L) ) //数组第一位提取作为基数
While j>i
While int ( su(j)) >= key and j > i //要先从最右边开始找 找到第一个小于key的数 这里添加的j>i的判断是为了防止j的值不断递减导致下标越界
j = j - 1
Wend
While int (su(i)) <= key and j > i //从最左边开始找 找到第一个大于key的数 （这里的字符串数组需要转换为数值型）
i = i + 1
Wend
If j>i then // 将和基数key对比得到的两个数对换 将大于key的值往右边放 小于key的值往左边放
T = su(i)
su(i) = su(j)
su(j) = T
End If
Wend // 这个 While 循环当i=j 第一轮比较完退出
su(L) = su(i) // 重新设置数组第一个元素为基数
su(i) = key// 基数归位 （排完一轮之后 左边的数<基数<右边的数 那么基数就到了排序中它该在的位置。）
Call ks(L, i - 1)//继续处理左边的数
Call ks(i + 1, B)//继续处理右边的数
End Function
For i = 0 To UBound(su)
TracePrint su(i)
Next

㈢ 快速排序算法

快速排序是对冒泡排序算法的一种改进，同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。

不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端，而快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。

快速排序是基于“分治法”原理实现，所谓分治法就是不断地将原数组序列按照一定规律进行拆分，拆分后各自实现排序直到拆分到序列只剩下一个关键字为止。

快速排序首先选取一个关键字为标志位（关键字的选取影响排序效率），然后将序列中小于标志位的关键字移动至标志位左侧，大于标志位的关键字移动至右侧。一趟比较完成后，整个序列以选取的标志位为界，左侧均小于标志位，右侧均大于关键字。

但左右两侧内部并不是有序的（左右两侧关键字个数也不一定相同）。进而继续将左右两侧分别再以这种方式进行排序，直到将序列拆分的剩余一个关键字为止，整个序列即变成有序。

㈣ 快速排序算法原理与实现

快速排序的原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小。

然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

1、设置两个变量I、J，排序开始的时候I：=1，J：=N；

2、以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；

4、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；

5、重复第3、4步，直到I=J。

(4)快速排序的分治方法扩展阅读：

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是：

1、设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2、以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3、从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]的值赋给A[i]；

4、从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]的值赋给A[j]；

5、重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。