资源描述：
《程序员必须知道的8大排序和3大查找》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、程序员必须知道的8大排序和3大查找现在我们分析一下8种排序算法的稳定性。（请网友结合前面的排序基本思想来理解排序的稳定性（8种排序的基本思想己经在前面说过，这里不再赘述）不然可能有些模糊）（1）直接插入排序：一般插入排序，比较是从有序序列的最后一个元索开始，如果比它大则直接插入在其后面，否则一直往前比。如杲找到一个和插入元素相等的，那么就插入到这个相等元素的后而。插入排序是稳定的。（2）希尔排序：希尔排序是按照不同步长对元素进行插入排序，一次插入排序是稳定的，不会改变相同元索的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，稳定性就会被破坏
2、，所以希尔排序不稳定。（3）简单选择排序：在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后而，那么交换后稳定性就被破坏了。光说可能有点模糊，来看个小实例：858410,笫一遍扫描，笫1个元素8会和4交换，那么原序列屮2个8的相对前后顺序和原序列不一致了，所以选择排序不稳定。（4）堆排序：堆排序的过程是从第n/2开始和其了节点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素Z间的选择当然不会破坏稳定性。但当为n/2-1,n/2-2,・・•这些父节点选择元素时，有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1
3、个父节点把后面一个相同的元素没有交换，所以堆排序并不稳定。（5）冒泡排序：由前而的内容可知，冒泡排序是相邻的两个元素比较，交换也发生在这两个元索之间，如果两个元索相等，不用交换。所以冒泡排序稳定。（6）快速排序：在中枢元素和序列中一个元素交换的时候，很有可能把前面的元素的稳定性打乱。还是看一个小实例：64454789,第一趟排序，屮枢元索6和第三个4交换就会把元索4的原序列破坏，所以快速排序不稳定。（7）归并排序：在分解的了列中，有1个或2个元素时，1个元素不会交换，2个元素如果大小相等也不会交换。在序列合并的过程屮，如果两个当前元素相等时，我们把处在前面的序列的元
4、素保存在结果序列的前面，所以，归并排序也是稳定的。（8）基数排序：是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。8种排序的分类，稳定性，吋间复杂度和空间复杂度总结:H性定稳7n20((n20(xllz00(0((n20(xnz定稳不选择n2)X17(n20(序排堆xlfz定稳不n2)0(7n2z(xo0o定稳不2o(nl0((n)0(X17rd)L+rd(
5、nrd0(注:琴教排序的复杂度中,r代表关键字的基数,d代表长度,n代表关键字的个数。常见查找1・顺序表的查找所谓顺序表，特点是相邻记录的物理位置也是相邻的。1）顺序查找算法思路：给定一个key值，在表屮顺序对比，若存在k二key,则查找成功,返回记录序号，或者成功1,失败返回0；2）折半杳找对于有序的顺序存储表来说，可以用这个方法挺高查找效率。算法思路：1＞给定值key,逐步确定待查记录所在区间，每次将搜索空间减少一半，直到查找成功或者失败为止。2＞设两个指针（或者游标）low,high,分别表示头和尾,初始时1ow=1,high=n令mid=（low+high）
6、/2;3＞将mid指向的值与key值比较如果micKkey,则说明要找的值应该往high靠近,令low二二"mid+1；比较如果mid二〃〃＞key,则说明要找的值应该往low靠近，令high=high-1；当key=mid所指向的值或者low＜=high不满足时返回。＜/key,则说明要找的值应该往high靠近，令low＞简单代码举例:1^include2itincludc33^defineMAXSIZE104ttdefineTRUE12^defineFALSE073intbin_search(int*list,intlen,
7、intkey);9lOintmain(intarge,char*argv[])11{12intlist[MAXSIZE]={1,3,5,7,9,11,13,15,17,19};13intkey=18;14printf(z，%dz，,bin_search(list,MAXSIZE,key));15return0;16}1718intsqserch(int*list,intlen,intkey)//顺序查找19{20inti;21i二len;22whilc(list[i]!=key&&i>=0)i--;23returni;24}2526intbinsearch(
