2022年2022年各种排序算法 .pdf

《2022年2022年各种排序算法 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年各种排序算法 .pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1. 冒泡排序 ，最简单也最常用的一种(_不复习的情况下， 笔试遇到排序问题， 我只能记住它 )，思想是：每次将数组前N 个中最大（升序）或最小（降序）的数交换到数组底部，每次数组大小N- ，再进行如此操作，直到所有的数都已排序即N=1 。这样循环比较的次数是（n-1 ）+(n-2)+(n-3). 约等于(n)(n+1)/2, 时间复杂度为O(n2),N的平方。 C 语言实现如下：void bubble_sort( int*array , int size )int i , j , temp ;for( i =size -1; i 1; i -)for( j =0; j array j +1)

2、 temp = array j +1; array j +1 = array j ; array j = temp;2. 交换排序 ，原理是用第一个元素和第二个元素比较，若第一个元素大于第二个，则交换，交换后第一个元素在与第三个元素比较. 直到 N 个元素，然后再选择第二个元素和第三个元素比较，进行同样操作 .直到选择到 N 个元素。这样操作完成后数组就变为升序了。其实说白了，原理就是第一次交换，确保第一个元素是最小的，第二次交换确保第二个元素是第二小的. 以此类推。效率也很低，循环次数(n-1)(n-2).即 O(n2), n的平方， C 语言实现如下：void change_sort (

3、int*array , int size )int i , j , temp ;for( i =0; i size ; i +)for( j =i +1; j array j ) temp = array j ; array j = array i ; array i = temp ;3. 选择排序 ，仔细看交换排序，发现其实没必要每次发现比自己小的元素就发生交换，只要和剩下的元素中最小的那个元素交换就可以了，即选择最小的元素进行交换，那么交换排序的扩展算法，选择排序就很容易得出来了，效率略比交换排序高，整体平均效率还是N 的平方， C 语言实现如下：void select_sort( int

4、*array , int size )int i , j , temp, pos ;for( i =0; i size ; i +) for(j =i +1, temp =array i , pos =i ; j array j ) temp = array j ; pos = j ; array pos = array i ; array i = temp ;4. 插入排序 ,有点类似冒泡排序的逆操作，也是比较简单易懂的算法。原理是，现对数组第一个和第二个排序，这样前 2 个元素就是有序的了，再引入第三个元素，找到合适的位置插入。以此插入剩余元素。这种排序算法比起冒泡排序算法效率更高，有点类

5、似冒泡排序的改进算法。虽然效率上比冒泡排序好，但名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - 是也是一种简单排序算法，循环次数为1+2+3.+n-1,即 n(n+1)/2, 平均情况下时间复杂度还是O(n2),n的平方。 C 语言实现如下：void insert_sort( int*array , int size )int i , j , temp ;for( i =1; i 0& temp0; gap=(gap = 2

6、?1:( int )( gap/ 2. 2) )for( i =gap; i =gap & temp array j - gap; j =j -gap) array j = array j - gap; array j = temp;6. 归并排序 ，采用的是分治算法，即将一组元素通过几次平分，分成若干组元素 （最终单个元素为一组），这样就形成一个满二叉树形结构，叶子节点为单个元素，归属于同一父节点的两组元素排序后归并成一组元素，最终归属于根节点的两组元素再归并成一组元素，完成排序。这是典型的分治算法，如能理解分治算法的含义，那么也不难理解归并排序。这个算法的缺点是需要借助于排序元素相同大小的

7、辅助数组，而且需要将数据反复的在原始数组和辅助数组之间拷贝，这些额外的工作大大降低了此算法的工作效率，时间复杂度为 O(NlogN),C编码如下：voidmerge( int*array , int*temp_array , intleft ,intright , intright_end )int left_end = right- 1 , i ;int tmp = left;int num = right_end - left+1;while( left= left_end & right= right_end)if(array left = array right ) temp_arra

8、y tmp+ = array left +;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - else temp_array tmp+ = array right +;while(left= left_end) temp_array tmp+ = array left+;while( right= right_end) temp_array tmp+ = array right +;for( i =0; i num ; i +,

9、 right_end-) array right_end = temp_array right_end ;void m_sort ( int*array ,int*temp_array ,intleft, intright )int center ;if( left right ) center = ( left +right )/ 2; m_sort( array , temp_array , left, center ); m_sort( array , temp_array , center +1,right );merge(array , temp_array ,left , cent

10、er +1, right );void merge_sort (int*array , int size )int*temp = ( int *) malloc ( size );memset ( temp, 0 , size ); m_sort( array , temp, 0 , size - 1);free ( temp);名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - 7. 快速排序 .实际应用中用的最多的，也是最常见

11、的一种排序方法，其主要思想还是用了分治法，算法是，从数组中找到一个支点，通过交换，使得支点的左边都是小于支点的元素，支点的右边都是大于支点的元素，而支点本身所处的位置就是排序后的位置！然后把支点左边和支点右边的元素看成两个子数组，再进行如上支点操作直到所有元素有序！这是基本的算法思想，各种不同的实现可能和支点的选择有关，最简单的是选择第一个元素做支点，常用的是选择中间的元素做支点，而本文的实现代码是第一个元素，中间元素，最后一个元素，这三个元素的中值即满足(abc)时，取 b 作为支点，这样能比纯粹的选第一个元素和中间元素更加合理。实现代码如下：voidswap( int* a, int*b)

12、 /交换函数int temp = *a;*a = *b;*b = temp;intpartition( int* array , int low , int high )int middle = ( low+high )/ 2, temp , pivot, i , j ;/ 选择第一个元素，最后一个元素，中间元素中的中间值作为支点if( array middle array low)swap(&array middle ,&array low);if( array high array low)swap (&array high ,&array low);if( array high arra

13、y middle )swap (&array high ,&array middle ); pivot = array middle ;/ 选中支点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - swap (&array middle ,&array high -1); / 将支点值换到倒数第二个位置for(i =low, j =high -1; ;)while( array + i pivot ) /找到一个大于支点的元素w

14、hile( pivot array - j ) /找到一个小于支点的元素if( i j ) /交换两个元素 temp = array j ; array j = array i ; array i =temp; elsebreak;swap (&array i ,&array high - 1);/ 将支点换回 i 点, 第一次分组结结束return i ;void quicksort( int*array ,int low ,int high )int piovt_pos ;if( low 0; i /=2) if( array i / 2 data ) / 与父节点比较 , 大于父节点则交

15、换位置 array i = array i / 2;elsebreak; array i = data ; / 插入名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - int heapdel (int*array , int len )intmin, last, i , j ;min = array 1;/ 堆顶元素删除 last = array len -;for(i =1; i *2=len ; i =j ) j = i *2

16、; /i的左儿子if( j!=len) & ( array j +1 array j ) array i = array j ;elsebreak; array i = last; / 将最后一个元素填入空白returnmin;void heap_sort ( int*array ,int size )名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 14 页 - - - - - - - - - int*temp = ( int *) malloc ( size +1);/

17、 方便编码，下标 0 的不用，从 1 开始int i ;for( i =0; i size ; i +) heapinsert( temp, i +1, array i );for( i =0; i size ; i +) array i = heapdel ( temp, size - i ); array size - 1= temp 1;free ( temp);9. 基数排序这种排序算法区别于以上的所有排序算法，以上的排序算法都是通过单个关键字的比较，移动元素位置来达到形成有序序列的目的。基数排序是利用将自身分解成多个关键字，通过依次对单个关键字的进行排序来达到整体的有序。比如扑克牌的

18、排序，可以将扑克牌的关键字分为花色和点数两个关键字。基数排序需要借助额外的存储空间，算法的时间复杂度为O(d(n+rd),其中 r,d 的大小和关键字的个数和额外存储的大小有关。 这里以 N 个正整数为例， 可以将正整数的每一位作为关键字，即个位，十位，百位。 。分别作为关键字，借助10 个链表，标号09 ，第一轮用个位关键字，遍历数组，以个位为标准，依次插入相应的链表，即个位0 的插入 0 号链，个位 1 的插入 1 号链，数组元素全部插入后，又依次从头部删除 09号链，删除的元素依次存入原数组，这样完成第一轮操作，然后进行第二轮操作，以十位为标准，重复以上操作，直到轮数等于最大数的位数。为

19、了简化代码实现，用STL 中的 LIST 实现如下：int get_radix( int num, int radix )/ 取得基数位的数int temp ;for ( int i =0; i radix ; i +) temp = num% 10;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - num = num/ 10;return temp ;void radix_sort(int*array , int size

20、)list temp_list 10;intmax , radix , i , j , k ;char temp_buf 20;list: iterator iter;memset ( temp_buf, 0 , sizeof ( temp_buf);max = array/ （1）平方阶 (O(n2) 排序一般称为简单排序，例如直接插入、直接选择和冒泡排序；（2）线性对数阶 (O(nlgn)排序如快速、堆和归并排序；（3）O(n1+) 阶排序是介于 0 和 1 之间的常数，即 01，如希尔排序；（4）线性阶 (O(n)排序如桶、箱和基数排序。名师资料总结 - - -精品资料欢迎下载 - -

21、- - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - 各种排序方法比较简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。影响排序效果的因素因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：待排序的记录数目n；记录的大小 ( 规模) ；关键字的结构及其初始状态；对稳定性的要求；语言工具的条件；存储结构；时间和辅助空间复杂度等。不同条件下，排序方法的选择(1) 若 n 较小( 如 n50) ，可采用直接插入或直接选择排序。

22、当记录 规模较小 时，直接插入 排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。(2) 若文件初始状态基本有序 ( 指正序 ) ，则应选用直接插人、 冒泡或随机的快速排序为宜；(3) 若 n 较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 -

23、- - - - - - 第 12 页，共 14 页 - - - - - - - - - 的最坏情况。这两种排序都是不稳定的。若要求排序 稳定，则可选用 归并排序 。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡， 通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。 因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。(4) 在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。当文件的 n 个关键字随机分布时，任何借助于 比较 的排序算法，至少需要 O(nlgn)

24、的时间。箱排序和基数排序只需一步就会引起m种可能的转移，即把一个记录装入 m个箱子之一，因此在一般情况下，箱排序和基数排序可能在O(n) 时间内完成对 n 个 记录的排序。但是，箱排序和基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合( 例如实数型关键字 ) 时， 无法使用箱排序和基数排序，这时只有借助于 比较 的方法来排序。若 n 很大，记录的关键字位数较少且可以分解时，采用基数排序较好。虽然桶排序对关键字的结构无要求， 但它也只有在关键字是随机分布时才能使平均时间达到线性阶，否则为平方阶。同时要注意，箱、桶、基数这三种分配排序均假定了关键字若为

25、数字时，则其值均是非负的，否则将其映射到箱( 桶) 号时，又要增加相应的时间。(5) 有的语言 ( 如 Fortran，Cobol或 Basic等) 没有提供指针及递归，导致实现归并、快速 ( 它们用递归实现较简单 ) 和基数 ( 使用了指针 ) 等排序算法变得复杂。此时可考虑用其它排序。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - (6) 本章给出的排序算法，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大

26、量的时间去移动记录，可以用链表作为存储结构。 譬如插入排序、归并排序、基数排序都易于在链表上实现，使之减少记录的移动次数。但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下，可以提取 关键字建立索引表，然后对索引表进行排序。然而更为简单的方法是：引人一个整型向量 t 作为辅助表，排序前令ti=i(0in)，若排序算法中要求交换 Ri和 Rj，则只需交换 ti和 tj即可；排序结束后，向量t 就指示了记录之间的顺序关系：Rt0.keyRt1.keyRtn-1.key 若要求最终结果是：R0.key R1.key Rn -1.key 则可以在排序结束后， 再按辅助表所规定的次序重

27、排各记录，完成这种重排的时间是 O(n) 。排序法最差时间分析平均时间复杂度稳定度空间复杂度冒泡排序O(n2) O(n2) 稳定O(1) 快速排序O(n2) O(n*log2n) 不稳定O(log2n)O(n) 选择排序O(n2) O(n2) 稳定O(1) 二叉树排序O(n2) O(n*log2n) 不一顶O(n) 插入排序O(n2) O(n2) 稳定O(1) 堆排序O(n*log2n) O(n*log2n) 不稳定O(1) 希尔排序O O 不稳定O(1名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -