常用排序算法总结——数据结构

第 9章 排序设 n 个 记录的序列为 R1 , R2 , R3 , . . . , Rn 其相应的关键字序列为 K1 , K2 , K3 , . . . , Kn 若 规定 1 , 2 , 3 , . . . , n 的一个排列 p1 , p2 , p3 , . . . , pn ，使得相应的关键字满足如下非递减关系 :Kp Kp Kp . . . Kp1 2 3 n则 原序列变为一个按关键字有序的序列 :Rp , Rp , Rp , . . . , Rp1 2 3 n 此操作过程称为 排序 。排序第 9章 排序假设 Ki = Kj ，且 排序前序列中 Ri 领先于 Rj ；若在排序后的序列中 Ri 仍领先于 Rj ， 则称排序方法是稳定的 。若在排序后的序列中 Rj 仍领先于 Ri ， 则称排序方法是不稳定的 。例，序列 3 15 8 8 6 9若排序后得 3 6 8 8 9 15 稳定的若排序后得 3 6 8 8 9 15 不稳定的稳定排序与不稳定排序第 9章 排序内部排序 : 指的是待排序记录存放在计算机 随机存储器中进行的排序过程。外部排序 : 指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对 外存 进行访问的排序过程。内部排序与外部排序第 9章 排序排序的时间复杂性排序过程主要是对记录的排序码进行 比较和记录的移动 过程。因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少，则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。第 9章 排序按照排序过程中所依据的原则的不同可以分类为 : 插入排序 交换排序 (快速排序 ) 选择排序 归并排序 基数排序 二叉排序树排序内部排序第 9章 排序思想 : 利用有序表的插入操作进行排序有序表的插入 : 将一个记录插入到已排好序的有序表中，从而得到一个新的有序表。例，序列 13 27 38 65 76 97 插入 4913 27 38 49 65 76 97插入排序 直接插入排序第 9章 排序例，序列 49 38 65 97 76 13 27 初始， S = 49 ； 38 49 初始，令第 1 个元素作为初始有序表；依次插入第 2 , 3 , , k 个元素构造新的有序表；直至最后一个元素； 38 49 65 38 49 65 97 38 49 65 76 97 13 38 49 65 76 97 13 27 38 49 65 76 97 直接插入排序算法主要应用 比较 和 移动 两种操作。直接插入排序算法描述第 9章 排序void insertsort(ElemType R,int n)/待排序元素用一个数组 R表示，数组有 n个元素 for ( int i=1; i=0)j-)Rj+1=Rj; /元素后移空出插入位Rleft=temp; 第 9章 排序折半插入效率分析二分插入算法与直接插入算法相比，需要辅助空间与直接插入排序基本一致；时间上，前者的比较次数比直接插入查找的最坏情况好，最好的情况坏，两种方法的元素的移动次数相同，因此二分插入排序的时间复杂度仍为 O(n2)。二分插入算法与直接插入算法的元素移动一样是顺序的，因此该方法也是稳定的。第 9章 排序分析直接插入排序1. 若待排序记录序列按关键字 基本有序 ，则排序效率可大大提高；2. 待排序记录总数越少，排序效率越高；希尔 (shell)排序第 9章 排序思想 : 先将待排序记录序列分割成为若干子序列分别进行直接插入排序；待整个序列中的记录基本有序后，再全体进行一次直接插入排序。例，序列 49 38 65 97 76 13 27 48 55 4 19 第一趟排序 49 13 1938 2765 4897 5576 413 19 4927 3848 6555 974 76第 9章 排序第二趟排序13 19 4927 3848 6555 974 7613 55 38 7627 4 65 4948 19 9713 38 55 764 27 49 6519 48 97第三趟排序 4 13 19 27 38 48 49 55 65 76 97第 9章 排序希尔排序的算法希尔排序的算法template void ShellSort (T Vector, int arrSize ) T temp;int gap = arrSize / 2; /gap是子序列间隔 while ( gap != 0 ) /循环 ,直到 gap为零for ( int i = gap; i = gap; j -= gap )if ( temp =i; j-) if (Rj= pivot)high -;Arraylow = Arrayhigh;while(low high Arrayhigh = Arraylow;/ /在作为快排序的子程序时不用Arraylow = pivot;return low;第 9章 排序快排序（ Quick Sort)| 快排序 -算法z快排序算法是个递归地对序列进行分割的过程，递归终止的条件是最终序列长度为 10 1 2 3 4 5 6 749 38 65 97 76 13 27 4976 97 65 4927 38 13 494913 3827 49 65 977613 17 38 49 76 9749 65第 9章 排序快排序（ Quick Sort)|快排序 -算法void QuickSort(T Array, int low, int high)int PivotLocation;if(low high)PivotLocation = Partition(Array, low, high);QuickSort(Array, low, PivotLocation-1);QuickSort(Array, PivotLocation+1, high);第 9章 排序 3快速排序的效率分析若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数 n与二叉树深度 h应满足log2nhlog2n+1 ， 所以总的比较次数不会超过 (n+1) log2n。 因此，快速排序的最好时间复杂度应为 O（nlog2n）。 而且在理论上已经证明，快速排序的平均时间复杂度也为 O（ nlog2n）。若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），则这时得到的二叉树是一棵单分枝树，得到的非空子区间包含有 n-i个 (i代表二叉树的层