数据结构-各类排序算法总结

1、数据结构-各类排序算法总结原文转自： HYPERLINK /zjf280441589/article/details/38387103 /zjf280441589/article/details/38387103各类排序算法总结一.排序的基本概念排序(Sorting )是计算机程序设计中的一种重要操作，其功能 是对一个数据元素集合或序列重新排列成一个按数据元素 某个项值有序的序列。有n个记录的序列R1，R2，Rn，其相应关键字的序 列是K1，K2，Kn，相应的下标序列为1，2，n。 通过排序，要求找出当前下标序列1，2，n的一种排 列p1，p2，pn，使得相应关键字满足如下的非递减(或 非递增

2、)关系，即：Kp1Kp2Kpn5这样就得到一个按 关键字有序的记录序列Rp1 , Rp2 ,，Rpn。作为排序依据的数据项称为“排序码”，也即数据元素的关键 码。若关键码是主关键码，则对于任意待排序序列，经排序 后得到的结果是唯一的；若关键码是次关键码，排序结果可能不唯一。实现排序的基本操作有两个:(1广比较”序列中两个关键字的大小；(2广移动”记录。若对任意的数据元素序列，使用某个排序方法，对它按关键 码进行排序：若相同关键码元素间的位置关系，排序前与排 序后保持一致，称此排序方法是稳定的；而不能保持一致的 排序方法则称为不稳定的。二.插入类排序直接插入排序直接插入排序是最简单的插入类排序。

3、仅有 一个记录的表总是有序的，因此，对n个记录的表，可从 第二个记录开始直到第n个记录，逐个向有序表中进行插 入操作，从而得到n个记录按关键码有序的表。它是利用顺 序查找实现“在R1.i-1 中查找Ri的插入位置”的插入排序。注意直接插入排序算法的三个要点：(1 )从Ri-1起向前进行顺序查找，监视哨设置在R0;cpp viewplaincopyR0 = Ri; / 设置“哨兵”for (j=i-1; R0.keyRj.key; -j) / 从后往前找return j+1; /返回Ri的插入位置为j+1( 2)对于在查找过程中找到的那些关键字不小于Ri.key的记录，可以在查 找的同时实现向后

4、移动，即:查找与移动同时进行.cpp view plaincopyfor (j=i-1; R0.keyRj.key; -j) (Rj+1 = Rj; ( 3)i = 2，3，n,实现整个序列的排序(从i = 2开始).【算法如下】cpp view plaincopy/C+代码,确保能够运行 void insertionSort(int *R,int length) (for (int i = 2; i = length; +i)(R0 = Ri;设为监视哨int j;for (j = i-1; R0 Rj; -j)(Rj+1 = Rj; /边查找边后移Rj+1 = R0;/插入到正确位置【性能

5、分析】空间效率：仅用了一个辅助单元，空间复杂度为O(1)。 只需R0做辅助.时间效率：向有序表中逐个插入记录的操作，进行了 n-1趟，每趟操作分为比较关键码和移动记录，而比较的次 数和移动记录的次数取决于待排序列按关键码的初始排列。直接插入排序的最好情况的时间复杂度为O(n)，平均时间复杂度为0(时2)。稳定性：直接插入排序是一个稳定的排序方法。总体来说:直接插入排序比较适用于带排序数目少，且基本有 序的情况下.折半插入排序直接插入排序的基本操作是向有序表中插入一个记录，插入 位置的确定通过对有序表中记录按关键码逐个比较得到的。 平均情况下总比较次数约为(2)/4。既然是在有序表中确定 插入位

6、置，可以不断二分有序表来确定插入位置，即一次比 较，通过待插入记录与有序表居中的记录按关键码比较，将 有序表一分为二，下次比较在其中一个有序子表中进行，将 子表又一分为二。这样继续下去，直到要比较的子表中只有 一记录时，比较一次便确定了插入位置。折半插入排序是利用折半查找实现“在R1.i-1中查找Ri的 插入位置”。综上:折半插入排序只是减少了比较的次数，因此折半插入排 序总的时间复杂度仍是O(V2).希尔排序希尔排序又称缩小增量排序，较直接插入排序和折半插入排 序方法有较大的改进。直接插入排序算法简单，在n值较 小时，效率比较高，在n值很大时，若序列按关键码基本 有序,效率依然较高，其时间效

7、率可提高到o(n)。希尔排序 即是从这两点出发，给出插入排序的改进方法。希尔排序的基本思想是：先将待排序记录序列分割成若干个 “较稀疏的”子序列，分别进行直接插入排序。经过上述粗略 调整，整个序列中的记录已经基本有序，最后再对全部记 录进行一次直接插入排序。具体实现时，首先选定两个记录 间的距离di,在整个待排序记录序列中将所有间隔为di的 记录分成一组，进行组内直接插入排序，然后再取两个记录 间的距离d2 Rj+1) 如果相邻元素中大者在 前,交换之(int temp = Rj;Rj = Rj+1;Rj+1 = temp;change = true;【性能分析】空间效率：仅用了一个辅助单元，

8、空间复杂度为0(1)。时间效率：最好情况的时间复杂度为0(n)，平均时间复 杂度为0(n入2)。稳定性：冒泡排序法是一种稳定的排序方法总比较次数快速排序快速排序是通过比较关键码、交换记录，以某个记录为界(该 记录称为支点)，将待排序列分成两部分。其中，一部分所有 记录的关键码大于等于支点记录的关键码，另一部分所有记 录的关键码小于支点记录的关键码。我们将待排序列按关键 码以支点记录分成两部分的过程，称为一次划分。对各部分 不断划分，直到整个序列按关键码有序.如果每次划分对一个元素定位后，该元素的左侧子序列与右 侧子序列的长度相同，则下一步将是对两个长度减半的子序 列进行排序,这是最理想的情况！

9、【算法如下】cpp viewplaincopy/伪码表示一趟快速排序算法：int Partitionl (Elem R, int low, int high)(pivotkey = Rlow.key; /用子表的第一个记录作枢轴记 录while (lowhigh) /从表的两端交替地向中间扫描(while (low=pivotkey)(-high;RlowjfRhigh; /将比枢轴记录小的记录交换到低端while (lowhigh &Rlow.key=pivotkey)(+low;RlowjfRhigh; /将比枢轴记录大的记录交换到高端return low; /返回枢轴所在位置容易看出，调

10、整过程中的枢轴位置并不重要，因此，为了减 少记录的移动次数，应先将枢轴记录“移出”，待求得枢轴记 录应在的位置之后(此时low=high),再将枢轴记录到位。将上述“一次划分”的算法改写如下：cpp viewplaincopyint Partition2 (Elem R, int low, int high)(R0 = Rlow; /用子表的第一个记录作枢轴记录pivotkey = Rlow.key; / 枢轴记录关键字while (low high) /从表的两端交替地向中间扫 描(while (low=pivotkey)(-high;Rlow = Rhigh; /将比枢轴记录小的记录移到低

11、 -LdJ 端while (lowhigh &Rlow.key=pivotkey)(+low;Rhigh = Rlow; /将比枢轴记录大的记录移到高-LdJ端Rlow = R0; /枢轴记录到位return low; /返回枢轴位置 cpp viewplaincopy/递归形式的快速排序算法：void QSort (Elem R, int low, int high)(对记录序列Rlow.high进行快速排序if (low high-1) / 长度大于 1(pivotloc = Partition(L, low, high); / 将 L.rlow.high 一分为二QSort(L, low

12、, pivotloc-1); / 对低子表递归排序， pivotloc是枢轴位置QSort(L, pivotloc+1, high); / 对高子表递归排序void QuickSort(Elem R, int n) /对记录序列进行快速排 序(QSort(R, 1, n);【性能分析】空间效率：快速排序是递归的，每层递归调用时的指针和 参数均要用栈来存放，递归调用层次数与上述二叉树的深度 一致。因而，存储开销在理想情况下为O(log2n)，即树的高 度；在最坏情况下，即二叉树是一个单链，为O(n)。(2)时间效率：在n个记录的待排序列中，一次划分需要约n 次关键码比较，时效为O(n)，若设T(

13、n)为对n个记录的待 排序列进行快速排序所需时间。理想情况下：每次划分，正 好将分成两个等长的子序列，则plain viewplaincopy T(n)cn+2T(n/2)c是一个常数cn+2(cn/2+2T(n/4)=2cn+4T(n/4)2cn+4(cn/4+T(n/8)=3cn+8T(n/8)O(n),时间复杂度-O(n入2)平均情况:空间复杂度-O(log2n),时间复杂度 -O(nlog2n)(5)快速排序比较适用于输入规模n较大的情况.四.选择类排序选择排序简单选择排序是最简单的一种选择类的排序方法。假设排序 过程中，待排记录序列的状态为：并且有序序列中所有记录的关键字均小于无序序

14、列中记录 的关键字，则第i趟简单选择排序是，从无序序列Ri.n的 n-i+1记录中选出关键字最小的记录加入有序序列。操作方法：第一趟，从n个记录中找出关键码最小的记录与 第1个记录交换；第二趟，从第二个记录开始的n-1个记 录中再选出关键码最小的记录与第2个记录交换；如此，第 i趟则从第i个记录开始的n-i+1个记录中选出关键码最小 的记录与第i个记录交换，直到整个序列按关键码有序。【算法如下】cpp viewplaincopy/C+代码int selectMinIndex(int *A,int index,int length) (int min = index;for (int i = i

15、ndex+1; i != length; +i)(if (Ai 0; -i )/把R1.n建成大顶堆HeapAdjust ( R, i, n );for ( i=n; i1; -i )(R1一Ri;/将堆顶记录和当前未经排序子序列,R1.i中最后一个记录相互交换HeapAdjust(R, 1, i-1);/ 将 R1.i-1重新调整为大顶堆?其中筛选的算法如下所示。为将Rs.m调整为“大顶堆”，算 法中“筛选”应沿关键字较大的孩子结点向下进行。cpp view plaincopyvoid HeapAdjust (Elem R, int s, int m)(/*已知Rs.m中记录的关键字除Rs.

16、key之外均满足 堆的定义，本函数调整Rs的关键字，使Rs.m成为一个大顶堆(对其中记录的关键字 而言)*/rc = Rs;for ( j=2*s; j=m; j*=2 )/ 沿 key 较大的孩子结点向下筛选(if ( jm & Rj.key= Rj.key )break; / rc应插入在位置s上Rs = Rj;s = j;Rs = rc; / 插入【性能分析】空间效率：仅用了一个辅助单元，空间复杂度为O(1)。时间效率：对深度为k的堆，“筛选”所需进行的关键字比较的次数至对n个关键字，建成深度为h(=?log2n?+1)的堆，所需进 行的关键字比较的次数至多为4n;调整“堆顶”n-1次，

17、总共进行的关键字比较的次数不超过 plain viewplaincopy2(?log2(n-1)?+ ?log2(n-2)?+ .+log22)2n(?lo g2n?)因此，堆排序的平均和最坏时间复杂度均为 O(nlogn)。堆排序是一个不稳定的排序方法。2.二路归并排序：【算法思想】归并排序的基本思想是：将两个或两个以上的有序子序列“归 并”为一个有序序列。在内部排序中，通常采用的是2-路归并排序。即：将两个位 置相邻的有序子序列，空间复杂度为O(n),稳定，时间复杂度 O(nlog2n)【算法如下】cpp viewplaincopy/伪代码，不一定能够运行void Merge(Elem S

18、R, Elem TR, int i, int m, int n)(/将有序的SRi.m和SRm+1.n归并为有序的TRi.nfor (j=m+1, k=i; i=m & j=n; +k)/将SR中记录由小到大地并入TR(if (SRi.key=SRj.key)TRk = SRi+;elseTRk = SRj+;if (i=m)TRk.n = SRi.m; / 将剩余的 SRi.m复制到 TR if (j=n)TRk.n = SRj.n; / 将剩余的 SRj.n复制到 TR 归并排序的算法可以有两种形式：递归的和递推的，它是由 两种不同的程序设计思想得出的。在此，只讨论递归形式的算法，这是一种自顶向下的分析方 法：如果记录无序序列Rs.t的两部分Rs.?(s+t)/2?和 R?(s+t)