最常用的排序算法总结

最常用的排序算法总结实际应用中最常用的排序是快速排序和堆排序。所谓堆排序，就是将最小的一个值放到堆栈的顶部，这样就可以使最后出来的数完成排序。快速排序是不稳定的，堆排序是稳定的。所谓稳定，就是当两个值相等时，排序后两个值的顺序和排序前相同。以上两种排序使用的范围和情况是不同的，一般对于自然生成序列排序使用快速排序效率比较高，而对于已经有一定顺序的序列，使用堆排序比较合适，而且稳定的。这里主要总结常用的5种排序，分别是快速排序，冒泡排序(也叫交换排序)，选择排序，shell排序,插入排序。下边分别介绍：1快速排序，就是从一个序列中随意取一个数，然后对剩下的数进行分类，小的放到左边，大的放到右边。如此进行下去知道最后。N(n-l)/2.空间复杂度是o(n).2冒泡排序，就是从第一个数开始和后一个数比较，然后依情况交换,然后再用第二个和第三个比较交换，如此反复，直到最后一个。一直进行n轮就可以完成排序。3选择排序，就是将一个序列中的最小的放到第一个，然后再将剩下的数据用相同的方式分别放到后一位。它的空间复杂度是0(1).4shell排序，就是将有一定间隔的数进行排序，并且间隔变小,也就是开始是n/2,然后继续变小，一般都是以一半为标准，直到最后间隔只有2,也就完成了排序。需要的空间复杂度是0(1).5插入排序，就比如平时玩的扑克排，一般整理排的时候需要将排排序，当你拿到一张新排的时候，就要比较左边和右边，只有在左右中间的那个值的时候才说明排序成功。它需要的空间复杂度也是0(1).Ps:空间复杂度就是需要另外占用的空间。以上排序中，只有快速排序是O(n),其他都是0(2),因为只有快速排序需要另外再起存储空间，而其他都是在原来空间中增加一个空间就可以。1,快速排序这个有点难解释，感觉上就是纽来纽去,先从首记录开始也行，从未记录开始也行，以后补上.TonyHoare在1962年首次提出了快速排序算法。对快速排序方法的研究表明，至今快速排序算法仍然是流传久远的最实用的排序算法。只在输入数据项有更详细的信息时，其它排序算法才可能胜过快速排序算法。快速排序算法是利用分治技术的典型例子，随机分治策略是设计组合优化与计算几何一类问题有效算法的基础。分治策略分为三步：将问题分成若干大小基本相等的子问题；独立地解决这些子问题；将子问题归并成原问题的解。快速排序的基本思路是：首先我们选择一个中间值middle(程序中我们可使用数组中间值)，把比中间值小的放在其左边，比中间值大的放在其右边。由于这个排序算法较复杂，我们先给出其进行一次排序的程序框架(从各类数据结构教材中可得)：voidQuickSort(int*pData,intleft,intright){inti,j;intmiddle,iTemp;i二left;j二right;middle二pData[(left十right)/2];〃求中间值do{while((pData[i]middle)(iright))〃从左扫描大于中值的数i十十；while((pDataDJmiddle)(jleft))〃从右扫描小于中值的数j-■if(i二j)〃找到了一对值{〃交换iTemp二pData[i];pData[i]二pData[j];pDatafj]二iTemp;i十十;j_-;}}while(i二j);〃如果两边扫描的下标交错，就停止(完成一次)〃当左边部分有值(left<j),递归左半边></j),递归左半边〉if(left<j)></j)>Quicksort(pDataJeftj);〃当右边部分有值(righti),递归右半边if(righti)Quicksort(pData.i,right);}由此可见，上述排序算法中采用了递归策略。在我设定的一个杯林个无序记录集中快速排序比冒炮节省了差不多一半时间，估计记录越多,这个数量级会更高.2,选择排序，选择排序和冒泡如果不仔细看，光从字面解释,很多人都弄混，解释这个很简单，举个例子就行.如:2,6丄4首先将2和所有记录遍历，找出比他小的交换位置，于是(第一个记录)1.6.2.4第二次将6遍历,找出小的交换(第二个记录)1.2.6.4第三次......1,2,4,6完成！3冒泡这个就更加简单理解两两相互之间比较，大(或者小的)放到前面，但必须遍历N-1次.感觉上如果是无序的记录让他遍历效率会高.女11,2,6,1,42,1,4,6(小的交换后继续和后面的记录交换)1.2,4.6完成(N-1次???好象是说选择排序了，忘记了.)数据量少的时候可以用冒泡，某些人说过冒泡效率最低当然还有改良的冒泡双琏算法.voidCTestDlg::BubbleSort(int*pData,intiNum)//冒泡{inti,j;inttemp;for(i=iNum-l;ii--)//iNum-1次for(j=0;j<i;j++){<px/i；j++)>if(pData[j]pDataO+l]){temp=pData|j];pData[j]=pData[j+l];pData[j+l]二temp;}}}4插入排序将第一个记录看成己经排好的序列，其次数据一个一个与之前最大的记录比较，子成序列,听说是如果有序的记录集合排序效果好.voidCTestDlg::insert_sort(int*list,intlength){inti,j,temp;for(i二1;ilength;i十十){temp=list[i];j=i-1;while((list[j]temp)(j二0)){listD+l]=list[j]；j-；}list0+1]二temp;//show」ist(list,length);}}各种排序算法的比较(转)2008-07-3009:121.稳定性比较插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的选择排序、希尔排序、快速排序、堆排序是不稳定的2.时间复杂性比较插入排序、冒泡排序、选择排序的时间复杂性为O(n2)其它非线形排序的时间复杂性为O(nlog2n)线形排序的时间复杂性为O(n);3•辅助空间的比较线形排序、二路归并排序的辅助空间为0("其它排序的辅助空间为0(2);4•其它比较插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。反而在这种情况下，快速排序反而慢了。当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。若待排序的记录的关键字在一个明显有限范围内时，且空间允许是用桶排序。当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。当n较大时，关键字元素可能出现本身是有序的，对稳定性