排列算法的算法描述和实现

❶ 各种排序算法实现和比较

1、 堆排序定义
n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。
2、大根堆和小根堆
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。
注意：
①堆中任一子树亦是堆。
②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。
3、堆排序特点
堆排序(HeapSort)是一树形选择排序。
堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。
4、堆排序与直接插入排序的区别
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
5、堆排序
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
（1）用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。
（2）大根堆排序算法的基本操作：
① 初始化操作：将R[1..n]构造为初始堆；
② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
注意：
①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
（3）堆排序的算法：
void HeapSort(SeqIAst R)
{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
int i；
BuildHeap(R)； //将R[1-n]建成初始堆
for(i=n;i1；i--){ //对当前无序区R[1..i]进行堆排序，共做n-1趟。
R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //将堆顶和堆中最后一个记录交换
Heapify(R，1，i-1)； //将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质
} //endfor
} //HeapSort
（4） BuildHeap和Heapify函数的实现
因为构造初始堆必须使用到调整堆的操作，先讨论Heapify的实现。
① Heapify函数思想方法
每趟排序开始前R[l..i]是以R[1]为根的堆，在R[1]与R[i]交换后，新的无序区R[1..i-1]中只有R[1]的值发生了变化，故除R[1]可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是R[low..high]时，只须调整以R[low]为根的树即可。
"筛选法"调整堆
R[low]的左、右子树(若存在)均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆性质，以R[low]为根的树已是堆，无须调整；否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key，R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为"筛选法"。
具体的算法
②BuildHeap的实现
要将初始文件R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。
显然只有一个结点的树是堆，而在完全二叉树中，所有序号 的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为 ， -1，…，1的结点作为根的子树都调整为堆即可。
具体算法。
5、大根堆排序实例
对于关键字序列(42，13，24，91，23，16，05，88)，在建堆过程中完全二叉树及其存储结构的变化情况参见。
6、 算法分析
堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1)，
它是不稳定的排序方法。

❷ 八大经典排序算法原理及实现

该系列文章主要是记录下自己暑假这段时间的学习笔记，暑期也在实习，抽空学了很多，每个方面的知识我都会另起一篇博客去记录，每篇头部主要是另起博客的链接。

冒泡排序算法应该是大家第一个接触的算法，其原理都应该懂，但我还是想以自己的语言来叙述下其步奏：

按照计算时间复杂度的规则，去掉常数、去掉最高项系数，其复杂度为O(N^2)
冒泡排序及其复杂度分析

空间复杂度就是在交换元素时那个临时变量所占的内存

给定一个整数序列{6,1,2,3,4},每完成一次外层循环的结果为：

我们发现第一次外层循环之后就排序成功了，但是还是会继续循环下去，造成了不必要的时间复杂度，怎么优化？

冒泡排序都是相邻元素的比较，当相邻元素相等时并不会交换，因此冒泡排序算法是稳定性算法

插入排序是对冒泡排序的一种改进

插入排序的思想是数组是部分有序的，再将无序的部分插入有序的部分中去,如图：
（图片来自 这里 ）

空间复杂度就是在交换元素时那个临时变量所占的内存

插入排序的优化，有两种方案：

文章后面会给出这两种排序算法

由于插入排序也是相邻元素的比较，遇到相等的相邻元素时不会发生交换，也不会造成相等元素之间的相对位置发生变化

其原理是从未排序的元素中选出最小值(最大值)放在已排序元素的后面

空间复杂度就是在交换元素时那个临时变量所占的内存

选择排序是不稳定的，比如 3 6 3 2 4，第一次外层循环中就会交换第一个元素3和第四个元素2，那么就会导致原序列的两个3的相对位置发生变化

希尔排序算是改良版的插入排序算法，所以也称为希尔插入排序算法

其原理是将序列分割成若干子序列（由相隔某个 增量 的元素组成的），分别进行直接插入排序；接着依次缩小增量继续进行排序，待整个序列基本有序时，再对全体元素进行插入排序，我们知道当序列基本有序时使用直接插入排序的效率很高。
上述描述只是其原理，真正的实现可以按下述步奏来：

希尔排序的效率取决于 增量值gap 的选取，这涉及到数学上尚未解决的难题，但是某些序列中复杂度可以为O(N 1.3)，当然最好肯定是O(N)，最坏是O(N 2)

空间复杂度就是在交换元素时那个临时变量所占的内存

希尔排序并不只是相邻元素的比较，有许多跳跃式的比较，难免会出现相同元素之间的相对位置发生变化，所以希尔排序是不稳定的

理解堆排序，就必须得先知道什么是堆？

二叉树的特点：

当父节点的值总是大于子结点时为 最大堆 ；反之为 最小堆 ，下图就为一个二叉堆

一般用数组来表示堆，下标为 i 的结点的父结点下标为(i-1)/2；其左右子结点分别为 (2 i + 1)、(2 i + 2)

怎么将给定的数组序列按照堆的性质，调整为堆？

这里以建立最小堆为示例，

很明显对于其叶子结点来说，已经是一个合法的子堆，所以做堆调整时，子节点没有必要进行，这里只需从结点为A[4] = 50的结点开始做堆调整，即从（n/2 - 1）位置处向上开始做堆调整：

由于每次重新恢复堆的时间复杂度为O(logN)，共N - 1次重新恢复堆操作，再加上前面建立堆时N / 2次向下调整，每次调整时间复杂度也为O(logN)，二次操作时间相加还是O(N logN)。故堆排序的时间复杂度为O(N * logN)。

空间复杂度就是在交换元素时那个临时变量所占的内存

由于堆排序也是跨越式的交换数据，会导致相同元素之间的相对位置发生变化，则算法不稳定。比如 5 5 5 ,堆化数组后将堆顶元素5与堆尾元素5交换，使得第一个5和第三个5的相对位置发生变化

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

快速排序在应该是大家经常看到、听到的算法，但是真正默写出来是有难度的。希望大家看了下面 挖坑填数 方法后，能快速写出、快速排序。

其原理就这么几句话，但是现实起来并不是这么简单，我们采取流行的一种方式 挖坑填数分治法

对于序列： 72 6 57 88 60 42 83 73 48 85

数组变为： 48 6 57 88 60 42 83 73 88 85
再重复上面的步骤，先从后向前找，再从前向后找：

数组变为： 48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了

空间复杂度，主要是递归造成的栈空间的使用:

快速排序的优化主要在于基准数的选取

快速排序也是跨越式比较及交换数据，易导致相同元素之间的相对位置发生变化，所以快速排序不稳定

前面也说了二分查找排序是改进的插入排序，不同之处在于，在有序区间查找新元素插入位置时，为了减少比较次数提高效率，采用二分查找算法进行插入位置的确定
具体步骤，设数组为a[0…n]：

二分查找插入位置，因为不是查找相等值，而是基于比较查插入合适的位置，所以必须查到最后一个元素才知道插入位置。
二分查找最坏时间复杂度：当2^X>=n时，查询结束，所以查询的次数就为x，而x等于log2n（以2为底，n的对数）。即O(log2n)
所以，二分查找排序比较次数为：x=log2n
二分查找插入排序耗时的操作有：比较 + 后移赋值。时间复杂度如下：

二分查找排序在交换数据时时进行移动，当遇到有相等值插入时也只会插入其后面，不会影响其相等元素之间的相对位置，所以是稳定的

白话经典算法排序
冒泡排序选择排序
快速排序复杂度分析
优化的插入排序

❸ 排序算法是怎样的

一、背景介绍

在计算机科学与数学中，排序算法（Sorting algorithm）是一种能将一串资料依照特定排序方式进行排列的一种算法。

最常用到的排序方式是数字顺序以及字典顺序。

有效的排序算法在一些算法（例如搜寻算法与合并算法）中是重要的， 如此这些算法才能得到正确解答。

排序算法也用在处理文字资料以及产生人类可读的输出结果。

基本上，排序算法的输出必须遵守下列两个原则：

1、输出结果为递增序列（递增是针对所需的排序顺序而言）；

2、输出结果是原输入的一种排列、或是重组；

虽然排序算法是一个简单的问题，但是从计算机科学发展以来，在此问题上已经有大量的研究。 更多的新算法仍在不断的被发明。

二、知识剖析

查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。 所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。

一般在面试中最常考的是快速排序和冒泡排序，并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。除此之外，还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。

三、常见的几种算法：

冒泡算法、选择排序、插入排序、希尔排序、归并排序、快速排序

算法的特点：

1、有限性：一个算法必须保证执行有限步之后结束。

2、确切性： 一个算法的每一步骤必须有确切的定义。

3、输入：一个算法有零个或多个输入，以刻画运算对象的初始情况，所谓零个输入是指算法本身给定了初始条件。

4、输出：一个算法有一个或多个输出。没有输出的算法毫无意义。

5、可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

❹ 排序算法总结

排序算法是什么?有多少种?排序算法总结又是怎样?以下是为您整理的排序算法总结，供您参考!

【排序算法总结】

排序算法：一种能将一串数据依照特定的排序方式进行排列的一种算法。

排序算法性能：取决于时间和空间复杂度，其次还得考虑稳定性，及其适应的场景。

稳定性：让原本有相等键值的记录维持相对次序。也就是若一个排序算法是稳定的，当有俩个相等键值的记录R和S，且原本的序列中R在S前，那么排序后的列表中R应该也在S之前。

以下来总结常用的排序算法，加深对排序的理解。

冒泡排序

原理

俩俩比较相邻记录的排序码，若发生逆序，则交旅派配换;有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。

性能

时间复杂度为O(N^2)，空间复杂度为O(1)。排序是稳定的，排序比较次数与初始序列无关，但交换次数与初始序列有关。

优化

若初始序列就是排序好的，对于冒泡排序仍然还要比较O(N^2)次，但无交换次数。可根据这个进行优化，设置一个flag，当在一趟序列中没有发生交换，则该序列已排序好，但优化后排序的时间复杂度没有发生量级的改变。

代码

插入排序

原理

依次选择一个待排序的数据，插入到前边已排好序的序列中。

性能

时间复杂度为O(N^2)，空间复杂度为O(1)。算法是稳定的，比较次数和交换次数都与初始序列有关。

优化

直接插入排序每次往前插入时，是按顺序依次往前找，可在这里进行优化，往前找合适的插入位置时采用二分查找的方式，即折半插入。

折半插入排序相对直接插入排序而言：平均性能更快，时间复杂度降至O(NlogN)，排序是稳定的，但排序的比较次数与初始序列无关，总是需要foor(log(i))+1次排序比较。

使用场景

当数据基本有序时，采用插入排序可以明显减少数据交换和数据移动次数，进而提升排序效率。

代码

希尔排拆指序

原理

插入排序的改进版，是基于插入排序的以下俩点性质而提出的改进方法：

插入排序对几乎已排好序的数据操作时，效率很高，可以达到线性排序的效率。

但插入排序在每次往前插入时只能将数据移动一位，效率比较低。

所以希尔排序的思想是：

先是取一个合适的gap

缩小间隔gap，例如去gap=ceil(gap/2)，重复上述子序列划分和排序

直到，最后gap=1时，将所有元素放在同一个序列中进行插入排序为止。

性能

开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点;其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。

代码

选择排序

原理

每次从未排序的序列中找到最小值，记录并最后存放到已排序序羡碰列的末尾

性能

时间复杂度为O(N^2)，空间复杂度为O(1)，排序是不稳定的(把最小值交换到已排序的末尾导致的)，每次都能确定一个元素所在的最终位置，比较次数与初始序列无关。

代码

快速排序

原理

分而治之思想：

Divide：找到基准元素pivot，将数组A[p..r]划分为A[p..pivotpos-1]和A[pivotpos+1…q]，左边的元素都比基准小，右边的元素都比基准大;

Conquer：对俩个划分的数组进行递归排序;

Combine：因为基准的作用，使得俩个子数组就地有序，无需合并操作。

性能

快排的平均时间复杂度为O(NlogN)，空间复杂度为O(logN)，但最坏情况下，时间复杂度为O(N^2)，空间复杂度为O(N);且排序是不稳定的，但每次都能确定一个元素所在序列中的最终位置，复杂度与初始序列有关。

优化

当初始序列是非递减序列时，快排性能下降到最坏情况，主要因为基准每次都是从最左边取得，这时每次只能排好一个元素。

所以快排的优化思路如下：

优化基准，不每次都从左边取，可以进行三路划分，分别取最左边，中间和最右边的中间值，再交换到最左边进行排序;或者进行随机取得待排序数组中的某一个元素，再交换到最左边，进行排序。

在规模较小情况下，采用直接插入排序

代码

归并排序

原理

分而治之思想：

Divide：将n个元素平均划分为各含n/2个元素的子序列;

Conquer：递归的解决俩个规模为n/2的子问题;

Combine：合并俩个已排序的子序列。

性能

时间复杂度总是为O(NlogN)，空间复杂度也总为为O(N)，算法与初始序列无关，排序是稳定的。

优化

优化思路：

在规模较小时，合并排序可采用直接插入;

在写法上，可以在生成辅助数组时，俩头小，中间大，这时不需要再在后边加俩个while循环进行判断，只需一次比完。

代码

堆排序

原理

堆的性质：

是一棵完全二叉树

每个节点的值都大于或等于其子节点的值，为最大堆;反之为最小堆。

堆排序思想：

将待排序的序列构造成一个最大堆，此时序列的最大值为根节点

依次将根节点与待排序序列的最后一个元素交换

再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列

性能

时间复杂度为O(NlogN)，空间复杂度为O(1)，因为利用的排序空间仍然是初始的序列，并未开辟新空间。算法是不稳定的，与初始序列无关。

使用场景

想知道最大值或最小值时，比如优先级队列，作业调度等场景。

代码

计数排序

原理

先把每个元素的出现次数算出来，然后算出该元素所在最终排好序列中的绝对位置(最终位置)，再依次把初始序列中的元素，根据该元素所在最终的绝对位置移到排序数组中。

性能

时间复杂度为O(N+K)，空间复杂度为O(N+K)，算法是稳定的，与初始序列无关，不需要进行比较就能排好序的算法。

使用场景

算法只能使用在已知序列中的元素在0-k之间，且要求排序的复杂度在线性效率上。

代码

桶排序

原理

根据待排序列元素的大小范围，均匀独立的划分M个桶

将N个输入元素分布到各个桶中去

再对各个桶中的元素进行排序

此时再按次序把各桶中的元素列出来即是已排序好的。

性能

时间复杂度为O(N+C)，O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM)，空间复杂度为O(N+M)，算法是稳定的，且与初始序列无关。

使用场景

算法思想和散列中的开散列法差不多，当冲突时放入同一个桶中;可应用于数据量分布比较均匀，或比较侧重于区间数量时。

基数排序

原理

对于有d个关键字时，可以分别按关键字进行排序。有俩种方法：

MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序

LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

性能

时间复杂度为O(d*(N+K))，空间复杂度为O(N+K)。

总结

以上排序算法的时间、空间与稳定性的总结如下：

❺ 基本排序算法原理

算法原理：每次对相邻的两个元素进行比较，若前者大于后者则进行交换，如此一趟下来最后一趟的就是最大元素，重复以上的步骤，除了已经确定的元素 。

算法原理：每次对相邻的两个元素进行比较，若前者大于后者则进行交换，如此一趟下来最后一趟的就是最大元素，重复以上的步骤，除了已经确定的元素

算法步骤

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

2）第一个数组值作为比较值，首先保存到temp中，即temp=A[0]；

3）然后j-- ,向前搜索,找到小于temp后,因为s[i]的值保存在temp中,所以直接赋值,s[i]=s[j]

4）然后i++,向后搜索,找到大于temp后,因为s[j]的值保存在第2步的s[i]中,所以直接赋值,s[j]=s[i],然后j--,避免死循环

5）重复第3、4步，直到i=j,最后将temp值返回s[i]中

6)  然后采用“二分”的思想,以i为分界线,拆分成两个数组 s[0,i-1]、s[i+1,n-1]又开始排序

排序图解

算法原理：从第一个元素开始，左边视为已排序数组，右边视为待排序数组，从左往右依次取元素，插入左侧已排序数组，对插入新元素的左侧数组重新生成有序数组 。需要注意的是，在往有序数组插入一个新元素的过程中，我们可以采用按 顺序循环 比较，也可以通过 折半查找法 来找到新元素的位置，两种方式的效率 取决于数组的数据量

算法原理：希尔排序也是利用插入排序的思想来排序。希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了，插入效率比较高。

排序图解

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

归并排序，顾名思义就是一种 “递归合并” 的排序方法（这个理解很重要）。对于一个数列，我们把它进行二分处理，依次递归下去，然后将小范围的数进行排序，最后将其合并在一起。就实现了归并排序。

这实际上是运用了 分治思想 ，显然，想要把一个数列排好序，最终达到的目的就是它的任何一部分都是有序的。这样的话，我们可以考虑分别把数列分成N多个部分，让每个部分分别有序，然后再将其统一，变成所有的东西都有序。这样就实现了排序。这个想法就叫分治思想。

排序图解

排序图解

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

快速排序的基本思想就是从一个数组中任意挑选一个元素（通常来说会选择最左边的元素）作为中轴元素，将剩下的元素以中轴元素作为比较的标准，将小于等于中轴元素的放到中轴元素的左边，将大于中轴元素的放到中轴元素的右边。

然后以当前中轴元素的位置为界，将左半部分子数组和右半部分子数组看成两个新的数组，重复上述操作，直到子数组的元素个数小于等于1（因为一个元素的数组必定是有序的）。

以下的代码中会常常使用交换数组中两个元素值的Swap方法，其代码如下

publicstaticvoidSwap(int[] A, inti, intj){

inttmp;

tmp = A[i];

A[i] = A[j];

A[j] = tmp;

(6)排列算法的算法描述和实现扩展阅读：

快速排序算法 的基本思想是：将所要进行排序的数分为左右两个部分，其中一部分的所有数据都比另外一 部分的数据小，然后将所分得的两部分数据进行同样的划分，重复执行以上的划分操作，直 到所有要进行排序的数据变为有序为止。

定义两个变量low和high，将low、high分别设置为要进行排序的序列的起始元素和最后一个元素的下标。第一次，low和high的取值分别为0和n-1，接下来的每次取值由划分得到的序列起始元素和最后一个元素的下标来决定。

定义一个变量key，接下来以key的取值为基准将数组A划分为左右两个部分，通 常，key值为要进行排序序列的第一个元素值。第一次的取值为A[0]，以后毎次取值由要划 分序列的起始元素决定。

从high所指向的数组元素开始向左扫描，扫描的同时将下标为high的数组元素依次与划分基准值key进行比较操作，直到high不大于low或找到第一个小于基准值key的数组元素，然后将该值赋值给low所指向的数组元素，同时将low右移一个位置。

如果low依然小于high，那么由low所指向的数组元素开始向右扫描，扫描的同时将下标为low的数组元素值依次与划分的基准值key进行比较操作，直到low不小于high或找到第一个大于基准值key的数组元素，然后将该值赋给high所指向的数组元素，同时将high左移一个位置。

重复步骤(3) (4)，直到low的植不小于high为止，这时成功划分后得到的左右两部分分别为A[low……pos-1]和A[pos+1……high]，其中，pos下标所对应的数组元素的值就是进行划分的基准值key，所以在划分结束时还要将下标为pos的数组元素赋值 为 key。