《常用排序算法比较与分析.doc》由会员分享，可在线阅读，更多相关《常用排序算法比较与分析.doc（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、常用排序算法比拟与分析一、常用排序算法简述下面主要从排序算法的根本概念、原理出发,分别从算法的时间复杂度、空间复杂度、算法的稳定性与速度等方面进展分析比拟。依据待排序的问题大小(记录数量 n)的不同，排序过程中需要的存储器空间也不同，由此将排序算法分为两大类：【内排序】、【外排序】。内排序：指排序时数据元素全部存放在计算机的随机存储器RAM中。外排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中还需要对外存进展访问的排序过程。先了解一下常见排序算法的分类关系(见图1-1)图1-1 常见排序算法二、内排序相关算法2.1 插入排序核心思想：将一个待排序的数据元素插入到前面已经排
2、好序的数列中的适当位置，使数据元素依然有序，直到待排序数据元素全部插入完为止。2.1.1 直接插入排序核心思想：将欲插入的第i个数据元素的关键码与前面已经排序好的i-1、i-2 、i-3、 数据元素的值进展顺序比拟，通过这种线性搜索的方法找到第i个数据元素的插入位置 ，并且原来位置 的数据元素顺序后移，直到全部排好顺序。直接插入排序中，关键词一样的数据元素将保持原有位置不变，所以该算法是稳定的，时间复杂度的最坏值为平方阶O(n2)，空间复杂度为常数阶O(l)。Python源代码：1. #-直接插入排序-2. definsert_sort(data_list):3. #遍历数组中的所有元素，其中
3、0号索引元素默认已排序，因此从1开场4. forxinrange(1,len(data_list):5. #将该元素与已排序好的前序数组依次比拟，如果该元素小，那么交换6. #range(x-1,-1,-1):从x-1倒序循环到07. foriinrange(x-1,-1,-1):8. #判断：如果符合条件那么交换9. ifdata_listidata_listi+1:10. temp=data_listi+111. data_listi+1=data_listi12. data_listi=temp2.1.2 希尔排序核心思想：是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序;随
4、着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。希尔排序时间复杂度会比O(n2)好一些，然而，屡次插入排序中，第一次插入排序是稳定的，但在不同的插入排序过程中，一样的元素可能在各自的插入排序中移动，所以希尔排序是不稳定的。Python源代码：1. #-希尔排序-2. definsert_shell(data_list):3. #初始化step值，此处利用序列长度的一半为其赋值4. group=int(len(data_list)/2)5. #第一层循环：依次改变group值对列表进展分组6. whilegroup0:7. #下面：利用直接插入排序的思
5、想对分组数据进展排序8. #range(group,len(data_list):从group开场9. foriinrange(group,len(data_list):10. #range(x-group,-1,-group):从x-group开场与选定元素开场倒序比拟，每个比拟元素之间间隔group11. forjinrange(i-group,-1,-group):12. #如果该组当中两个元素满足交换条件，那么进展交换13. ifdata_listjdata_listj+group:14. temp=data_listj+group15. data_listj+group=data_l
6、istj16. data_listj=temp17. #while循环条件折半18. group=int(group/2)2.2 选择排序核心思想：每一趟扫描时，从待排序的数据元素中选出关键码最小或最大的一个元素，顺序放在已经排好顺序序列的最后，直到全部待排序的数据元素排完为止。2.2.1 直接选择排序核心思想：给每个位置选择关键码最小的数据元素，即：选择最小的元素与第一个位置的元素交换，然后在剩下的元素中再选择最小的与第二个位置的元素交换，直到倒数第二个元素与最后一个元素比拟为止。根据其根本思想，每当扫描一趟时，如果当前元素比一个元素小，而且这个小元素又出现在一个与当前元素相等的元素后面，那
7、么它们的位置发生了交换，所以直接选择排序时不稳定的，其时间复杂度为平方阶O(n2)，空间复杂度为O(l)。Python源代码：1. #-直接选择排序-2. defselect_sort(data_list):3. #依次遍历序列中的每一个元素4. foriinrange(0,len(data_list):5. #将当前位置的元素定义此轮循环当中的最小值6. minimum=data_listi7. #将该元素与剩下的元素依次比拟寻找最小元素8. forjinrange(i+1,len(data_list):9. ifdata_listjminimum:10. temp=data_listj;1
8、1. data_listj=minimum;12. minimum=temp13. #将比拟后得到的真正的最小值赋值给当前位置14. data_listi=minimum2.2.2 堆排序堆排序时对直接选择排序的一种有效改良。核心思想：将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶的数据元素与序列的最后一个元素交换;接着重建堆、交换数据，依次下去，从而实现对所有的数据元素的排序。完成堆排序需要执行两个动作：建堆与堆的调整，如此反复进展。堆排序有可能会使得两个一样值的元素位置发生互换，所以是不稳定的，其平均时间复杂度为0(nlog2n)，空间复杂度为O(l)。Python源代码：1. #-
9、堆排序-2. #*获取左右叶子节点*3. defLEFT(i):4. return2*i+15. defRIGHT(i):6. return2*i+27. #*调整大顶堆*8. #data_list:待调整序列length:序列长度i:需要调整的结点9. defadjust_max_heap(data_list,length,i):10. #定义一个int值保存当前序列最大值的下标11. largest=i12. #执行循环操作：两个任务：1寻找最大值的下标；2.最大值与父节点交换13. while1:14. #获得序列左右叶子节点的下标15. left,right=LEFT(i),RIGHT
10、(i)16. #当左叶子节点的下标小于序列长度并且左叶子节点的值大于父节点时，将左叶子节点的下标赋值给largest17. if(leftdata_listi):18. largest=left19. #print(左叶子节点)20. else:21. largest=i22. #当右叶子节点的下标小于序列长度并且右叶子节点的值大于父节点时，将右叶子节点的下标值赋值给largest23. if(rightdata_listlargest):24. largest=right25. #print(右叶子节点)26. #如果largest不等于i说明当前的父节点不是最大值，需要交换值27. if(
11、largest!=i):28. temp=data_listi29. data_listi=data_listlargest30. data_listlargest=temp31. i=largest32. #print(largest)33. continue34. else:35. break36. #*建立大顶堆*37. defbuild_max_heap(data_list):38. length=len(data_list)39. forxinrange(int(length-1)/2),-1,-1):40. adjust_max_heap(data_list,length,x)41
12、. #*堆排序*42. defheap_sort(data_list):43. #先建立大顶堆，保证最大值位于根节点；并且父节点的值大于叶子结点44. build_max_heap(data_list)45. #i：当前堆中序列的长度.初始化为序列的长度46. i=len(data_list)47. #执行循环：1.每次取出堆顶元素置于序列的最后(len-1,len-2,len-3.)48. #2.调整堆，使其继续满足大顶堆的性质，注意实时修改堆中序列的长度49. whilei0:50. temp=data_listi-151. data_listi-1=data_list052. data_
13、list0=temp53. #堆中序列长度减154. i=i-155. #调整大顶堆56. adjust_max_heap(data_list,i,0)核心思想：顾名思义，就是一组待排序的数据元素中，按照位置的先后顺序相互比拟各自的关键码，如果是逆序，那么交换这两个数据元素，直到该序列数据元素有序为止。2.3.1 冒泡排序核心思想：对于待排序的一组数据元素，把每个数据元素看作有重量的气泡，按照轻气泡不能在重气泡之下的原那么，将未排好顺序的全部元素自上而下的对相邻两个元素依次进展比拟与调整，让较重的元素往下沉，较轻的往上冒。根据根本思想，只有在两个元素的顺序与排序要求相反时才将调换它们的位置，否
14、那么保持不变，所以冒泡排序时稳定的。时间复杂度为平方阶O(n2)，空间复杂度为O(l)。Python源代码：1. #-冒泡排序-2. defbubble_sort(data_list):3. length=len(data_list)4. #序列长度为length，需要执行length-1轮交换5. forxinrange(1,length):6. #对于每一轮交换，都将序列当中的左右元素进展比拟7. #每轮交换当中，由于序列最后的元素一定是最大的，因此每轮循环到序列未排序的位置即可8. foriinrange(0,length-x):9. ifdata_listidata_listi+1:1
15、0. temp=data_listi11. data_listi=data_listi+112. data_listi+1=temp2.3.2 快速排序快速排序是对冒泡排序本质上的改良。核心思想：是一个就地排序，分而治之，大规模递归的算法。即：通过一趟扫描后确保基准点的这个数据元素的左边元素都比它小、右边元素都比它大，接着又以递归方法处理左右两边的元素，直到基准点的左右只有一个元素为止。快速排序时一个不稳定的算法，其最坏值的时间复杂度为平方阶O(n2)，空间复杂度为O(log2n)。Python源代码：1. #-快速排序-2. #data_list：待排序的序列；start排序的开场index
16、,end序列末尾的index3. #对于长度为length的序列：start=0;end=length-14. defquick_sort(data_list,start,end):5. ifstartend:6. i,j,pivot=start,end,data_liststart7. whileij:8. #从右开场向左寻找第一个小于pivot的值9. while(i=pivot):10. j=j-111. #将小于pivot的值移到左边12. if(ij):13. data_listi=data_listj14. i=i+115. #从左开场向右寻找第一个大于pivot的值16. whi
17、le(ij)and(data_listipivot):17. i=i+118. #将大于pivot的值移到右边19. if(ij):20. data_listj=data_listi21. j=j-122. #循环完毕后，说明i=j，此时左边的值全都小于pivot,右边的值全都大于pivot23. #pivot的位置移动正确，那么此时只需对左右两侧的序列调用此函数进一步排序即可24. #递归调用函数：依次对左侧序列：从0i-1/右侧序列：从i+1end25. data_listi=pivot26. #左侧序列继续排序27. quick_sort(data_list,start,i-1)28.
18、#右侧序列继续排序29. quick_sort(data_list,i+1,end)核心思想：把数据序列递归地分成短序列，即把1分成2、2分成4、依次分解，当分解到只有1个一组的时候排序这些分组，然后依次合并回原来的序列，不断合并直到原序列全部排好顺序。合并过程中可以确保两个相等的当前元素中，把处在前面的元素保存在结果序列的前面，因此归并排序是稳定的，其时间复杂度为O(nlog2n)，空间复杂度为O(n)。Python源代码：1. #-归并排序-2. #这是合并的函数3. #将序列data_listfirst.mid与序列data_listmid+1.last进展合并4. defmergear
19、ray(data_list,first,mid,last,temp):5. #对i,j,k分别进展赋值6. i,j,k=first,mid+1,07. #当左右两边都有数时进展比拟，取较小的数8. while(i=mid)and(j=last):9. ifdata_listi=data_listj:10. tempk=data_listi11. i=i+112. k=k+113. else:14. tempk=data_listj15. j=j+116. k=k+117. #如果左边序列还有数18. while(i=mid):19. tempk=data_listi20. i=i+121. k
20、=k+122. #如果右边序列还有数23. while(j=last):24. tempk=data_listj25. j=j+126. k=k+127. #将temp当中该段有序元素赋值给data_list待排序列使之局部有序28. forxinrange(0,k):29. data_listfirst+x=tempx30. #这是分组的函数31. defmerge_sort(data_list,first,last,temp):32. iffirstlast:33. mid=(int)(first+last)/2)34. #使左边序列有序35. merge_sort(data_list,f
21、irst,mid,temp)36. #使右边序列有序37. merge_sort(data_list,mid+1,last,temp)38. #将两个有序序列合并39. mergearray(data_list,first,mid,last,temp)40. #归并排序的函数41. defmerge_sort_array(data_list):42. #声明一个长度为len(data_list)的空列表43. temp=len(data_list)*None44. #调用归并排序45. merge_sort(data_list,0,len(data_list)-1,temp)2.5 基数排序核
22、心思想：首先是低位排序，然后收集;其次是高位排序，然后再收集;依次类推，直到最高位。Python源代码：1. #-基数排序-2. #确定排序的次数3. #排序的顺序跟序列中最大数的位数相关4. defradix_sort_nums(data_list):5. maxNum=data_list06. #寻找序列中的最大数7. forxindata_list:8. ifmaxNum0):13. maxNum=(int)(maxNum/10)14. times=times+115. returntimes16. #找到num从低到高第pos位的数据17. defget_num_pos(num,pos
23、):18. return(int)(num/(10*(pos-1)%1019. #基数排序20. defradix_sort(data_list):21. count=10*None#存放各个桶的数据统计个数22. bucket=len(data_list)*None#暂时存放排序结果23. #从低位到高位依次执行循环24. forposinrange(1,radix_sort_nums(data_list)+1):25. #置空各个桶的数据统计26. forxinrange(0,10):27. countx=028. #统计当前该位(个位，十位，百位.)的元素数目29. forxinrang
24、e(0,len(data_list):30. #统计各个桶将要装进去的元素个数31. j=get_num_pos(int(data_listx),pos)32. countj=countj+133. #counti表示第i个桶的右边界索引34. forxinrange(1,10):35. countx=countx+countx-136. #将数据依次装入桶中37. forxinrange(len(data_list)-1,-1,-1):38. #求出元素第K位的数字39. j=get_num_pos(data_listx,pos)40. #放入对应的桶中，countj-1是第j个桶的右边界索
25、引41. bucketcountj-1=data_listx42. #对应桶的装入数据索引-143. countj=countj-144. #将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表45. forxinrange(0,len(data_list):46. data_listx=bucketx三、排序算法实测图3-1 常用排序算法测试统计四、排序算法比照与分析表4-1各个排序算法比拟直接插入排序是对冒泡排序的改良，比冒泡排序快，但是只适用于数据量较小(1000 ) 的排序希尔排序比拟简单，适用于小数据量(5000以下)的排序，比直接插入排序快、冒泡排序快，因此，希尔排序适用于小
26、数据量的、排序速度要求不高的排序。直接选择排序与冒泡排序算法一样，适用于n值较小的场合，而且是排序算法开展的初级阶段，在实际应用中采用的几率较小。堆排序比拟适用于数据量到达百万及其以上的排序，在这种情况下，使用递归设计的快速排序与归并排序可能会发生堆栈溢出的现象。冒泡排序是最慢的排序算法，是排序算法开展的初级阶段，实际应用中采用该算法的几率比拟小。快速排序是递归的、速度最快的排序算法，但是在内存有限的情况下不是一个好的选择;而且，对于根本有序的数据序列排序，快速排序反而变得比拟慢。归并排序比堆排序要快，但是需要的存储空间增加一倍。基数排序适用于规模n值很大的场合，但是只适用于整数的排序，如果对浮点数进展基数排序，那么必须明确浮点数的存储格式，然后通过某种方式将其映射到整数上，最后再映射回去，过程复杂。【编辑推荐】1. Python分布式抓取和分析京东商城评价2. 硅谷资深数据科学家教你认清探索性数据分析EDA的价值3. 像Excel一样使用python进展数据分析-(2)4. 数据和分析带来五大积极业务成果5. 文本分析之制作网络关系图Python第 20 页