各种排序算法总结.doc

《各种排序算法总结.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、各种排序算法总结　　各种排序算法总结排序算法是最基本最常用的算法，不同的排序算法在不同的场景或应用中会有不同的表现，我们需要对各种排序算法熟练才能将它们应用到实际当中，才能更好地发挥它们的优势。　　今天，来总结下各种排序算法。　　下面这个表格总结了各种排序算法的复杂度与稳定性各种排序算法复杂度比较.png冒泡排序冒泡排序可谓是最经典的排序算法了，它是基于比较的排序算法，时间复杂度为O(n^2)，其优点是实现简单，n较小时性能较好。　　?算法原理相邻的数据进行两两比较，小数放在前面，大数放在后面，这样一趟下来，最小的数就被排在了第一位，第二趟也是如此，如此类推，直到所有的数据排序完成?c++代

2、码实现1.voidbubble_sort(intarr[],intlen)2.{3.for(inti=0;i=i;j--)6.{7.if(arr[j]　　以此类推，直到所有元素均排序完毕。　　?c++代码实现1.voidselect_sort(intarr[],intlen)2.{3.for(inti=0;i　　插入排序又分为直接插入排序、二分插入排序、链表插入等，这里只讨论直接插入排序。　　它是稳定的排序算法，时间复杂度为O(n^2)?c++代码实现1.voidinsert_sort(intarr[],intlen)2.{3.for(inti=1;i-1&&k　　它的基本思想是通过一趟排序

3、将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。　　?c++代码实现1.voidquick_sort(intarr[],intleft,intright)2.{3.if(lefttarget)9.j--;10.if(i　　(1)，但如果是使用数组来存储数据的话，在归并的过程中，需要临时空间来存储归并好的数据，所以空间复杂度为O(n)?c++代码实现1.voidmerge(intarr[],inttemp_arr[],intstart_index,intm

4、id_index,intend_index)2.{3.inti=start_index,j=mid_index+1;4.intk=0;5.while(iarr[j])8.temp_arr[k++]=arr[j++];9.else10.temp_arr[k++]=arr[i++];11.}12.while(i　　当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。　　一般二叉树简称为堆。　　堆的存储一般都是数组来存储堆，i结点的父结点下标就为(i–1)/2。　　它的左右子结点下标分别为2*i+1和2*i+2。　　如第0个结点左右子结点下标分别为1和2。　　存储结构如图所示堆结构.png

5、堆排序原理堆排序的时间复杂度为O(nlogn)?算法原理（以最大堆为例）o先将初始数据R[1..n]建成一个最大堆，此堆为初始的无序区o再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].keyo由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。　　o重复　　2、3步骤，直到无序区只有一个元素为止。　　?c++代码实现1./**2.*将数组arr构建大根堆3.*@paramarr待调整的数组4.*@parami待调整的数组元素的下标5.*

6、@paramlen数组的长度6.*/7.voidheap_adjust(intarr[],inti,intlen)8.{9.intchild;10.inttemp;11.12.for(;2*i+1arr[child])17.child++;18.//如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点19.if(arr[i]=0;i--)38.{39.heap_adjust(arr,i,len);40.}41.42.for(i=len-1;i>0;i--)43.{44.//将第1个元素与当前最后一个元素交换，保证当前的最后一个位置的元素都是现在的这个序列中最大的45.intt

7、emp=arr[0];46.arr[0]=arr[i];47.arr[i]=temp;48.//不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值49.heap_adjust(arr,0,i);50.}51.}【推荐】1.移动开发者服务联盟第二期线下公开课总结高效，高效，还是高效！2.Java习惯用法总结3.3年代码总结分享4.使用Playground学习数值算法5.Android6.