各种排序算法介绍

《各种排序算法介绍》由会员分享，可在线阅读，更多相关《各种排序算法介绍（8页珍藏版）》请在金锄头文库上搜索。

1、快速排序（Quicksort）是对冒泡排序的一 种改进。由 C. A. R. Hoare 在 1962 年提出。 它的基本思想是：通过一趟排序将要排序 的数据分割成独立的两部分，其中一部分 的所有数据都比另外一部分的所有数据都 要小，然后再按此方法对这两部分数据分 别进行快速排序，整个排序过程可以递归 进行，以此达到整个数据变成有序序列。算法过程 设要排序的数组是 A0AN-1，首先 任意选取一个数据（通常选用第一个数据） 作为关键数据，然后将所有比它小的数都 放到它前面，所有比它大的数都放到它后 面，这个过程称为一趟快速排序。一趟快 速排序的算法是： 1）设置两个变量 I、J，排序开始的时

2、候：I=0，J=N-1； 2）以第一个数组元素作为关键数据， 赋值给 key，即 key=A0； 3）从 J 开始向前搜索，即由后开始向 前搜索（J=J-1） ，找到第一个小于 key 的值 AJ，并与 AI交换； 4）从 I 开始向后搜索，即由前开始向 后搜索（I=I+1） ，找到第一个大于 key 的 AI，与 AJ交换； 5）重复第 3、4、5 步，直到 I=J； (3,4 步是在程序中没找到时候 j=j-1，i=i+1，直 至找到为止。找到并交换的时候 i， j 指针 位置不变。另外当 i=j 这过程一定正好是 i+ 或 j+完成的最后另循环结束) 例如：待排序的数组 A 的值分别是：

3、 （初始关键数据：X=49） 注意关键 X 永 远不变，永远是和 X 进行比较，无论在什 么位子，最后的目的就是把 X 放在中间， 小的放前面大的放后面。 A0 、 A1、 A2、 A3、 A4、A5、 A6： 49 38 65 97 76 13 27 进行第一次交换后： 27 38 65 97 76 13 49 ( 按照算法的第三步从后面开始找) 进行第二次交换后： 27 38 49 97 76 13 65 ( 按照算法的第四步从前面开始找X 的值，6549,两者交换，此时：I=3 ) 进行第三次交换后： 27 38 13 97 76 49 65 ( 按照算法的第五步将又一次执行算 法的第三

4、步从后开始找 进行第四次交换后： 27 38 13 49 76 97 65 ( 按照算法的第四步从前面开始找大 于 X 的值，9749,两者交换，此时： I=4,J=6 ) 此时再执行第三步的时候就发现 I=J， 从而结束一趟快速排序，那么经过一趟快 速排序之后的结果是：27 38 13 49 76 97 65，即所以大于 49 的数全部在 49 的后面， 所以小于 49 的数全部在 49 的前面。 快速排序就是递归调用此过程在 以 49 为中点分割这个数据序列，分别对前 面一部分和后面一部分进行类似的快速排 序，从而完成全部数据序列的快速排序， 最后把此数据序列变成一个有序的序列， 根据这种

5、思想对于上述数组 A 的快速排序 的全过程如图 6 所示： 初始状态 49 38 65 97 76 13 27 进行一次快速排序之后划分为 27 38 13 49 76 97 65 分别对前后两部分进行快速排序 27 38 13 经第三步和第四步交换后变成 13 27 38 完成排序。 76 97 65 经第三步和第四步交换后变成 65 76 97 完成排序。插入排序 有一个已经有序的数据序列，要求在这个 已经排好的数据序列中插入一个数，但要 求插入后此数据序列仍然有序，这个时候 就要用到一种新的排序方法插入排序 法,插入排序的基本操作就是将一个数据插 入到已经排好序的有序数据中,从而得到一

6、个新的、个数加一的有序数据，算法适用 于少量数据的排序，时间复杂度为 O(n2)。 是稳定的排序方法。插入算法把要排序的 数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外， 而第二部分就只包含这一个元素。在第一 部分排序后，再把这个最后元素插入到此 刻已是有序的第一部分里的位置 插入排序： 包括：直接插入排序，二分插入排序（又 称折半插入排序） ，链表插入排序，希尔排 序（又称缩小增量排序） 。 编辑本段 基本思想将 n 个元素的数列分为已有序和无序 两个部分，如 插入排序过程示例 下所示： ，a2，a3，a4，,an a1(1)，a2(1)，a3(1)，a4(1) ,a

7、n(1) a1(n-1)，a2(n-1) ，, an(n-1) 每次处理就是将无序数列的第一个元 素与有序数列的元素从后往前逐个进行比 较，找出插入位置，将该元素插入到有序 数列的合适位置中。 插入排序算法步骤1.从有序数列和无序数列a2,a3,an 开始进行排序； 2.处理第 i 个元素时(i=2,3,n) , 数列 a1,a2,ai-1是已有序的,而数列 ai,ai+1,an是无序的。用 ai 与 ai-1，a i- 2,a1 进行比较,找出合适的位置将 ai 插入；3.重复第二步，共进行 n-1 次插入处理， 数列全部有序。 void insertSort(Type* arr,long

8、len)/*InsertSort algorithm*/ long i=0,j=0;/*iterator value*/ Type tmpData; assertF(arr!=NULL,“In InsertSort sort,arr is NULLn“); for(i=1;i 0 j-; arrayj+1 = temp; 这个更好: void InsertSort(char array,unsigned int n) int i,j; int temp; for(i=1;i0 biIter bond = begin; std:advance(bond, 1); for(; bond!=end;

9、 std:advance(bond, 1) value_type key = *bond; biIter ins = bond; biIter pre = ins; std:advance(pre, -1); while(ins!=begin std:advance(ins, -1); std:advance(pre, -1); *ins = key; 希尔排序(Shell Sort)是插入排序的一种。是 针对直接插入排序算法的改进。该方法又 称缩小增量排序，因 DLShell 于 1959 年 提出而得名。 基本思想希尔排序基本思想： 先取一个小于 n 的整数 d1 作为第一个增量， 把文件

10、的全部记录分成 d1 个组。所有距离 为 dl 的倍数的记录放在同一个组中。先在 各组内进行直接插入排序；然后，取第二 个增量 d20i using namespace std; int main() int num10 = 9,8,10,3,4,6,4,7,2,1; cout numj) pos = j; int tem; tem = numpos; numpos = numi; numi = tem; coutdes then max=mid-1 else min=mid+1 return max 折半查找法也称为二分查找法，它充分利 用了元素间的次序关系，采用分治策略， 可在最坏的情况下

11、用 O(log n)完成搜索任务。 它的基本思想是，将 n 个元素分成个数大 致相同的两半，取 an/2与欲查找的 x 作比 较，如果 x=an/2则找到 x，算法终止。如 果 xan/2，则我们只要在数组 a 的右 半部继续搜索 x。堆排序 堆积排序(Heapsort)是指利用堆积树（堆） 这种资料结构所设计的一种排序算法，可 以利用数组的特点快速定位指定索引的元 素 树中任一非叶结点的关键字均不大于(或不 小于)其左右孩子(若存在)结点的关键字。 【例】关键字序列 (10，15，56，25，30，70)和 (70，56，30，25，15，10)分别满足堆性质 (1)和(2)，故它们均是堆，

12、其对应的完全二 叉树分别如小根堆示例和大根堆示例所示。大根堆和小根堆：根结点(亦称为堆顶)的关 键字是堆里所有结点关键字中最小者的堆 称为小根堆，又称最小堆。根结点(亦称为 堆顶)的关键字是堆里所有结点关键字中最 大者，称为大根堆，又称最大堆。注意： 堆中任一子树亦是堆。以上讨论的堆 实际上是二叉堆(Binary Heap)，类似地可定 义 k 叉堆。 堆的高度堆可以被看成是一棵树，结点在堆中 的高度可以被定义为从本结点到叶子结点 的最长简单下降路径上边的数目；定义堆 的高度为树根的高度。我们将看到，堆结 构上的一些基本操作的运行时间至多是与 树的高度成正比，为 O（lgn） 。 堆排序堆排序

13、利用了大根堆(或小根堆)堆顶记 录的关键字最大(或最小)这一特征，使得在 当前无序区中选取最大(或最小)关键字的记 录变得简单。 （1）用大根堆排序的基本思想 先将初始文件 R1.n建成一个大根 堆,此堆为初始的无序区 再将关键字最大的记录 R1(即堆 顶)和无序区的最后一个记录 Rn交换，由 此得到新的无序区 R1.n-1和有序区 Rn， 且满足 R1.n-1.keysRn.key 由于交换后新的根 R1可能违反堆 性质，故应将当前无序区 R1.n-1调整为 堆。然后再次将 R1.n-1中关键字最大的 记录 R1和该区间的最后一个记录 Rn-1 交换，由此得到新的无序区 R1.n-2和有 序

14、区 Rn-1.n，且仍满足关系 R1.n-2. keysRn-1.n.keys，同样要将 R1.n-2调 整为堆。 直到无序区只有一个元素为止。 （2）大根堆排序算法的基本操作： 初始化操作：将 R1.n构造为初始 堆； 每一趟排序的基本操作：将当前无 序区的堆顶记录 R1和该区间的最后一个 记录交换，然后将新的无序区调整为堆(亦 称重建堆)。 注意： 只需做 n-1 趟排序，选出较大的 n-1 个关键字即可以使得文件递增有序。 用小根堆排序与利用大根堆类似， 只不过其排序结果是递减有序的。堆排序 和直接选择排序相反：在任何时刻堆排序 中无序区总是在有序区之前，且有序区是 在原向量的尾部由后往

15、前逐步扩大至整个 向量为止 特点堆排序(HeapSort)是一树形选择排序。 堆排序的特点是：在排序过程中，将 Rl.n看 成是一棵完全二叉树的顺序存储结构，利 用完全二叉树中双亲结点和孩子结点之间 的内在关系(参见二叉树的顺序存储结构)， 在当前无序区中选择关键字最大(或最小)的 记录 堆排序与直接选择排序的区别直接选择排序中，为了从 R1.n中选 出关键字最小的记录，必须进行 n-1 次比 较，然后在 R2.n中选出关键字最小的记 录，又需要做 n-2 次比较。事实上，后面 的 n-2 次比较中，有许多比较可能在前面 的 n-1 次比较中已经做过，但由于前一趟 排序时未保留这些比较结果，所以后一趟 排序时又重复执行了这些比较操作。 堆排序可通过树形结构保存部分比较 结果，可减少比较次数。 算法分析堆排序的时间，主要由建立初始堆和 反复重建堆这两部分的时间开销构成，它 们均是通过调用 Heapify 实现的。 堆排序的最坏时间复杂度为 O(nlog2n)。 堆序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多， 所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为 O(1)，它是不稳定的排序方法。 #define MAX 100/数据元素的最大个