面试排序算法总结.doc

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

1、面试排序算法总结　　排序算法　　1、插入排序插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。　　例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。　　以下面5个无序的数据为例652759

2、6458（文中仅细化了第四次插入过程）第1次插入:2765596458第2次插入:2759656458第3次插入:2759646558第4次插入:2758596465二二.、效率分析稳定空间复杂度O　　(1)时间复杂度O(n2)最差情况反序，需要移动n*(n-1)/2个元素最好情况正序，不需要移动元素数组在已排序或者是“近似排序”时，插入排序效率的最好情况运行时间为O(n)；插入排序最坏情况运行时间和平均情况运行时间都为O(n2)。　　通常，插入排序呈现出二次排序算法中的最佳性能。　　对于具有较少元素（如

3、n<=15）的列表来说，二次算法十分有效。　　在列表已被排序时，插入排序是线性算法O(n)。　　在列表“近似排序”时，插入排序仍然是线性算法。　　在列表的许多元素已位于正确的位置上时，就会出现“近似排序”的条件。　　通过使用O(nlog2n)效率的算法（如快速排序）对数组进行部分排序，然后再进行选择排序，某些高级的排序算法就是这样实现的。　　三三.算法实现从前向后查找的插入排序[cpp]viewplaincopy1./********************************************

4、************2.*函数名称InsertSort3.*参数说明pDataArray无序数组；4.*iDataNum为无序数据个数5.*说明插入排序6.*********************************************************/7.voidInsertSort(int*pDataArray,intiDataNum)8.{9.for(inti=1;ij)//挪动位置20.{21.pDataArray[k]=pDataArray[k-1];22.k--;23.}

5、24.pDataArray[k]=temp;//插入25.}26.}27.}但楼主发现从后面查找插入的方式，代码复杂程度较低[cpp]viewplaincopy1./********************************************************2.*函数名称InsertSort3.*参数说明pDataArray无序数组；4.*iDataNum为无序数据个数5.*说明插入排序6.************************************************

6、*********/7.voidInsertSort(int*pDataArray,intiDataNum)8.{9.for(inti=1;i=0&&pDataArray[j]>temp)//从后向前，找到比其小的数位置14.{15.pDataArray[j+1]=pDataArray[j];//向后挪动16.j--;17.}18.19.if(j!=i-1)//存在比其小的数20.pDataArray[j+1]=temp;21.}22.}　　2、选择排序比如在一个长度为N的无序数组中，在第一趟遍历N个数据

7、，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。　　以下面5个无序的数据为例5612809120（文中仅细化了第一趟的选择过程）第1趟1256809120第2趟1220809156第3趟1220569180第4趟1220568091二.算法分析平均时间复杂度O(n2)空间复杂度O　　(1)(用于交换和记录索引)稳定性不稳定（比如序列【5，5，3】第一趟就

8、将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）三三.算法实现[cpp]viewplaincopy1.//交换data1和data2所指向的整形2.voidDataSwap(int*data1,int*data2)3.{4.inttemp=*data1;5.*data1=*data2;6.*data2=temp;7.}8.9./********************************************